Eight puzzle.pdf-资料库

qirixi-3202622-16359647661168209005.pdf-第1页.png

第1页 / 共42页

qirixi-3202622-16359647661168209005.pdf-第2页.png

第2页 / 共42页

qirixi-3202622-16359647661168209005.pdf-第3页.png

第3页 / 共42页

qirixi-3202622-16359647661168209005.pdf-第4页.png

第4页 / 共42页

qirixi-3202622-16359647661168209005.pdf-第5页.png

第5页 / 共42页

qirixi-3202622-16359647661168209005.pdf-第6页.png

第6页 / 共42页

qirixi-3202622-16359647661168209005.pdf-第7页.png

第7页 / 共42页

qirixi-3202622-16359647661168209005.pdf-第8页.png

第8页 / 共42页

滑块问题求解系统设计报告班级： 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

滑块问题求解系统——福州大学数学与计算机科学学院 04 级计算机(2)班姜志渊 S030402227 详细见下图：５、横向评测：见菜单－>功能－>横向评测。同时启动所有算法进行评比各项统计结果，见下图： ①、八种算法的比较： 5

滑块问题求解系统——福州大学数学与计算机科学学院 04 级计算机(2)班姜志渊 S030402227 ②、启发函数不同系数下的效果：６、参数设置：见菜单－>功能－>参数设置。可设置自动演示延迟时间，范围 200~2000(ms)；有界深度优先搜索的界限，范围 5~50（步）；两种 A*算法的启发函数 h(x)的系数值，范围为 0~100；（整数）７、切换图片：暂时可供选择图片有：数字、女孩、图标。８、帮助： ①、关于，作者信息。 ②、帮助主题：简要介绍了本系统的用法。三、系统已实现的功能：系统基本参照设计任务书的要求设计。１、本系统使用方法参见第二部分。另外，总共实现了八种算法： ①、简单广度优先搜索，Breadth-first Search ②、双向广度优先搜索，Bidirectional Search ③、简单深度优先搜索，Depth-first Search ④、有界深度优先搜索，Depth-limited Search 6

滑块问题求解系统——福州大学数学与计算机科学学院 04 级计算机(2)班姜志渊 S030402227 ⑤、迭代加深深度优先搜索 Iterative deeping depth-first search ⑥、A star 搜索（启发函数采用所有图片到达目的地的曼哈顿距离之和），A*1 ⑦、A star 搜索（启发函数采用所有不在目标位置的图片数目之和），A*2 ⑧、迭代加深 A*搜索，（启发函数采用所有图片到达目的地的曼哈顿距离之和）， Iterative deeping A star 算法具体说明参见第五部分。２、本系统支持手玩模式，集游戏互动于一身。３、在搜索模式下可列出搜索结果，使得算法优劣性一目了然。４、横向评测可以同时启动所有算法，通过横向评比主要统计因数，使得算法之间的对比更加鲜明。四、算法思想及分析：首先引入几个概念： Ⅰ、假设每个结点都有 b 个后继节点 Ⅱ、解路径深度 d Ⅲ、最深的节点深度 m １、盲目搜索（Uninformed search） BFS 是一种简单的搜索策略。它从根节点开始，按搜索深度逐层扩展结点， ①、简单广度优先搜索，Breadth-first Search 直到找到目标结点为止其搜索顺序如下图所示：该算法可以使用 FIFO 队列实现，初始时将开始结点放入队列中，每次取队头结点，判断是否为终结点，不是则将其所有子结点放入队列尾，直到队列为空或者找到目标结点为止。如果目标结点在深度 d，那么该算法扩展完深度小于 d 的结点后就将找到目标结点。而且，显然这是最优的。容易观察到，在根节点的第一子层有 b 个结点，第二子层有 b2，然后是 b3，以此类推。在最坏情况下，我们将扩展为目标结点前的所有结点，在 d + 1 层扩展 bd+1-b 个，那么将总共扩展： b + b2 + b3 + …… + bd + (bd+1-b) = O(bd+1) 由此可见，该算法的空间要求是相当高的。 7

资料库

Eight puzzle.pdf

相关推荐

课程资源

热门标签

最新资料