无题

__BlueGuy__ · 发表于 2015-7-9 10:15:51

八数码问题是指一个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[i][j] != '*' && matrix.matrix[i][j] != dstMatrix[i][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[i].isVisited)
{
a[an++] = queue->data[i];
}
else
{
b[bn++] = queue->data[i];
}
}
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[i] = a[i];
}
for (int i = 0; i < bn; i++)
{
queue->data[an+i] = b[i];
}
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[i][j];
dstString[t++] = dst[i][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[i][j] = src[i][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[i][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*
*****

复制代码

__BlueGuy__ · 发表于 2015-7-9 10:23:16

给个首页推荐推荐吧

账号		自动登录	找回密码
密码			立即注册