《人工智能》--八数码问题求解.doc
需积分: 9 65 浏览量
2021-06-14
16:12:21
上传
评论
收藏 80KB DOC 举报
基于 A*算法的八数码问题求解
一、实验目的
八数码游戏包括一个 33 的棋盘，棋盘上摆放着 8 个数字的棋子，留下一个空位。与空
位相邻的棋子可以滑动到空位中。游戏的目的是要达到一个特定的目标状态。标注的形式
化如下：<初始状态<<<<<<753
164
280
目标状态<<<<<<<<<<<<<<<<123
804
765
搜索形式描述
状态：<<<<<<<<状态描述了 8 个棋子和空位在棋盘的 9 个方格上的分布。
初始状态：<<<<任何状态都可以被指定为初始状态。
操作符：<<<<<<用来产生 4 个行动（上下左右移动）。
目标测试：<<<<用来检测状态是否能匹配上图的目标布局。
路径费用函数：每一步的费用为 1，因此整个路径的费用是路径中的步数。
现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标
状态。
在 A*算法中，启发性信息用一个特别的估价函数 f*来表示：
f*(n)=g*(n)+h*(n)
式中：
g*(n)为从初始节点到节点 n 的最佳路径所付出的代价；
h*(n)是从 n 到目标节点的最佳路径所付出的代价；
f*(n)是从初始节点出发通过节点 n 到达目标节点的最佳路径的总代价。
（在这里要特别说明前面所说的 f(n)=g(n)+h(n)未带<<*为评估代价而非一定是最优代价）
基于上述 g*(n)和 h*(n)的定义，对启发式搜索算法中的 g(n)和 h(n)做如下限制：
①g(n)是对 g*(n)的估计，且 g(n)>0；
剩余13页未读，继续阅读
评论0