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

一、实验内容和要求八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目

. 一、实验内容和要求 八数码问题：在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八数码问题示意图 请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发 AA 式搜索方法（全局择优搜索，加权状态图搜索，算法或*算法）编程求解 八数码问题（）。选择一个初始状态，画出搜索树，填写相应的 初始状态任选 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)（大多数情况下都是满足的，可以不