1、基于 A 星算法解决 8 数码问题的编程实现姓 名： 学 号： 2010-11-25基于 A 星算法解决 8 数码问题的编程实现- 1 -一、问题描述8 数码问题又称 9 宫问题，与游戏“华容道”类似。意在给定的 棋格3的 8 个格子内分别放一个符号，符号之间互不相同，余下的一格为空格。并且通常把 8 个符号在棋格上的排列顺序称作 8 数码的状态。开始时，规则给定一个初始状态和一个目标状态，并要求被试者对棋格内的符号经过若干次移动由初始状态达到目标状态，这个过程中只有空格附近的符号可以朝空格的方向移动，且每次只能移动一个符号。为方便编程和表示，本文中 8 个格子内的符号分别取 18 的 8 个
2、数字表示，空格用 0 表示。并给定 8 数码的初始状态和目标状态分别如图 1、2 所示。图 1 初始状态 图 2 目标状态则要求以图 1 为初始状态，通过交换 0 和 0 的上、下、左、右四个方位的数字（每次只能和其中一个交换） ，达到图 2 所示目标状态。二、算法设计根据任务要求，本文采用 A*搜索算法。但要在计算机上通过编程解决该问题，还应当解决该问题在计算机上表示的方式，并设计合适的启发函数，以提高搜索效率。状态的表示在 A*算法中，需要用到 open 表和 closed 表，特别是在 open 表中，待扩展节点间有很严格的扩展顺序。因此在表示当前状态的变量中，必须要有能指向下一个扩展节
3、点的指针，以完成对 open 表中元素的索引。从这一点上看，open 表中的元素相互间即构成了一个线性表，因此初步选定使用结构体表示问题的状态。如图 3 所示，表示问题的结构体包括表示当前节点状态的 DATA 和指向open 表中下一个待扩展节点的指针 NEXT。图 3 结构体现在进一步考虑 DATA 中包括的内容：如图 1、2 所示，8 数码问题的提出是以一个 数表表示的，因此本文中3采用一个 的二维数组 s33表示当前状态的具体信息。而为了保证在搜3基于 A 星算法解决 8 数码问题的编程实现- 2 -索到目标状态后能够顺利复现寻优路径，当前状态的 DATA 中还应该包括一个指向其父节点的
4、指针 father，这样，才能在达到目标状态后，通过指针 father逐层回溯到初始状态，即复现寻优路径。另一方面，A*搜索算法是通过考察节点的代价值来决定 open 表的排序的，因此在表示当前状态的 DATA 中还应该有对当前节点代价值的描述。根据 A*算法的定义，当前节点的代价值由估价函数给出，即： ()()fndhn其中： 表示当前节点 n 在搜索树中的深度；()dn是启发函数。h因此，在 DATA 还应包括表示当前节点代价、深度和启发信息的 、f、 。d最后，为提高程序的运行效率，减少程序扩展节点时搜索量，将当前 0 所处位置(i_0：0 在 s33中所处行号，j_0：0 在 s33中
5、所处列号)也存储在 DATA 中。综上所述，问题状态的表示如下图所示。图 4 问题的状态表示启发函数的设计根据 A*算法的定义，启发函数应满足： 。*()hn其中： 表示从当前节点 n 到目标节点 s_g 的最优路径的实际代价。*()hn并且，在满足 的条件下， 的值越大它所携带的启发性信息*()h()越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。在 8 数码问题中，常用的启发函数为： “不在位”数码个数，或数码“不在位”的距离和。显然，后者的 不小于前者，因此本文中采用数码“不在()hn基于 A 星算法解决 8 数码问题的编程实现- 3 -位”的距离和作为启发函数。规则库设计0 在某
6、一位置时，能选择向左、向右、向上、向下移动中的哪几种策略进行移动，主要是由当前 0 所处位置（更具体地说是当前位置的行列号）和其祖父节点（为提高搜索效率，新扩展的节点应当至少不为其祖父节点）所决定的。当然，按照 A*算法的思想，每扩展出一个新节点，都要判断其是否为有效子节点，不为有效子节点的不能加入到 open 表中。这一段的具体过程可以参考程序流程部分。因此移动的规则库可以写成如下形式：左移：if(p-j_0=1) /空格所在列号不小于 1,可左移temp=p-father;if(temp!=NULL /新节点与其祖父节点相同，无操作else /新节点与其祖父节点不同，或其父节点为起始节点(
7、扩展新节点，并判断是否加入 open 表)/详细代码见源程序/end 左移右移：if(p-j_0father;if(temp!=NULL /新节点与其祖父节点相同，无操作else /新节点与其祖父节点不同，或其父节点为起始节点(扩展新节点，并判断是否加入 open 表)/详细代码见源程序/end 右移上移：if(p-i_0=1) /空格所在列号不小于 1,可上移temp=p-father;基于 A 星算法解决 8 数码问题的编程实现- 4 -开 始初 始 化 s_0， 把 s_0送 入 open表open表 为 空 ? 失 败 ， 退 出把 open表 的 首 节 点 （ 节 点 n）从 e表
8、 移 出 ， 放 入 closed表节 点 n为 目 标 节 点 ？ 成 功 ， 退 出YN扩 展 节 点 n： 将 有 效子 节 点 加 入 open表 ，无 效 子 节 点 删 除if(temp!=NULL /新节点与其祖父节点相同，无操作else /新节点与其祖父节点不同，或其父节点为起始节点(扩展新节点，并判断是否加入 open 表)/详细代码见源程序/end 上移下移：if(p-i_0father;if(temp!=NULL /新节点与其祖父节点相同，无操作else /新节点与其祖父节点不同，或其父节点为起始节点(扩展新节点，并判断是否加入 open 表)/详细代码见源程序/end
9、下移程序流程主程序流程图：基于 A 星算法解决 8 数码问题的编程实现- 5 -其中，扩展节点 n 的具体步骤如下：a) 首先判断其是否在 closed 表已经出现过, 如果出现过，并且新节点的代价值比其小，则应将其从 closed 表删除，同时将新节点加入到 open 表；如果没有出现过，则转 b。b) 判断其是否已经存在于 open 表中待扩展，如果出现过，并且新节点的代价值比其小，则应将其从 open 表删除，同时将新节点加入到 open 表；如果没有出现过，则说明该节点为一个全新的节点，转 c。c) 将该节点加入 open 表。三、运行结果基于 A 星算法解决 8 数码问题的编程实现-
10、 6 -第 4 步 右移当前：f=8，d=4，h=4当前节点状态为：1 3 28 0 57 6 4第 5 步 上移当前：f=11，d=5，h=6当前节点状态为：1 0 28 3 57 6 4第 6 步 右移当前：f=12，d=6，h=6当前节点状态为：1 2 08 3 57 6 4第 7 步 下移当前：f=13，d=7，h=6当前节点状态为：1 2 58 3 07 6 4第 8 步 下移当前：f=14，d=8，h=6当前节点状态为：总共扩展 1269 个节点总共扩展 22 层*解路径如下：第 0 步当前：f=8，d=0，h=8当前节点状态为：3 8 21 0 57 6 4第 1 步 上移当前：
11、f=9，d=1，h=8当前节点状态为：3 0 21 8 57 6 4第 2 步 左移当前：f=10，d=2，h=8当前节点状态为：0 3 21 8 57 6 4第 3 步 下移当前：f=9，d=3，h=6当前节点状态为：1 3 20 8 57 6 4基于 A 星算法解决 8 数码问题的编程实现- 7 -1 2 58 3 47 6 0第 9 步 左移当前：f=15，d=9，h=6当前节点状态为：1 2 58 3 47 0 6第 10 步 上移当前：f=16，d=10，h=6当前节点状态为：1 2 58 0 47 3 6第 11 步 右移当前：f=19，d=11，h=8当前节点状态为：1 2 58
12、 4 07 3 6第 12 步 上移当前：f=20，d=12，h=8当前节点状态为：1 2 08 4 57 3 6第 13 步 左移当前：f=21，d=13，h=8当前节点状态为：1 0 28 4 57 3 6第 14 步 下移当前：f=22，d=14，h=8当前节点状态为：1 4 28 0 57 3 6第 15 步 下移当前：f=23，d=15，h=8当前节点状态为：1 4 28 3 57 0 6第 16 步 右移当前：f=24，d=16，h=8当前节点状态为：1 4 28 3 57 6 0第 17 步 上移当前：f=23，d=17，h=6当前节点状态为：1 4 28 3 07 6 5第 18 步 左移当前：f=22，d=18，h=4当前节点状态为：1 4 28 0 37 6 5第 19 步 上移当前：f=23，d=19，h=4当前节点状态为：1 0 28 4 37 6 5第 20 步 右移当前：f=24，d=20，h=4当前节点状态为：1 2 08 4 3基于 A 星算法解决 8 数码问题的编程实现- 8 -7 6 5第 21 步 下移当前：f=23，d=21，h=2当前节点状态为：1 2 38 4 07 6 5第 22 步 左移当前：f=22，d=22，h=0当前节点状态为：1 2 38 0 47 6 5
