用A*搜索解决八数码拼图游戏

1.实验目的

通过本实验理解并掌握A*搜索的基本思路和编程实现，体会在实际问题中设计代价函数g（n）、启发函数h（n）、评估函数f（n）的方法，加深理解启发函数的信息度对搜索过程的影响。

2.实验内容

使用Python设计程序实现A*搜索算法，并用其实现八数码拼图游戏。

实验参考代码说明：

（1）安装Pygame包。

为了使程序界面更友好，本实验参考代码使用了Pygame包。Pygame是为了编写电子游戏设计的一套Python模块。它基于SDL（Simple Direct Media Layer）库添加了很多功能，以便用Python进行游戏以及多媒体程序开发。SDL库是一个跨平台的开发库，它提供了通过OpenGL和Direct3D访问键盘、鼠标、显卡等硬件的底层访问接口。

在Pycharm中安装Pygame包的方法为：选择File菜单下的“Settings…”，在弹出的对话框中找到“Project”部分的Python解释器“Python Interpreter”，如图3.28所示，检查是否已经安装有Pygame包，图中方框处表示已经安装有Pygame包，版本为2.0.1，最新版本也为2.0.1。如果没有发现“pygame”，则表示还没安装Pygame包，点击左下角的“+”号，在接着弹出的窗口中显示了所有可以获得的安装包，找到Pygame，选定版本号，点击安装按钮即可，如图3.29所示。

图3.28　在Pycharm中安装Pygame包

(www.xing528.com)

图3.29　在Pycharm中查找并安装指定版本的包

同样，也可以在安装了Python环境的命令行中，通过输入“pip install pygame==2.0.1”或“pip3 install pygame==2.0.1”进行安装，pip3一般对应Python 3版本。

Pygame官方参考文档提供了较详细的教程，网址为：https：//www.pygame.org/docs/。这里只对参考代码用到的部分做简要介绍。

（2）参考代码分析。

参考代码中Py8Puzzle.py实现了A*搜索算法，可供其他模块调用。

Py8Puzzle.py中使用了math和random库。首先定义了一个puzzle类，它包含初始状态Start Node和目标状态Goal Node两个列表。在Start Node中存放将要放置的一个初始状态，0代表空格所在位置。为了和第2章中的内容一致，参考程序也通过采用列表模拟二维矩阵来表示9个格子组成的不同状态。

Py8Puzzle.py中使用了一个简单的启发信息。可以尝试用不同的启发信息，看看对搜索性能的影响。比如，对比一下完全不用启发信息和用信息度更高的启发信息时，找到解的速度情况。另外，请参考例3.3设计出评估函数，构成真正意义上的A*搜索。

程序代码中附上了详细的注释，请注意阅读。另外，还可以使用集合set来代替列表，避免重复元素。

调试时需要注意，存在某些初始状态无法到达的目标状态。

MyPuzzle.py借助Pygame，使用图形化界面模仿了移动过程，它会首先按照初始状态，显示8个数字及空格的位置，然后在窗口内任意地方点击后，程序将自动完成解答。空格通过将方格的背景色设置为黑色来体现。

Puzzle Test.py是为了测试程序性能而设计的，可以统计访问的状态节点数，还可以通过自行添加记录时间的代码来测试算法执行时间。