- -
一、实验内容和要求
八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格
是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格
上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
例如:
2 8 3 1 2 3
1 6 4 8 4
7 0 5 7 6 5
(a) 初始状态 (b) 目标状态
图 1 八数码问题示意图
请任选一种盲目搜索算法〔广度优先搜索或深度优先搜索〕或任选一种启
发式搜索方法〔全局择优搜索,加权状态图搜索,A 算法或A* 算法〕编程求解
八数码问题〔初始状态任选〕。选择一个初始状态,画出搜索树,填写相应的
OPEN表和CLOSED表,给出解路径,对实验结果进展分析总结,得出结论。
二、实验目的
1. 熟悉人工智能系统中的问题求解过程;
2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用;
3. 熟悉对八数码问题的建模、求解及编程语言的应用。
三、实验算法
A*算法是一种常用的启发式搜索算法。
在 A*算法中,一个结点位置的好坏用估价函数来对它进展评估。A*算法的估价
函数可表示为:
f'(n) = g'(n) + h'(n)
这里,f'(n)是估价函数,g'(n)是起点到终点的最短路径值〔也称为最小消耗或
最小代价〕,h'(n)是 n 到目标的最短路经的启发值。由于这个 f'(n)其实是无法
预先知道的,所以实际上使用的是下面的估价函数:
f(n) = g(n) + h(n)
其中 g(n)是从初始结点到节点 n 的实际代价,h(n)是从结点 n 到目标结点的最
正确路径的估计代价。在这里主要是 h(n)表达了搜索的启发信息,因为 g(n)是
的。用 f(n)作为 f'(n)的近似,也就是用 g(n)代替 g'(n),h(n)代替 h'(n)。这样
必须满足两个条件:〔1〕g(n)>=g'(n)〔大多数情况下都是满足的,可以不
用考虑〕,且 f 必须保持单调递增。〔2〕h 必须小于等于实际的从当前节点到
- word.zl-