“八数码问题求解”程序说明

八数码问题求解八数码问题求解 程序说明程序说明 姓名 崔秋石 姓名 崔秋石 学号 学号 1080329038 班级 班级 B0803291 一 程序中使用到得算法一 程序中使用到得算法 本程序用到了三种搜索算法 分别是 BFS 广度优先搜索 DFS 深度优先搜索 和 A 算法 A BFS 算法步骤 1 每次搜索之前清空 OPEN CLOSED PATH 三表 并初始化初始状态 Initstate 2 将初始节点放入 OPEN 表中 3 判断初始和目标状态 Goalstate 是否相同 如是则成功退出 4 将 OPEN 表中首端第一个节点取出放入 CLOSED 表中 5 如果 OPEN 表为空 则失败退出 否则用函数 expandnodeBFS 按 Left Right Up Down 顺序扩展节点 给子节点的深度赋值 定义其父节点和子 节点的指针 6 判断扩展后的子节点是否和目标节点相同 如是则成功退出 并用 FindPath 函数按 照其父节点回溯到初始节点以寻找路径 并把所寻每一节点放入 PATH 表中 如果 不相同 则把它放入 OPEN 表末端 7 转步骤 4 广度优先搜索算法程序流程示意图 B DFS 算法步骤 1 将初始节点 S 放入 OPEN 表中 若此节点为目标节点 则得解 2 若 OPEN 表为空 则失败退出 3 把 OPEN 表中首端第二个节点 n 移出 放入 CLOSED 表中 4 若节点 n 的深度等于最大限制深度 则转向 2 5 扩展节点 n 产生其全部子节点 并将它们放入 OPEN 表首端 并给出返回 n 的指 针 若节点不能扩展 则转向 2 6 若后继子节点中有目标节点 则得解 成功退出 开始 初始节点放入OPEN表中 把OPEN表首端第一个节点取出放入 CLOSED表中 失败 退出OPEN表为空 扩展节点 并将其子节点放入 OPEN表首端 并为每个子节 点配置指向其父节点的指针 节点为目标节点 成功 退出 节点能否扩展 是 是 是 否 否 否 深度优先搜索算法程序流程示意图 C Heuristic A 算法步骤 1 每次搜索之前清空 OPEN CLOSED PATH 三表 并初始化初始状态 Initstate 2 将初始节点放入 OPEN 表中 3 判断初始和目标状态 Goalstate 是否相同 如是则成功退出 4 从 OPEN 表中找到估价值最小的节点 函数 Evaluate 将其取出放入 CLOSED 表中 5 如果 OPEN 表为空 则失败退出 否则用函数 expandHeuristic 按 Left Right Up Down 顺序扩展节点 给子节点的深度赋值 定义其父节点和子 节点的指针 6 判断扩展后的子节点是否和目标节点相同 如是则成功退出 并用 FindPath 函数按 照其父节点回溯到初始节点以寻找路径 并把所寻每一节点放入 PATH 表中 如果 不是 则判断子节点是否已在 CLOSED 表和 OPEN 表中 如果都不在 则放入 OPEN 表末端 7 转步骤 4 启发式搜索算法程序流程示意图 二 程序数据结构描述二 程序数据结构描述 1 节点状态表示 定义结构体 struct Eightpuzzle int depthcurrent 节点深度 int state 9 节点状态 struct Eightpuzzle father 节点的父节点 struct Eightpuzzle child 节点的子节点 2 OPEN 表 CLOSED 表 用 MFC 中 CList 类定义 CPtrList Open OPEN 表 CPtrList Closed CLOSED 表 CPtrList Path 用于最后存放路径 PATH 表 三 函数说明三 函数说明 1 估价函数 int Evaluate Eightpuzzle current Eightpuzzle goal 返回一个 int 型数值 计算状态 current 中每个格子的号码与 goal 中相应号码之间的距 离之和 取 f n d n h n h n P n 2 enum direction LEFT RIGHT UP DOWN INVALID direction MoveDirection Eightpuzzle father Eightpuzzle child int 定义枚举类型 direction 判断返回节点扩展时可以移动的方向 3 主要函数一览 public bool NumberCheck int state 9 检查数据有效性 bool Ishavepath Eightpuzzle initial Eightpuzzle goal 检查时候有路径 bool SearchHeuristic 启发式搜索 bool SearchBFS 广度优先搜索 bool SearchDFS 深度优先搜索 int Evaluate Eightpuzzle current Eightpuzzle goal 计算估价函数取 P n Eightpuzzle Initstate 初始节点 Eightpuzzle Goalstate 目标节点 CPtrList Open OPEN 表 CPtrList Closed CLOSED 表 CPtrList Path 用于最后存放路径 PATH 表 int m ndepth Eightpuzzle currentstep private enum direction LEFT RIGHT UP DOWN INVALID void FindPath Eightpuzzle finalnode Eightpuzzle initnode 按各节点父节点寻找路径 direction MoveDirection Eightpuzzle father Eightpuzzle child int 判断可移动方向 bool IsinClosed Eightpuzzle curnode 判断当前扩展的节点是否已存在 CLOSED 表中 bool IsinOpen Eightpuzzle curnode 判断当前扩展的节点是否已存在 OPEN 表中 bool Comparestate Eightpuzzle stateone Eightpuzzle stateanother 比较两个节点状态 时候相同 void Copy8puzzle Eightpuzzle stateone Eightpuzzle stateanother 复制节点状态 bool MovetoDown Eightpuzzle fatherstate Eightpuzzle childstate 向下移动 bool MovetoUp Eightpuzzle fatherstate Eightpuzzle childstate 向上移动 bool MovetoRight Eightpuzzle fatherstate Eightpuzzle childstate 向右移动 bool MovetoLeft Eightpuzzle fatherstate Eightpuzzle childstate 向左移动 bool expandnodeBFS Eightpuzzle newnode Eightpuzzle nodeN Eightpuzzle pinit 广度 优先搜索中扩展节点 bool expandnodeDFS Eightpuzzle newnode Eightpuzzle nodeN Eightpuzzle pinit 深度 优先搜索中扩展节点 bool expandnodeHeuristic Eightpuzzle newnode Eightpuzzle pstart 启发式搜索中扩展