滑块问题求解系统
设计报告
班级： 04级计算机（2）班
学生姓名：姜志渊
学号： 030402227
实验时间：2007.3-2007.4
任课老师：陈昭烔
滑块问题求解系统——福州大学数学与计算机科学学院 04 级计算机(2)班 姜志渊 S030402227
目录
一、系统设计任务 ........................................................... 2
二、设计环境及使用说明 ..................................................... 2
1、状态生成 ............................................................ 2
2、手玩模式 ............................................................ 3
3、搜索解决 ............................................................ 3
4、生成状态图 .......................................................... 4
5、横向评测 ............................................................ 5
6、参数设置 ............................................................ 6
7、切换图片 ............................................................ 6
8、帮助 ................................................................ 6
三、系统已实现功能 ......................................................... 6
四、算法思想及分析 ......................................................... 7
1、盲目搜索（Uninformed search） .......................................... 7
①、简单广度优先搜索，Breadth-first Search ............................. 7
②、双向广度优先搜索，Bidirectional Search ............................. 8
③、简单深度优先搜索，Depth-first Search .............................. 9
④、有界深度优先搜索，Depth-limited Search ........................... 10
⑤、迭代加深深度优先搜索，Iterative deeping depth-first search .............. 11
2、启发式搜索（informed search） .......................................... 13
①、贪心搜索，Greedy best-first search ................................... 13
②、A*搜索 ......................................................... 13
③、迭代加深 A*搜索算法(IDA*) ....................................... 14
3、滑块（八数码）系统的分析 ............................................. 15
①、问题分析 ....................................................... 15
②、状态的表示与存储 ............................................... 16
③、八种算法的具体实现 ............................................. 17
类的派生关系 ................................................... 18
搜索公共基类 searher 的实现 ..................................... 18
Ⅰ、广度优先搜索的 search 函数.................................... 19
Ⅱ、双向广度优先搜索的 search 函数................................ 20
Ⅲ、深度优先搜索的 search 函数.................................... 22
Ⅳ、有界深度优先搜索的 search 函数................................ 24
Ⅴ、迭代加深深度优先搜索的 search 函数............................ 25
Ⅵ、A*搜索的 search 函数.......................................... 26
Ⅶ、IDA*搜索的 search 函数 ...................................... 28
五、结果图示及分析 .......................................................... 29
1、简单分析 ............................................................. 29
2、统计分析 ............................................................. 37
六、已知问题报告和进一步改进 ................................................ 40
七、参考文献 ................................................................ 41
1
滑块问题求解系统——福州大学数学与计算机科学学院 04 级计算机(2)班 姜志渊 S030402227
滑块问题求解系统
一、系统设计任务：
以八数码问题为例，设计一类滑块问题的求解系统，初步掌握智能搜索算法中的盲目搜
索和启发式搜索这两类基本方法，同时通过具体的问题体会搜索算法、数据结构、程序设计
等知识的综合应用。
二、设计环境及使用说明：
本系统采用 Visual C++ 7.1 MFC 做界面设计，核心部分（各种搜索算法）采用独立类
封装，同界面程序分开，具有良好的可移植性。
系统使用方法如：
１、状态生成：
①、默认状态，如下图：
②、随机状态,可选择是否随机初始状态、结束状态，以及是否避免生成无解状态。
如下图：
③、手动设置，图片下方的复选框用来标明此图是否已在初始状态（前）或结束状
态（后）中被选中，下方的数字用来在切换为其它非数字图片时标明图片的序
号值。设置方法为点击图片按钮，再在状态框里的具体位置单击，即可将图片
放置其上，也可以在状态框中互换两个图片的位置，具体如下图：
2
滑块问题求解系统——福州大学数学与计算机科学学院 04 级计算机(2)班 姜志渊 S030402227
２、手玩模式：
①、必须选中“手玩模式”复选框才可以进入手玩模式，否则点击图片时，将会交
换两图片的位置（这是为了设置状态而用），在选中“手玩模式”之前，需要先设
置好状态。进入手玩模式后将丢失先前搜索信息！
②、移动图片时只需要单击空图旁边的图片，即可让图片向空图位置移动，如果想
退回上一步，单击“上一步”按钮即可，相应地，也有“下一步”按钮，也可以选
择恢复初始状态。移动时将指出当前所用的步数。如下图：
３、搜索解决：
①、本系统提供八种算法（见后面算法说明）以供选择，如下图：
②、单击“详细>>”按钮，可以观察算法说明以及搜索结果，如下图：
3
滑块问题求解系统——福州大学数学与计算机科学学院 04 级计算机(2)班 姜志渊 S030402227
③、单击“开始搜索”按钮开始利用计算机找寻答案。因为本系统采用多线程编写，
如果算法所用时间过长，也可以中途停止搜索（在搜索时，按钮将变为“停止
搜索”），搜索将有可能出现以下几种结果：
Ⅰ、无解：
Ⅱ、有解但是因为算法限制而找不到解：
Ⅲ、成功找到解答，搜索结果框中出现统计结果，此时自动演示按钮将变为有
效状态（见演示功能）。
④、演示功能：
在成功找到解决方案时，即可演示解答过程。
Ⅰ、手动，单击“上一步”、“下一步”按钮逐步观察，如下图：
Ⅱ、自动演示，如以让计算机自动逐步演示答案，可以选择演示延迟时间（见
参数设置），按钮如下图：
⑤、必须在未选中手玩模式才有效。
４、生成状态图：
见菜单－>功能－>生成状态图，初始状态时，该按钮无效。
在手动模式下成功到达目标或者利用算法成功搜索到解决方案时，该按钮将变成有
效，点击可以观察状态的变化过程，其中状态表示方式如下：
2 3
1 4 5 ===========> 876541320
6 7 8
4
