A*算法八数码问题
八数码问题描述
八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中，这里空格用数字0代替。给定九宫格的初始状态重点内容，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)并打印出求解路径及求解的扩展节点。
A*算法
（1）A*算法；是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。A*算法对A算法中的g(n)和h(n)分别提出如下限制：第一，g(n)是对最小代价g*(n)的估计，且g(n)>0；第二，h(n)是最小代价h*(n)的下界，即对任意节点n 均有h(n)≤h*(n)。即满足上述两条限制的A算法称为A*算法。 （2）估价函数；用来估算节点希望程度的量度，叫估价函数f(x)，f(x)=g(x)+h(x)。g(x)为从初始节点到当前节点已经付出的代价，h(x)为从当前节点到目标节点的最优路径的估计代价。本算法中令g(x)为当前节点的深度depth； h(x)为当前节点每个数字位与目标节点数字位间距离和distance，进一步考虑当前结点与目标结点的距离信息，可以令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径），满足h ( n ) <= h * ( n )， 且对于目标节点有 h ( t ) = 0，对于结点m和n （n 是m的子结点） 有h ( m ) – h ( n ) <= 1满足单调限制条件；也可以考虑令启发函数h ( n )为放错棋子移到目标位置的距离的总和；当然也可以如A算法令启发函数h ( n )为放错棋子的数目； 在这里使用的启发函数h ( n )为w ( n ) +3*d ( n )，w ( n )为放错棋子的数目， d ( n )为放错棋子移到目标位置的距离的总和； （3）open和closed表的数据结构表示；对open表的操作，每次需要得到所有待扩展结点中 f 值最小的那个结点。closed表存储已扩展的结点间的扩展关系，主要用于输出路径。closed 表中任意一个结点都存储有它的前驱结点的信息，考虑closed表中任意一个结点，如果它是初始结点，它没有前驱结点，如果不是根结点，扩展该结点时它的前驱结点已经记录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱点的下标位置，可以用数组实现。每个结点记录８数码格局和它的前驱结点的下标。
算法分析
把S放入open表，记f = h，令closed为空表；loop:直至找到目标节点为止。若open表为空，则失败；选取open表中（未设置过的）具有最小f的节点为最佳节点bes，并把它放入closed表；若bes为一目标节点，则成功求得一解；若bes不是目标节点，则扩展之，产生后继节点suc；对每个后继节点suc，进行下列过程： a. 建立从后继节点suc返回最佳节点bes的指针； b. 计算g（suc） = g（bes） + g(bes,suc); c. 若后继节点suc在open表或clsoed表中，则称此节点为old，并把它添加至最佳节点bes的后继节点表中，比较新旧路径代价： 1） 若g（suc）小于g(old),则重新确定old的父辈节点为bes节点，记下较小代价 g（old），并修正f（old）值。转7； 2） 若至old节点的代价较低或一样，则停止可扩展节点；转7；计算f的值；Go loop
源程序 程序是用C实该程序实现了A*算法寻找最优的路径，并且把所有的扩展节点给打印出来，打印扩展节点时，运行程序得到的结果中从上至下，第一大列对应的便是解决方案的路径，同时也是父节点与子节点之间的关系， Step n 这一代的所有节点对应的父节点都是Step n-1 代节点中最左边的那个节点 棋子目标状态： 1 2 3 8 0 4 7 6 5
程序实现如下 ：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
struct node
{
int start[
3][
3];
int f;
int g;
int h;
int x;
int y;
struct node * father;
struct node * next;
};
static int target[
3][
3] = {
1,
2,
3,
8,
0,
4,
7,
6,
5 };
static int sum_num =
0;
static int same[
100];
int gets_h(node*s);
int same_node(node*a, node*b);
node*In_list(node*L, node*n);
void zero_place(node*s)
{
int i, j;
for (i =
0; i <
3; i++)
{
for (j =
0; j <
3; j++)
{
if (s->start[i][j] ==
0)
{
s->x = i;
s->y = j;
return;
}
}
}
}
void _input(node* s)
{
int i, j;
printf(
"测试情况：输入\n\n");
printf(
"****2 8 3****\n");
printf(
"****1 6 4****\n");
printf(
"****7 0 5****\n\n");
printf(
"请输入初始位置：(3*3)\n");
for (i =
0; i <
3; i++)
{
for (j =
0; j <
3; j++)
{
scanf(
"%d", &s->start[i][j]);
}
printf(
"\n");
}
s->g =
0;
s->h = gets_h(s);
s->f = s->g + s->h;
zero_place(s);
s->next =
NULL;
s->father =
NULL;
return;
}
void _print(node*best, node*all)
{
int i;
int j;
int k;
int length =
0;
for (i =
0; i <
100; i++)
{
if (same[i] !=
0)
{
length++;
}
}
node *s[
400];
node *ss[
400];
node *child;
node *other;
child = best;
other = all;
for (i =
0; i <
400; i++)
{
s[i] =
NULL;
ss[i] =
NULL;
}
int depth = child->g;
for (i = depth; i >=
0; i--)
{
s[i] = child;
child = child->next;
}
for (i = length; i >
0; i--)
{
ss[i -
1] = other;
other = other->next;
}
printf(
"扩展%d层\n", depth);
int m;
for (k =
0; k <= depth; k++)
{
printf(
"Step %d\n", k);
for (i =
0; i <
3; i++)
{
for (j =
0; j <
3; j++)
{
printf(
"%d\t", s[k]->start[i][j]);
}
for (m =
0; m < length; m++)
{
if (k == same[m] && k !=
0)
{
printf(
"\t");
for (j =
0; j <
3; j++)
{
printf(
"%d\t", ss[m]->start[i][j]);
}
}
}
printf(
"\n");
}
}
}
int gets_h(node *s)
{
int i;
int j;
int k =
0;
int value =
0;
for (i =
0; i <
3; i++)
{
for (j =
0; j <
3; j++)
{
if (s->start[i][j] != target[i][j] && s->start[i][j] !=
0)
{
value++;
}
}
}
k = value;
value =
0;
int a[
8][
2], b[
8][
2];
for (i =
0; i <
3; i++)
{
for (j =
0; j <
3; j++)
{
if (s->start[i][j] !=
0)
{
a[s->start[i][j] -
1][
0] = i;
a[s->start[i][j] -
1][
1] = j;
}
if (target[i][j] !=
0)
{
b[target[i][j] -
1][
0] = i;
b[target[i][j] -
1][
1] = j;
}
}
}
for (i =
0; i <
8; i++)
{
for (j =
0; j <
2; j++)
{
value = value + abs(a[i][j] - b[i][j]);
}
}
value = (value *
3 + k);
return value;
}
void list_insert(node* &List, node *n)
{
if (List ==
NULL)
{
n->next =
NULL;
List = n;
}
else
{
n->next = List;
List = n;
}
return;
}
void list_remove(node* &L, node*n)
{
struct node *p, *q;
p =
NULL, q =
NULL;
if (L ==
NULL)
{
return;
}
else if (same_node(L, n) && L->f == n->f)
{
L = L->next;
L->next =
NULL;
return;
}
else
{
p = L;
q = p->next;
while (q)
{
if (same_node(q, n) && q->f == n->f)
{
p->next = q->next;
return;
}
else
{
p = q;
q = q->next;
}
}
return;
}
}
void getmin(node* &L, node*p)
{
struct node *p1, *p2;
p1 = L;
p2 =
NULL;
if (L ==
NULL)
{
p->next =
NULL;
L = p;
}
else
{
while (p1 !=
NULL&&p->f > p1->f)
{
p2 = p1;
p1 = p1->next;
}
if (p2 ==
NULL)
{
p->next = L;
L = p;
}
else if (p1 ==
NULL)
{
p->next =
NULL;
p2->next = p;
}
else
{
p2->next = p;
p->next = p1;
}
}
}
void search(node *L, node * &all)
{
int i;
node *s2;
node *s1[
4];
if (L !=
NULL)
{
for (i =
0; i <
4; i++)
{
s1[i] =
NULL;
}
s2 = L;
for (i =
0; i <
4 && s2 !=
NULL; i++)
{
s1[i] = s2;
s2 = s2->next;
}
sum_num++;
for (i =
1; i <
4 && s1[i] !=
NULL; i++)
{
if (s1[
0]->h == s1[i]->h)
{
sum_num++;
same[sum_num - s1[
0]->g -
1] = s1[
0]->g;
list_insert(all, s1[i]);
}
}
}
return;
}
void get_node(node* &open, node* close, node *bestnode,
int deep,
int move,
int &sumnode)
{
struct node *newnode, *f_node, *old, *ls;
old =
NULL;
ls =
NULL;
newnode =
NULL;
newnode = (
struct node*)malloc(
sizeof(
struct node));
f_node = bestnode->father;
if (f_node !=
NULL&&f_node->x == bestnode->x&&f_node->y == bestnode->y)
{
;
}
else
{
int i, j;
for (i =
0; i <
3; i++)
{
for (j =
0; j <
3; j++)
{
newnode->start[i][j] = bestnode->start[i][j];
}
}
newnode->x = bestnode->x;
newnode->y = bestnode->y;
newnode->next = bestnode->next;
newnode->father = bestnode->father;
switch (move)
{
case 1:
newnode->start[newnode->x][newnode->y] = newnode->start[newnode->x][newnode->y -
1];
newnode->start[newnode->x][newnode->y -
1] =
0;
newnode->y = newnode->y -
1;
break;
case 2:
newnode->start[newnode->x][newnode->y] = newnode->start[newnode->x][newnode->y +
1];
newnode->start[newnode->x][newnode->y +
1] =
0;
newnode->y = newnode->y +
1;
break;
case 3:
newnode->start[newnode->x][newnode->y] = newnode->start[newnode->x -
1][newnode->y];
newnode->start[newnode->x -
1][newnode->y] =
0;
newnode->x = newnode->x -
1;
break;
case 4:
newnode->start[newnode->x][newnode->y] = newnode->start[newnode->x +
1][newnode->y];
newnode->start[newnode->x +
1][newnode->y] =
0;
newnode->x = newnode->x +
1;
break;
default:
break;
}
newnode->g = deep +
1;
newnode->h = gets_h(newnode);
newnode->f = newnode->g + newnode->h;
newnode->father = bestnode;
ls = newnode;
ls->father =
NULL;
ls->next =
NULL;
if (old = In_list(open, newnode))
{
if (newnode->g < old->g)
{
list_remove(open, old);
getmin(open, ls);
sumnode++;
}
}
else if (old = In_list(close, newnode))
{
if (newnode->g < old->g)
{
list_remove(close, old);
getmin(open, ls);
sumnode++;
}
}
else
{
getmin(open, ls);
sumnode++;
}
}
}
int same_node(node*a, node*b)
{
int i, j;
int flag =
1;
for (i =
0; i <
3; i++)
{
for (j =
0; j <
3; j++)
{
if (a->start[i][j] != b->start[i][j])
{
flag =
0;
return flag;
}
}
}
return flag;
}
node * In_list(node*L, node*n)
{
struct node*temp;
struct node *ls;
ls =
NULL;
temp = L;
while (temp !=
NULL)
{
if (same_node(n, temp))
{
ls = temp;
break;
}
else
{
temp = temp->next;
}
}
return ls;
}
void main()
{
for (
int i =
0; i <
100; i++)
{
same[i] =
0;
}
int result =
0;
int sunnode =
0;
struct node* open =
NULL;
struct node* close =
NULL;
struct node s;
struct node *bestnode;
struct node *best;
best =
NULL;
struct node *current;
struct node *a;
a =
NULL;
struct node *all;
all =
NULL;
_input(&s);
list_insert(open, &s);
while (open !=
NULL)
{
bestnode = open;
a = bestnode;
a->next =
NULL;
current = open->next;
list_insert(close, a);
list_insert(best, a);
open = current;
if (bestnode->h ==
0)
{
result =
1;
printf(
"寻找成功\n");
break;
}
else
{
if (bestnode->y >=
1)
{
get_node(open, close, bestnode, bestnode->g,
1, sunnode);
}
if (bestnode->y <=
1)
{
get_node(open, close, bestnode, bestnode->g,
2, sunnode);
}
if (bestnode->x >=
1)
{
get_node(open, close, bestnode, bestnode->g,
3, sunnode);
}
if (bestnode->x <=
1)
{
get_node(open, close, bestnode, bestnode->g,
4, sunnode);
}
search(open, all);
}
}
if (result ==
1)
{
_print(best, all);
printf(
"搜索过的叶子节点：%d\n", sunnode);
printf(
"扩展节点数目：%d\n", sum_num);
}
else
{
printf(
"没达到目标\n");
}
}
测试结果1： -初始状态： 2 8 3 1 6 4 7 0 5 运行； 测试情况：输入
*2 8 3* *1 6 4* *7 0 5*
请输入初始位置：(3*3) 2 8 3
1 6 4
7 0 5
寻找成功 扩展5层 Step 0 2 8 3 1 6 4 7 0 5 Step 1 2 8 3 1 0 4 7 6 5 Step 2 2 0 3 1 8 4 7 6 5 Step 3 0 2 3 1 8 4 7 6 5 Step 4 1 2 3 0 8 4 7 6 5 Step 5 1 2 3 8 0 4 7 6 5 搜索过的叶子节点：11 扩展节点数目：5 请按任意键继续… - 测试结果2： -初始状态： 0 3 4 5 1 6 7 8 2 运行； 测试情况：输入
*2 8 3* *1 6 4* *7 0 5*
请输入初始位置：(3*3) 0 3 4
5 1 6
7 8 2
寻找成功 扩展56层 Step 0 0 3 4 5 1 6 7 8 2 Step 1 5 3 4 3 0 4 0 1 6 5 1 6 7 8 2 7 8 2 Step 2 5 3 4 1 0 6 7 8 2 Step 3 5 3 4 5 3 4 1 8 6 1 6 0 7 0 2 7 8 2 Step 4 5 3 4 1 8 6 7 2 0 Step 5 5 3 4 1 8 0 7 2 6 …… …… …… Step 51 1 0 3 8 2 6 7 5 4 Step 52 1 2 3 8 0 6 7 5 4 Step 53 1 2 3 8 6 0 7 5 4 Step 54 1 2 3 8 6 4 7 5 0 Step 55 1 2 3 8 6 4 7 0 5 Step 56 1 2 3 8 0 4 7 6 5 搜索过的叶子节点：105 扩展节点数目：66 请按任意键继续. . . 以上程序也是刚学人工智能A*算法写的，有不对的地方我们共同交流；
