网页私服论坛

 找回密码
 立即注册
搜索
查看: 184531|回复: 0

A*算法解八数码

[复制链接]

1

主题

6

帖子

34

积分

新手上路

Rank: 1

积分
34
QQ
发表于 2015-7-11 04:26:26 | 显示全部楼层 |阅读模式
本帖最后由 __BlueGuy__ 于 2015-7-9 10:39 编辑
    八数码问题是指一个3X3的9格棋盘上放置1到8这8个数字,多余一个空格,空格周围的数字可以移动到空格中
    例如输入0,2,3,1,8,4,7,6,5这九个数(0表示空格位置),按输入顺序排列为setp 0,通过若干步移动就可以到达最终状态setp 2:
    setp 0
    0 2 3
    1 8 4
    7 6 5
    setp 1
    1 2 3
    0 8 4
    7 6 5
    setp 2
    1 2 3
    8 0 4
    7 6 5

    1 Create search tree Tr consisting only of the start node (root) n0. Put n0 on an ordered list called OPEN.
    2 Create empty list called CLOSED.
    3 If OPEN is empty, exit with failure.
    4 Move the first node on OPEN, called n, to CLOSED.
    5 If n is a goal node, exit with success; the solution is the path from n to n0 along the edges in Tr.
    6 Expand node n by generating a set M of successors and connect them to n. Also put the members of M on OPEN.
    7 Reorder the list OPEN according to a specific rule.
    8 Go to step 3.

    // f(x) = 节点深度
    // g(x) = 节点中不在最终位置上的数字个数

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define NUM 5
    typedef struct bgMatrix
    {
        int v, w;
        char matrix[NUM][NUM];
        int pre;
        int f;
        int g;
        bool isVisited;
    }Matrix;
    typedef struct bgQueue
    {
        Matrix* data;
        int length;
        int maxLength;
        int head;
        int tail;
    }BGQueue;
    typedef BGQueue* Queue;
    typedef struct bgStack
    {
        Matrix* data;
        int top;
    }BGStack;
    typedef BGStack* Stack;
    char srcMatrix[NUM][NUM] =
    {
        {'*', '*', '*', '*', '*'},
        {'*', '2', '8', '3', '*'},
        {'*', '1', '6', '4', '*'},
        {'*', '7', '0', '5', '*'},
        {'*', '*', '*', '*', '*'}
    };
    char dstMatrix[NUM][NUM] =
    {
        {'*', '*', '*', '*', '*'},
        {'*', '1', '2', '3', '*'},
        {'*', '8', '0', '4', '*'},
        {'*', '7', '6', '5', '*'},
        {'*', '*', '*', '*', '*'}
    };
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    int cnt = -1;
    Queue queue;
    Stack stack;
    bool astar(Matrix matrix);
    int getG(Matrix matrix);
    void initQueue(int length);
    void putQueue(Matrix matrix);
    Matrix getQueue(void);
    int isQueueEmpty(void);
    int isQueueFull(void);
    void initStack(int length);
    void pushStack(Matrix matrix);
    Matrix popStack(void);
    int isStackEmpty(void);
    int matrixCmp(char src[][NUM], char dst[][NUM]);
    void matrixCpy(char dst[][NUM], char src[][NUM]);
    void matrixPrint(char matrix[][NUM]);
    int main(int argc, char *argv[]) {
       
        Matrix src;
       
        initQueue(3628800+1);
        initStack(3628800+1);
       
        src.v = 3;
        src.w = 2;
        matrixCpy(src.matrix, srcMatrix);
        src.pre = cnt;
        src.f = 0;
        src.g = getG(src);
        astar(src);
        return 0;
    }
    bool astar(Matrix matrix)
    {
        Matrix t, s;
       
        int v, w;
       
        int direction;
       
        putQueue(matrix);
       
        while (!isQueueEmpty())
        {
            s = getQueue();
            
            cnt++;
            
            for (direction = 0; direction < 4; direction++)
            {
                t = s;
                v = t.v + dx[direction]; w = t.w + dy[direction];
                
                if (srcMatrix[v][w] != '*')
                {
                    char c = t.matrix[t.v][t.w];
                    t.matrix[t.v][t.w] = t.matrix[v][w];
                    t.matrix[v][w] = c;
                   
                    t.v = v;
                    t.w = w;
                    t.pre = cnt;
                    t.f = s.f + 1;
                    t.g = getG(t);
                    t.isVisited = false;
                   
                    int h = 0;
                    for (; h < queue->tail; h++)
                    {
                        if (matrixCmp(queue->data[h].matrix, t.matrix))
                        {
                            break;
                        }
                    }
                   
                    if (h == queue->tail)
                    {
                        putQueue(t);
                        
                        if (matrixCmp(t.matrix, dstMatrix))
                        {
                            pushStack(t);
                            
                            for (int father = t.pre; !matrixCmp(queue->data[father].matrix, srcMatrix); father = queue->data[father].pre)
                            {
                                pushStack(queue->data[father]);
                            }
                            
                            puts("PathFind = ");
                            
                            matrixCpy(t.matrix, srcMatrix);
                            pushStack(t);
                            
                            while (!isStackEmpty())
                            {
                                s = popStack();
                                matrixPrint(s.matrix);
                            }
                            
                            return true;
                        }
                    }
                }
            }
        }
       
        return false;
    }
    int getG(Matrix matrix)
    {
        int g = 0;
       
        for (int i = 0; i < NUM; i++)
        {
            for (int j = 0; j < NUM; j++)
            {
                if (matrix.matrix[j] != '*' && matrix.matrix[j] != dstMatrix[j])
                {
                    g++;
                }
            }
        }
       
        return g;
    }
    void initQueue(int length)
    {
        queue = malloc(sizeof(BGQueue));
       
        queue->data = malloc(sizeof(Matrix) * length);
        queue->length = 0;
        queue->maxLength = length;
        queue->head = 0;
        queue->tail = 0;
    }
    void putQueue(Matrix matrix)
    {
        queue->data[queue->tail++] = matrix;
        queue->tail = queue->tail % queue->maxLength;
        queue->length++;
       
        Matrix* a = malloc(sizeof(Matrix) * queue->maxLength);
        Matrix* b = malloc(sizeof(Matrix) * queue->maxLength);
       
        int an = 0;
        int bn = 0;
       
        for (int i = 0; i < queue->length; i++)
        {
            if (queue->data.isVisited)
            {
                a[an++] = queue->data;
            }
            else
            {
                b[bn++] = queue->data;
            }
        }
        for (int i = 0; i < bn-1; i++)
        {
            for (int j = bn-1; j > i; j--)
            {
                int h1 = b[j-1].f + b[j-1].g;
                int h2 = b[j].f + b[j].g;
                
                if (h1 > h2)
                {
                    Matrix t = b[j-1];
                    b[j-1] = b[j];
                    b[j] = t;
                }
            }
        }
       
        for (int i = 0; i < an; i++)
        {
            queue->data = a;
        }
       
        for (int i = 0; i < bn; i++)
        {
            queue->data[an+i] = b;
        }
        free(a);
        free(b);
    }
    Matrix getQueue(void)
    {
        queue->data[queue->head].isVisited = true;
       
        Matrix ret;
        ret = queue->data[queue->head++];
        queue->head = queue->head % queue->maxLength;
       
        return ret;
    }
    int isQueueEmpty(void)
    {
        return queue->head == queue->tail;
    }
    int isQueueFull(void)
    {
        return ((queue->tail+1) % queue->maxLength) == queue->head;
    }
    void initStack(int length)
    {
        stack = malloc(sizeof(BGStack));
       
        stack->data = malloc(sizeof(Matrix) * length);
        stack->top = 0;
       
    }
    void pushStack(Matrix matrix)
    {
        stack->data[stack->top++] = matrix;
    }
    Matrix popStack(void)
    {
        Matrix ret;
        ret = stack->data[--stack->top];
       
        return ret;
    }
    int isStackEmpty(void)
    {
        return (stack->top == 0);
    }
    int matrixCmp(char src[][NUM], char dst[][NUM])
    {
        int i, j, s, t, ret;
       
        char srcString[30] = {0};
        char dstString[30] = {0};
       
        s = 0;
        t = 0;
       
        for (i = 0; i < NUM; i++)
        {
            for (j = 0; j < NUM; j++)
            {
                srcString[s++] = src[j];
                dstString[t++] = dst[j];
            }
        }
       
        ret = !strcmp(srcString, dstString);
       
        return ret;
    }

    void matrixCpy(char dst[][NUM], char src[][NUM])
    {
        int i, j;
       
        for (i = 0; i < NUM; i++)
        {
            for (j = 0; j < NUM; j++)
            {
                dst[j] = src[j];
            }
        }
    }
    void matrixPrint(char matrix[][NUM])
    {
        char s[60] = {0};
       
        int i, j, k;
       
        k = 0;
       
        for (i = 0; i < NUM; i++)
        {
            for (j = 0; j < NUM; j++)
            {
                s[k++] = matrix[j];
            }
            
            s[k++] = 'r';
            s[k++] = 'n';
        }
       
        s[k++] = 'r';
        s[k++] = 'n';
       
        puts(s);
       
    }

    PathFind =
    *****
    *283*
    *164*
    *705*
    *****

    *****
    *283*
    *104*
    *765*
    *****

    *****
    *203*
    *184*
    *765*
    *****

    *****
    *023*
    *184*
    *765*
    *****

    *****
    *123*
    *084*
    *765*
    *****

    *****
    *123*
    *804*
    *765*
    *****
复制代码

网页游戏私服论坛 http://www.c14.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|网页私服论坛  

GMT+8, 2017-9-20 20:56 , Processed in 0.072862 second(s), 31 queries .

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表