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

实验一 A*算法实现八数码搜索问题
题目:编程实现8数码问题
初始状态:
3
8
2
1
5
7
6
4

目标状态:
1
2
3
8
4
7
6
5
要求: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(i