八数码问题实验报告c语言,八数码问题C语言A星算法详细实验报告含代码.pdf

一、实验内容和要求

八数码问题：在 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 必须小于等于实际的从当前节点到达

目标节点的最小耗费 h(n)<=h'(n) 。第二点特别的重要。可以证明应用这样的估

价函数是可以找到最短路径的。

3.A* 算法的步骤

A* 算法基本上与广度优先算法相同， 但是在扩展出一个结点后， 要计算它的估价

函数，并根据估价函数对待扩展的结点排序， 从而保证每次扩展的结点都是估价

函数最小的结点。

A* 算法的步骤如下：

1)建立一个队列，计算初始结点的估价函数 f ，并将初始结点入队，设置队列

头和尾指针。

2 )取出队列头(队列头指针所指)的结点，如果该结点是目标结点，则输出路

径，程序结束。否则对结点进行扩展。

3 )检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复

(位于队列头指针之前)，则将它抛弃；若新结点与待扩展的结点重复(位于队

列头指针之后)，则比较两个结点的估价函数中 g 的大小，保留较小 g 值的结点。

跳至第五步。

4 )如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数 f