目录
一、实验概述 3
(1) 实验目的 3
(2) 实验内容 3
二、实验方案设计 3
(1) 总体设计思路与总体架构 3
3. 流程图：（见下页） 3
(2) 核心算法及基本原理 4
(3) 模块设计 5
(4) 其它创新内容或优化算法 8
15 数码问题也能通过简单的修改宏定义来整体适应。 9
三、实验过程 9
(1) 环境说明 9
(2) 源文件代码清单、主要函数清单 9
8Puzzle_UI.h： 9
8Puzzle.h： 10
(3) 实验结果展示 13
(4) 实验结论 16
四、总结 16
(1) 实验中存在的问题及解决方案 16
(2) 心得体会 17
(3) 后续改进方向 17
(4) 总结 18
五、参考文献 18
六、成员分工与自评 18
1. 成员分工： 18
2. 成员自评： 18
3. 总体评价与收获 19
一、实验概述
(1)实验目的
熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用 A*算法求解 8 数码难题，理解求解流程和搜索顺序。
(2)实验内容
1.采用 C++语言实现 A*算法的求解八数码问题的程序，设计了两种不同的估价函数： 第一种：计算不在位的棋子数；第二种：计算所有棋子到其目标的距离和。
2.设置相同初始状态和目标状态，针对两种的估价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、生成节点数和运行时间。画出不同启发函数 h(n)求解 8 数码问题的结果比较表，进行性能分析。
3.通过 UI 界面显示八数码问题的初始状态，目标状态和中间搜索步骤。
4.画出搜索生成的树，在每个节点显示对应节点的 f (n)值，以显示搜索过程。以红色标注出最终结果所选用的路线。
二、实验方案设计
(1)总体设计思路与总体架构
1.总体设计思路：程序从设计上分为两个部分：算法实现部分和图形显示部分。两部分相互独立，仅通过函数进行数值传递或者指针传递的方式进行关联。当算法部分运行完成后，会得到关于一个八数码问题的最优路径解、搜索树以及求解过程中产生的例如生成结点数、扩展结点数的信息，将这些信息以数值、指针、字符串等形式传值至图形显示部分。
2.总体架构：总体架构设计基于上述的设计思路。程序代码具体分为：算法实现部分、八数码九宫格绘制部分、搜索树绘制部分三份代码。每份代码具有独立的数据结构定义及相关功能实现过程，通过 main()函数进行主算法的调用、参数传递，并在主算法中对图形界面绘制函数进行调用和传参。
