人工智能A算法九宫格报告.doc

文档介绍：人工智能A算法九宫格报告
题目:编程实现8数码问题
初始状态:
目标状态:
要求:1、报告:给出状态表示,编码规则,搜索算法A*,简单程序说明,最优路径。
2、调通的程序(语言不限)
一、状态表示
用一个3×3的数组来表示状态,数组中的各个元素对应状态位置的数字。其中空格用0表示。
二、编码规则
在程序实现过程中,只有移动0的位置,即可生成新的节点。
规则库
设数组中0的位置为a[i][j],其中0≤i≤2,0≤j≤2。
R1:if(i≥1) then 上移
R1:if(i≤1) then 下移
R1:if(j≥1) then 左移
R1:if(j≤1) then 右移
三、搜索算法A*
用于度量节点的“希望”的量度f(n),即用来衡量到达目标节点的路径的可能性大小。 A算法:
基本思想:定义一个评价函数,对当前的搜索状态进行评估,找出一个最有希望的节点进行扩展:f(n) = g(n) + h(n),n为被评价节点
g*(n):从s到n的最优路径的实际代价
h*(n):从n到g的最优路径的实际代价
f*(n)=g*(n)+h*(n):从s经过n到g的最优路径的实际代价
g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值
g (n)通常为从S到到n这段路径的实际代价,则有g (n) ≥ g*(n)
h (n):是从节点n到目标节点Sg的最优路径的估计代价. 它的选择依赖于有关问题领域的启发信息,叫做启发函数
A算法:在图搜索的一般算法中,在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序表中的节点进行排序, 找出一个最有希望的节点作为下一次扩展的节点。
在A算法中,如果满足条件:h(n)≤h*(n),则A算法称为A*算法。
在本算法中,为实现八数码的搜索问题,定义估价函数为:f(n)=g(n)+h(n),
其中g(n)表示节点n在搜索树中的深度;
h(n)表示节点n的各个数码到目标位置的曼哈顿距离和。
四、程序说明
1、算法实现的步骤:
(1)把初始节点S0放入Open表中,置S0的代价g(S0)=0;
(2)如果Open表为空,则问题无解,失败退出;
(3)把 Open表的第一个节点取出放入 Closed表,并记该节点为n
(4)考察节点n是否为目标节点。若是,则找到了问题的解,成功退出;
(5)若节点n不可扩展,则转第(2)步;
(6)扩展节点 n,生成其子节点 ni, (其中i=1,2,3,„„),将这些子节点放入 Open表中,并为每一个子节点设置指向父节点的指针;按公式 g(ni)=g(n)+c(n,ni)(i=1,2,„)计算Open表中的各子节点的代价,并根据各节点的代价对Open表中的全部节点按照从小到大顺序重新进行排序;然后转第(2)步。
2、思路
通过代价函数对Open表中的节点进行排序,代价小的先扩展。
A*算法代码的核心部分
pnode move(pnode p,int dir)
{
pnode Unode=(pnode)malloc(sizeof(node));
for(int i=0;i
{ for(int j=0;j
{
Unode->a[i][j]=p->a[i][j];
}
}
switch(dir)
{
case 1: //up
{
Unode->x=p->x-1;
Unode->y=p->y;
Unode->a[Unode->x][Unode->y]=0;
Unode->a[Unode->x+1][Unode->y]=p->a[Unode->x][Unode->y];
break;
}
case 2:„„„„„„//down
}
Unode->father=p;
Unode->g=p->g+1;//深度增加一层
Unode->h=hvalue(Unode->a,final); //更新h函数值
Unode->f=Unode->h+Unode->g;
return Unode;
}
int main(int argc, char *argv[])
{
pnode A0=(pnode)malloc(sizeof(node));
pnode open, //open表头
close, //close表头
now, //当前节点
Lnode,Rnode,Unode,Dnode, //下一个左,右,上,下节点
fnode; //终节点
initial(A0,start);
open=A0;
close=NULL;
while(1)
{
if(open==NULL) //Open表为空