1、 滑块问题求解系统报告一、 设计任务 ：以八数码问题为例，设计一类滑块问题的求解系统，初步掌握智能搜索算法中的盲目搜索和启发式搜索这两类基本方法，同时通过具体的问题体会搜索算法、数据结构、程序设计等知识的综合应用。图 1 8 数码问题示意图二 设计环境及使用说明操作系统 : Windows Xp开发平台 : eclipse开发语言： java三 系统已实现的功能a)状态设置栏：（如图）（ 1） 默认终态：本程序默认终态为 123456780（ 2） 手动布局：用户可以手动输入起始状态和终点状态，空格用 0表示2 8 31 47 6 51 2 38 47 6 5（ 3） 导入布局：用户输入结束后
2、把布局导入到程序中（ 4） 随机生成：包括（起始状态）（目标状态）的随机生成，避免无解可以产生一个有解状态八数码。（建议勾选）(5)如下图进行导入操作：（单击左框状态设置栏的 “导入布局 ”按钮）b）算法选择区C）当前步骤栏目：显示当前进行的步数统计（如图）d) 操作栏 恢复初态：演示后恢复到初始状态 开始搜索：搜索是否有解及步数 自动演示：界面将实时显示求解过程e) 界面选择输入初始时，每个格子均显示所有数字，之后根据用户选择动态更新候选数四 算法思想及分析1.采用算法 ：盲目搜索（深度优先），启发式搜索两种2. 设计的思想（启发函数）a. 启发函数一：f(n)=g(n)+h(n) 其中 g
3、（ n）为当前节点深度， h（ n）为直线距离 b. 启发函数二：1 (7向下一次 ) + 1 (2向上一次 ) + 2 (4向左两次 ) + 3 (6向右两次，向上一次 ) + 2 (5向上一次向左一次 ) = 9f(n)=g(n)+h(n) 其中 g（ n）为当前节点深度， h（ n）为曼哈顿距离 3.数据结构定义了一个结构体，每个如左图结点都包含如下信息：class Node /定义 NODE 结构 int Id; /当前结点 IDint arr=new int33; /八数码状态数组int FatherId; /父亲结点的 IDint g; /深度int f; /权值int h; /曼
4、哈顿long hash; /哈希值OPEN表：存放未检查和扩展的节点CLOSED表：存放已检查和扩展的节点规则：1从 OPEN表中 取出 一个节点 n，检查其是否为目标节点，若是则搜索成功，返回结果路径。2将 n放入 CLOSED表中。3 扩展 n的子节点， 检查重复性 ， 放入 OPEN表中。4）主要的实现框架两个随机状态之间是否可达，可以通过计算两者的逆序值，若两者奇偶性相同则可达，否则两个状态不可达。（关键算法）for(int i = 0;i指明/了他是一个结点，是不是很明了了？ open.setElementAt(temp,min_flag);/你把那个第一个放了最小的，我这个原本第一个放哪里？/当然是放到那个min_flag的位置啦五 结果图示及分析六 算法效率相同输入： 243185670相同输出： 635207481盲目搜索执行时间： 2609ms执行步数： 7286已扩展结点： 7500未扩展结点： 5468A 星算法 1（直线距离）执行时间： 297ms执行步数： 22已扩展结点： 2518未扩展结点： 1617A 星算法 2（曼哈顿距离）执行时间： 94ms执行步数： 22已扩展结点： 1067未扩展结点： 745
