A星算法求八数码问题实验报告

人工智能实验报告人工智能实验报告 实验名称 八数码问题实验名称 八数码问题 姓名 姓名 xx 学号 学号 2012210 xx xx 计算机学院计算机学院 2014 年年 1 月月 14 日日 1 实验目的实验目的 掌握 A 的思想 启发式搜索 来求解在代价最小的情况下将九宫格从一 个状态转为另状态的路径 2 实验内容实验内容 给定九宫格的初始状态 要求在有限步的操作内 使其转化为目标状态 且所得到的解是代价最小解 即移动的步数最少 并打印出求解路径 例如 28 3 164 705 28 3 164 705 3 A 算法思想 算法思想 1 思想 思想 A 算法是一种静态路网中求解最短路最有效的直接搜索方法 估价值与实 际值越接近 估价函数取得就越好 2 2 原理 原理 估价函数公式表示为 f n g n h n 其中 f n 是从初始点经由节点 n 到目标点的估价函数 g n 是在状态空 间中从初始节点到 n 节点的实际代价 h n 是从 n 到目标节点最佳路径的估计 代价 保证找到最短路径 最优解的 条件 关键在于估价函数 h n 的选取 估价值 h n 实际值 搜索的点数少 搜索范围小 效率高 但不能保证得到最优 解 4 算法流程 算法流程 是 是 输出路径 否 生成 n 的所有子状态 Heuristic Search 启发式搜索 While 未拓 展表不为空 从未拓展表中删除第一个状态 n N 为目标状态 Case 此子状态 不在拓展表和 未拓展表中 Case 此子状态 在未拓展表中 Case 此子状态 在拓展表 计算该子状态的估价函 数值 记录比已有的路径更短 的路径 记录比已有的路径更短 的路径 5 关键技术 关键技术 1 1 使用了使用了 CreateChildCreateChild 函数 求得了任意未拓展九宫格的扩展结点 便于 函数 求得了任意未拓展九宫格的扩展结点 便于 拓展子空间 搜索所有情况 拓展子空间 搜索所有情况 关键代码 关键代码 bool CreateChild NOExtend ns NOExtend ne int i j k 0 for i 0 i 3 i for j 0 j 0 将空格向上移动 CopySudoku ns k cur sudoku ne cur sudoku 先把未改变的九 宫格复制给九宫格数组的某一元素 ns k cur sudoku num i j ne cur sudoku num i 1 j 然后 仅改变此二维九宫格的两项值即可 ns k cur sudoku num i 1 j 0 ns k dx 1 k if j 1 2 将空格向右移动 CopySudoku ns k cur sudoku ne cur sudoku ns k cur sudoku num i j ns k cur sudoku num i j 1 ns k cur sudoku num i j 1 0 ns k dx 1 k if i 1 0 将空格向左移动 CopySudoku ns k cur sudoku ne cur sudoku ns k cur sudoku num i j ns k cur sudoku num i j 1 ns k cur sudoku num i j 1 0 ns k dx 1 k return 1 返回 return 0 2 2 用启发式搜索函数寻找求解路径 运用了 用启发式搜索函数寻找求解路径 运用了 A A 算法的思想 能够更快的求解算法的思想 能够更快的求解 出最优解 出最优解 关键代码 关键代码 bool Heuristic Search Sudoku start Sudoku end int a 0 b 0 c 0 int count 0 NOExtend Sudoku ns 未扩展结点表 Extended Sudoku es 已扩展结点表 Path path 求解路径 NOExtend father 定义父节点 ns no node a cur sudoku start 初始化未拓展结点表 ns no node a dx 0 ns no node a hx GetHx ns no node a cur sudoku end ns no node a fx ns no node a dx ns no node a hx a while a 0 当未拓展结点表不为空时 father ns no node 0 父节点为为拓展表的第一个结点 path pa c father 记录求解路径 DeleteFirst ns a 从未拓展表中删除第一个结点 a if EqualSudoku father cur sudoku end 如果找到了目标九宫格则输出 求解路径 ShowPath path c return 1 NOExtend child 4 因为九宫格只能拓展上下左右四 个方向所以拓展出的结点最多有四个 CreateChild child father 生成父节点的扩展结点 if CreateChild child father continue 如果没有扩展结点就跳出进行下一次循 环 for int i 0 i 4 i if child i dx 1 对于父节点可以生成的每个子结点 if ExistNOExtend ns child i cur sudoku 获取此结点的估价值 ns no node a child i ns no node father a father a continue if ExistNOExtend ns child i cur sudoku 如果未拓展表中有此状态 此求得当前状态的估价值并且与表中 存在的此状态的估价值比较 若估价值大就放弃此结点 更小 就加入此结点 Value child i father end if child i fx father fx ns no node a child i ns no node father a father a continue if ExistExtended es child i cur sudoku 如果已拓展表中有此状态 此求得当前状态的估价值并且与表中 存在的此状态的估价值比较 若估价值大就放弃此结点 更小 就加入此结点 Value child i father end if child i fxMAXPATH break return 0 6 6 实验心得实验心得 1 学习