实验1.2 A*算法搜索
一 实验目的
1 加深对各种状态图搜索策略概念的理解；
2 熟悉和掌握A搜索的定义、估价函数和算法过程；
3 理解和掌握A搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；
4 通过实验掌握估价函数的计算方法，理解估价函数定义的意义。
**
二 实验内容
以重排九宫问题/八数码问题为例，以A搜索算法求解给定初始状态和目标状态的最优搜索路径。
*
三 实验要求
1 自己定义估价函数,能正确求解出从初始状态到目标状态的移动路线； 2 要求界面显示初始状态、目标状态和中间搜索步骤； 3 对不可达状态能进行正确识别；
4 对所采用的估价函数做出性能分析，分析g(n)和h(n)的主要作用是什么，以及不同取值的实验效果，并进行分析。
四 实验背景知识
A算法和A算法是图搜索的两种典型的启发式搜索算法。 1 A算法
A算法是在图搜索算法中的树式搜索算法中增加了估价函数f(x)的一种启发式搜索算法。估价函数的一般形式为：
f(x)＝g(x)＋h(x)
其中g(x)为从初始节点S0到节点x已经付出的代价，h(x)是启发函数，表示估计搜索树上节点x与目标节点Sg接近程度。估价函数f(x)是从初始节点S0到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值之总和。 有时估价函数还可以表示为
f(x)＝d(x)＋h(x) 其中d(x)表示节点x的深度。
f(x)中的g(x)或d(x)有利于搜索的横向发展，h(x)则有利于搜索的纵向发展，因而可提高搜索的效率和搜索的完备性。但在确定f(x)时，要权衡利弊，使g(x)（或d(x)）与h(x)的比重适当，这样才能取得理想的效果。 2 A算法
对A算法限制其估价函数中的启发函数h(x)，使其满足：对所有的节点x均有： h(x)≤h*(x)
9
*
*
其中h*(x)是从节点x到目标节点的最小代价(若有多个目标节点则为其中最小的一个)，则
*
它就称为A算法。
A算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点x的估价函数值为两个分量：从起始节点到节点x的代价以及从节点x到达目标节点的代价。 3 估价函数示例
f(x)?g(x)?h(x)，其中g(x)为初始节点到达当前节点的所花步数，h(x)为当前节点到目标节点的曼哈顿距离。估计函数为到达当前节点步数和Manhattan距离之和，由相关
**h(x)h(x)?h(x)h资料得Manhattan距离满足，其中(x)是当前节点到达目标节点的最小
*
代价，所以此估价函数对应为A算法。
可以用反证法来证明上述估计函数满足A*算法要求。若存在最佳路径且长度为L1，a为最佳路径上的任意一节点，假设A*没有得出最优解，其求出路径长度为L2>L1，b为其求解路径上的终结点。因为估价函数f(n)=step+h(n),h(n)<=n（n为到目标的实际路径）。所以f(a)<=L1,f(b)=L2,推出f(a) * 五 实验关键技术 下面给出A算法的具体步骤： 步1 把附有f(S0)的初始节点S0放入OPEN表； 步2 若OPEN表为空，则搜索失败，退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n； 步4 若目标节点Sg=N，则搜索成功，结束。 步5 若N不可扩展，则转步2； 步6 扩展N，生成一组附有f(x)的子节点，对这组子节点作如下处理： （1）考察是否有已在OPEN表或CLOSED表中存在的节点；若有则再考察其中有无N的先辈节点，若有则删除之；对于其余节点，也删除之，但由于它们又被第二次生成，因而需考虑是否修改已经存在于OPEN表或CLOSE表中的这些节点及其后裔的返回指针和f(x)值，修改原则是“抄f(x)值小的路走”； （2）对其余子节点配上指向N的返回指针后放入OPEN表中，并对OPEN表按f(x)值以升序排序，转步2。 六 实验检查要求 1 界面显示要求： （1）包含初始状态和目标状态的显示，可由指导老师随机输入状态进行检查； （2）每次搜索过程的步骤，不要求树型结构，只要求（动画）表现，每走一步的状态 10 变化； （3）每走一次搜索步，需要有步数的累积显示； （4）最后有完成一次搜索完毕的结果显示。 2 代码要求 检查时要求提供源代码。 3 讲解要求 要求学生讲解自己设计代码的构架，如何实现的（包含使用了何种数据结构，open表和close表的结构等）；要求学生说明自己所使用的估价函数，以及程序运行效果。 4 回答辅导老师提出的问题。 5 提交实验报告（课后把实验报告和源代码在规定的时间内提交到指定邮箱里）。 11 实验1.3 其他应用问题 一 迷宫问题 走迷宫是人们熟悉的一种游戏，如下图就是一个迷宫。如果我们把该迷宫的每一个格 子以及入口和出口都作为节点，把通道作为边，则该迷宫可以由一个有向图表示(如图4所示)。那么，走迷宫其实就是从该有向图的初始节点S0(入口)出发，寻找目标节点Sg(出口)的问题，或者是寻找通向目标节点(出口)的路径的问题。 S1S2S3 S4S5S6S0 S7S8S9 图4 迷宫图 请用图搜索算法进行求解。 Sg二 八皇后问题 八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8?8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。 请用图搜索算法进行求解。 三 一字棋游戏 设有一个三行三列的棋盘，两个棋手A，B轮流走步，每个棋手走步时往空格上摆一个自 己的棋子，谁先使自己的棋子成三子一线为赢。 初始棋盘 各走一步后棋盘 图5 一字棋 设A的棋子用“a”表示，B的棋子用“b”表示。为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下： 设棋局为P，估价函数为e(P)。 (1)若P是A必胜的棋局，则e(P)=+∞。 (2)若P是B必胜的棋局，则e(P)=-∞。 (3)若P是胜负未定的棋局，则e(P)=e(+P)-e(-P) 其中e(+P)表示棋局P上有可能使a成为三子成一线的数目；e(-P)表示棋局P上有可能使b成为三子成一线的数目。例如，对于上图所示的棋局，则 12 e(P)=6-4=2 另外，我们假定具有对称性的两个棋局算作一个棋局。还假定A先走棋，我们站在A的立场上。下图给出了A的第一着走棋生成的博弈树。图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出，对于A来说最好的一着棋是S3，因为S3比S1和S2有较大的倒推值。 图6 一字棋极小极大搜索 请用图搜索算法进行求解，并要求应用α-β剪枝技术。 13