维普资讯 http://www.cqvip.com ２００８年第１期 文章编号：１００６—２４７５（２００８）０１－００２９－０３ 计算机与现代化 ＪＩＳＵＡＮＪＩ ＹＵ ＸＩＡＮＤＡＩＨＵＡ 总第１４９期 基于Ａ术算法的八数码问题的优化实现 ｂ奎昊，宋杰，李国斌 （安徽大学计算智能与信号处理教育部重点实验室，安徽合肥２３００３９） 摘要：用人工智能领域中经典的Ａ 算法解决了人工智能中常见的八数码问题。本文首先介绍了八数码问题，然后对 Ａ 算法进行了解释。针对八数码问题给出并证明了路径不存在时的条件，并事先作了判定。定义了灵活的估价函数， 分析了估价函数对程序效率的影响，并对Ｃｌｏｓｅｄ表进行了若干优化，提高了搜索效率，取得了较好的效果。 关键词：八数码问题；Ａ 算法；逆序数；估价函数 中图分类号：ＴＰ３１１ 文献标识码：Ａ Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ Ｅｉｇｈｔ Ｐｕｚｚｌｅ Ｐｒｏｂｌｅｍ Ｂａｓｅｄ ｏｎ Ａ Ａｌｇｏｒｉｔｈｍ ｂｉｎ ＢＵ Ｋｕｉ—ｈａｏ，ＳＯＮＧ Ｊｉｅ，ＬＩ Ｇｕｏ－。（Ｔｈｅ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ，Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ， Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｈｅｆｅｉ ２３００３９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｅｉｇｈｔ ｐｕｚｚｌｅ ｐｒｏｂｌｅｍ ｉｓ ｃｏｍｍｏｎ ｉｎ ｔｈｅ ａｒｔｉｉｆｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ ｄｏｍａｉｎ．Ｔｈｅ ａｒｔｉｃｌｅ ｒｅｓｏｌｖｅｓ ｔｈｉｓ ｐｒｏｂｌｅｍ ｔｈｒｏｕｇｈ ｔｈｅ ｃｌａｓｓｉｃａｌ Ａ ａｌｇｏｒｉｔｈｍ．Ｆｉｒｓｔｌｙ，ｔｈｅ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｅｉｇｈｔ ｐｕｚｚｌｅ ｐｒｏｂｌｅｍ，ａｎｄ ｔｈｅｎ ｄｅｓｃｒｉｂｅｓ ｔｈｅ Ａ‘ａｌｇｏｒｉｔｈｍ．Ｆｏｃｕｓ ｏｎ ｔｈｅ ｅｉｇｈｔ ｐｕｚｚｌｅｓ ｐｒｏｂｌｅｍ，ｔｈｅ ａｒｔｉｃｌｅ ｇｉｖｅｓ ｔｈｅ ｃｏｎｄｉｔｉｏｎ ｗｈｅｎ ｔｈｅ ｐａｔｈ ｄｏｅｓ ｎｏｔ ｅｘｉｓｔ ａｎｄ ｐｒｏｖｅｓ ｉｔ．Ｔｈｅ ｐａｐｅｒ ｄｅｆｉｎｅｓ ａ ｆｌｅｘｉｂｌｅ ｅｖａｌ— ｕａｔｉｏｎ ｆｕｎｃｔｉｏｎ，ａｎａｌｙｚｅｓ ｉｔｓ ｉｎｆｌｕｅｎｃｅ ｔｏ ｔｈｅ ｆｕｎｃｔｉｏｎ ｅｆｉｃｉｆｅｎｃｙ ａｎｄ ｏｐｔｉｍｉｚｅｄ Ｃｌｏｓｅｄ ｔａｂｌｅ．Ａｌｌ ｔｈｏｓｅ ｅｎｈａｎｃｅｓ ｔｈｅ ｓｅａｒｃｈ ｅｆｉ— ｆｃｉｅｎｃｙ ａｎｄ ｏｂｔａｉｎｅｓ ｔｈｅ ａｎｔｉｃｉｐａｔｅｄ ｅｆｆｅｃｔ． Ｋｅｙ ｗｏｒｄｓ：ｅｉｇｈｔ ｐｕｚｚｌｅ ｐｒｏｂｌｅｍ；Ａ ａｌｇｏｒｉｔｈｍ；ｐｅｒｍｕｔａｔｉｏｎ ｎｕｍｂｅｒ；ｅｖａｌｕａｔｉｏｎ ｆｕｎｃｔｉｏｎ ０ 引 言 八数码问题是人工智能领域中的一个经典的问 题，虽然已有不少八数码的算法，但现有的一般搜索 方法在搜索过程中需要回溯，故其实现较为复杂。本 文对此进行改进，采用基于Ａ 算法来实现，并针对 八数码问题进行了优化，取得了较好的结果。 的数码盘的排列（称目标状态），如图１所示。 图１初始状态和目标状态 １ 问题描述 所谓八数码问题起源于一种游戏：将分别标有数 字１，２，３，…，８的八块正方形数码牌任意地放在一块 ３×３的数码盘上。放牌时要求不能重叠。于是，在３ ２ Ａ 算法 由于盲目搜索效率低，耗费过多的计算空间与时 间，因此进行搜索技术一般需要某些有关具体问题领 域的特性的信息，把此种信息叫做启发信息。利用启 发信息的搜索方法叫做启发式搜索方法。启发式搜 索方法有很多，如局部最优搜索法、最好优先搜索法 等等。一个比较灵活（但代价也较大）的利用启发信 息的方法是应用某些准则来重新排列每一步Ｏｐｅｎ ×３的数码盘上出现了一个空格。现在要求按照每 次只能将与空格相邻的数码牌与空格交换的原则，将 任意摆放的数码盘（称初始状态）逐步摆成某种给定 收稿日期：２００７－０５．３１ 作者简介：卜奎昊（１９８３一），男，江苏淮安人，安徽大学硕士研究生，研究方向：嵌人式系统开发；宋杰（１９６６．），男，副教授，博 士；李国斌，男，硕士。 维普资讯 http://www.cqvip.com
３０ 计算机与现代化 ２００８年第１期 表中所有节点的顺序。然后，搜索就可能沿着某个被 性改变，所以移动两次后奇偶性不变。所以，上下左 认为是最有希望的边缘区段向外扩展。应用这种排 序过程，需要估算某些节点“希望”的量度，这种量度 叫做估价函数（ｅｖａｌｕａｔｉｏｎ ｆｕｎｃｔｉｏｎ）。根据估价函数 的不同，人们得出了不同的启发式搜索算法。 Ａ 算法是一种有序搜索算法，其特点在于对评 价函数的定义上。对于一般的有序搜索，总是选择ｆ 右四个操作均不会影响序列逆序数的奇偶性。 据统计，单纯用Ａ’算法要花费几个小时时间才 能判断出不能达到目标状态，这时Ｃｌｏｓｅｄ表长度为 １８１４４０。在本方法中，开始时就判断目标状态是否可 达，这样就节约了大量的时间。这是本方法针对八数 码这个具体问题的第一点优化。 ３．２估价函数 值最小的节点作为扩展节点。因此，ｆ是根据需要找 到一条最小代价路径的观点来估算节点的，可考虑将 每个节点ｎ的估价函数值分解为两个分量：从起始节 本方法实现的程序中用到的估价函数如下：ｆ（ ｎ）＝ａ・ｈ（ｎ）＋ｂ・ｇ（ｎ）。其中，ｈ（ｎ）代表搜 索树中节点ｎ的深度，根节点深度是０。启发函数ｇ（ ｎ）定义为当前节点与其目标节点相应位置不相同元 素的个数。可根据需要选择相应系数ａ，ｂ的值，本 点到节点ｎ的最小代价路径的代价与从节点ｎ到目 标节点的最小代价路径的代价之和，也就是说ｆ（ｎ） 是约束通过节点ｎ的一条最小代价路径的代价的一 个估计。再定义一个函数ｆ ，使得在任意一个节点ｎ 上的函数值ｆ （ｎ）就是从节点Ｓ到节点ｎ的一条最 佳路径的实际代价加上从节点ｎ到目标节点的一条 程序分别选了ａ＝１，ｂ＝１和ａ＝０，ｂ＝１两组数据，通 过比较说明了估价函数对效率的影响。 ３．３对Ｏｐｅｎ表和Ｃｌｏｓｅｄ表的优化 最佳路径的代价之和，即： ｆ’（ｎ）＝ｇ （ｎ）＋ｈ （ｎ） 本算法在插入节点到Ｏｐｅｎ表时是按照估价函 数从小到大有序插入的，这样做就不必在每次查找当 前状态下估价函数最优的节点时重排Ｏｐｅｎ表。只 要取Ｏｐｅｎ表中的第一个元素即可（这第一个元素代 表的节点就是所要查找的估价函数值最优的节点）。 这样也节约了大量的时间。这是本算法的第二点优 化。 评价函数ｆ是ｆ 的一个估计，这个估计可由下式 给出： ｆ（ｎ）：ｇ（ｎ）＋ｈ（ｎ） 其中ｇ是ｇ 的估计，ｈ是ｈ 的估计。ｇ （ｎ）的 估计ｇ（ｎ）就是搜索树中从初始节点到当前节点ｎ 的这段路径的代价，这一代价可以由从初始节点到当 前节点ｎ寻找路径时，把遇到的各段路径的代价加起 来给出ｏ ｈ （ｎ） 的估计ｈ（ｎ）依赖于有关问题的领 域的启发信息，于是被称作启发函数。在启发函数 中，应用的启发信息（问题知识）越多，扩展的节点就 越少，这样就能更快地搜索到目标节点¨ 。 按照Ａ 算法，在算法实现中需要判断某后继节 点是否在Ｃｌｏｓｅｄ表中，而Ｃｌｏｓｅｄ表较长，因此许多情 况下查找Ｃｌｏｓｅｄ表都要花费很长时间，本算法通过 减小Ｃｌｏｓｅｄ表的长度对此进行了优化。因为任何一 个状态与目标状态对应位置不同元素的个数只可能 是０、２、３、４、５、６、７、８、９个，如果相应位置不同元素个 数为０个，则这种情况下已经成功到达目标状态，此 时只要通过父节点向前搜索即可找到从初始节点到 ３ 问题的分析与解决 ３．１关于解的存在性的结论 目标节点的路径。因此可把Ｃｌｏｓｅｄ表分解为一个含 空格不计，则九宫图的某状态为数１到８的一个 排列，记为ｎ０ｎｌｎ２ｎ３ｎ４ｎ５ｎ６ｎ７。两个状态之间是否可 ８个元素的一维数组Ｃｌｏｓｅｄ［８］，在将某状态节点插 入到Ｃｌｏｓｅｄ表时，假设该节点与目标节点相应位置 达可以通过计算两者的逆序数来判断，若两者逆序数 的奇偶性相同则可达，否则不可达。也即对于任一个 目标状态节点，只有（１／２）×９ １：１８１４４０个状态可 达该节点。 简单证明一下： 不同元素个数为ｉ，将该节点插入到相应的Ｃｌｏｓｅｄ［ｉ一 ２］表中，这样Ｃｌｏｓｅｄ［ｉ］表中分别链接了与目标节点 相应位置不同元素的个数为（ｉ＋２）个（ｉ＝０，１，２， ３，４，５，６，７）的状态节点，这样在判断某状态节点是否 在Ｃｌｏｓｅｄ表中时只要根据它与目标节点相应位置不 ｌｅｆｔ和ｒｉｇｈｔ操作，不会影响状态的逆序值，因为 它不会改变这个排列。 ｕｐ和ｄｏｗｎ操作是使某个位置的数字左或右移 两位。由于数字序列的每一次移动会使逆序值奇偶 同元素的个数查找相应的Ｃｌｏｓｅｄ［ｉ］表即可。这是本 算法的又一优化 Ｊ。 ４ 程序数据结构与程序实现 维普资讯 http://www.cqvip.com ２００８年第１期ｌ、＿奎昊等：基于Ａ 算法的八数码问题的优化实现 ３１ ４．１程序数据结构 继节点是否在Ｏｐｅｎ表、相应的Ｃｌｏｓｅｄ［ｉ］表中，如果 ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ＳＮｉｎｅＧｒｉｄ／／定义包含状态、估价值、指向后 在则不处理该节点，否则把该后继节点按估价函数值 继节点指针等的结构体 插入到有序Ｏｐｅｎ表中，并维持Ｏｐｅｎ表的有序性。 ｛（３）从Ｏｐｅｎ表中删除节点Ｐ并把它插入到相应 ｉｎｔ Ｓ［３］［３］；／／存放节点棚应的存放值 的Ｃｌｏｓｅｄ［ｉ］表以待将来找路径时用。 ｉｎｔ ｗｅｉｇｈｔ；／／存放节点的估价值 （４）转（１）循环执行。 ＳＮｉｎｅＧｒｉｄ ｐａｒｅｎｔ；／／它的父类节点，即产生该节点的节 ４．３程序界面 点，可用于同溯找路径 ＳＮｉｎｅＧｒｉｄ ｎｅｘｔ；／／下一个节点，用于链接链表 程序界面如图２所示 。 ｝ＳＮｉｎｅＧｆｉｄ， ＣＰｔｒＬｉｓｔ； ｃｌａｓｓ ＣＮｉｎｅＧｒｉｄ ｛ ｐｕｂｌｉｃ： ＳＮｉｎｅＧｒｉｄ ＳｔａｔｅＳｔａｒｔ；／／初始状态节点 ＳＮｉｎｅＧｒｉｄ ＳｔａｔｅＡｉｍ：／／目标状态节点 ＳＮｉｎｅＧｒｉｄ ＳｔａｔｅＣｕｒ：／／当前状态节点 ＣＰｔｒＬｉｓｔ Ｏｐｅｎ：／／Ｏｐｅｎ表 ＣＰｔｒＬｉｓｔ Ｃｌｏｓｅｄ［８］；／／将Ｃｌｏｓｅｄ表分解为一个一维数组， 减小了查找长度 ＣＰｔｒＬｉｓｔ ＲｏｕｔｅＬｉｓｔ；／／保存结果 ｐｕｂｌｉｃ： ｉｎｔ ｄｅｐｔｈ；／／搜索深度 ｉｎｌｉｎｅ ｉｎｔ ＣａｌＤｉｆｅｒｅｎｅｅ（）；／／当前节点与目标节点相应位 置不同元素的个数 图２程序运行界面 ｂｏｏｌ Ｓｕｃｃｅｓｓｏｒ（）；／／产生后继节点 ４．４改进后的性能与改进前性能的比较 ｖｏｉｄ ＦｉｎｄＲｏｕｔｅ（）；／／找出路径 在这里设计了三个有代表性的初始状态，如图３ ｖｏｉｄ ＩｎｓｅｒｔＬｉｓｔ（ＣＰｔｒＬｉｓｔ Ｌｉｓｔ，ＣＰｔｒＬｉｓｔ ｎｏｄｅ）；／／把节点插 所示。 入链表 ｖｏｉｄ ＤｅｌｅｔｅＮｏｄｅ（ＣＰｔｒＬｉｓｔ Ｌｉｓｔ，ＣＰｔｒＬｉｓｔ ｎｏｄｅ）；／／把节点 从链表删除 田园豳 圈 ｝； ４．２程序执行步骤 图３实验的初始状态和目标状态 １．首先判断初始状态和目标状态对应排列逆序 在本方法实现的程序中，对于不同的估价函数， 数的奇偶性是否相同，如果两者逆序数的奇偶性不相 将初始状态１、初始状态２、初始状态３输入得到一些 同，则查找不到路径，程序结束，否则程序向下执行第 参数性能如表１所示（设：ｆ是估价函数，ｈ是搜索深 ２步。 度，ｇ是初始状态与目标状态中对应位置不同元素个 ２．置Ｏｐｅｎ表、Ｃｌｏｓｅｄ［ｉ］表为空，把初始状态节 数）。 点捅人到Ｏｐｅｎ表中。 表１不同估价函数所消耗资源比较 ３．循环执行以下几步： 估价函数 ｆ＝ｇ ｆ＝ｇ＋ｈ （１）检查Ｏｐｅｎ表是否为空，如果为空，则查找失 初始状态 初始 初始 初始 初始 初始 初始 败，即没有从初试状态到目标状态的路径，否则找到 状态１ 状态２ 状态３ 状态１ 状态２ 状态３ 路径长 估价函数最优的节点Ｐ．产生Ｐ的后继节点，并判断 度（步） ２８ ‘８０ 无路径 １６ ２０ 无路径 该后继节点是否就是目标节点。如果该后继节点是 搜索时 目标节点则成功找到路径，通过父辈节点找到从初试 ＜１ １ ＜１ ＜１ ５ ＜１ 间（ｓ） 状态到目标状态的路径。 通过实验，可知对于估价函数ｆ＝ｇ，可很快得 （２）如果该后继节点不是目标节点，则判断该后 到从初始状态到目标状态的路径，但（下转第３５页） 维普资讯 http://www.cqvip.com
２００８年第１期 吴良清等：基于Ｗｅｂ Ｓｅｒｖｉｃｅｓ的商务智能研究 ３５ 坌析以 ｏ Ｍ ［２］郑４－￣，炜ｆＥ，韩２０毅０６，（宋２６绍）：成５２．‘商业智能门户应用策略研究［Ｊ］ｌ中心（Ｗ ｅ、…ｂｕ三Ｄ ：ＤＩ）注册并发布。 ¨ ”，企业用户借助ＷＳＤＬ麓 曲服务鎏 描 ［３］ＯＩ７１ ｋ￣ＩＰ］） ．王卫所需访问的分析服务，利用ＳＯＡＰ协议向注册中心发 网络 研究［Ｊ］平， 莩： 基于ｗ。ｂ ｓ。ｎ，ｉ。 。 的商务智能 九 ．计算机系统应用，２００６（７）：１６．１９． ４结束语 夏 ．的研究及发展趋势 模地应用了商务智能…。里 ”。～，２００６年中国ＢＩ软件市场规模 、 行 妻 ［８］ 霎 ｎ ｍｏｎＨ ： ａｔ ｗ ｈ术、构架和应。 。（ｓ。。 川‘。 ｄ Ｅｄｉ ． 将超过１６亿元人民币，成为了中国软件市场的一大 ｔｉ。 ）『Ｍ１．Ｊ。ｈ ｗｉｌ。 ＆Ｓｏ ｓ，Ｉ 。．，№ Ｙ。ｒｋ，１９９６． 亮点。全球ＢＩ市场，新许可证的销售收入超过了２３ ［９］巩曙平．商业智能软件ＩＴ产业突起的黑马［Ｊ］．中国科 （上接第３１页） 路径长度可能较长，而对于估价函数ｆ＝ｇ＋ｈ，虽 ５ 结束语 然要花费较多的时问 但可得到较短的从初始状态到 本算法主要是用Ａ 算法来求八数码问题的解， 目标状态的路径。在实际中可根据需要选择合适的 并针对八数码这个具体问题进行了优化，对没有路径 估价函数。 的情况事先作了判断，并改进了Ｏｐｅｎ表和Ｃｌｏｓｅｄ表， 将初始状态１、初始状态２、初始状态３输入到改 通过大量的实验证明，本算法提高了程序执行的效 进前算法和改进后算法实现的的程序中得到的性能 率。此外，本程序还设计了灵活的估价函数，通过分 参数如表２所示（此时取估价函数ｆ＝ｇ＋ｈ）。 析不同估价函数对程序效率的影响，为实际中估价函 表２算法改进前后消耗资源比较 数的选择提供了参考依据。 改进前 改进后 初始状态 初始 初始 初始 初始 初始 初始 参考文献： 状态１ 状态２ 状态３ 状态１ 状态２ 状态３ ［１］蔡自兴，徐光佑．人工智能及其应用［Ｍ］．北京：清华大 路径长 １６ ２０ 无路径 １６ ２０ 无路径 学出版社，２００４． 度（步） ［２］ 马少平，朱小燕．人工智能［Ｍ］．北京：清华大学出版 搜索时 间（．８） ＜１ ８ ２８１Ｏ７ ＜１ ５ ＜１ 社．２００４． ［３］尼尔逊Ｎ Ｊ．人工智能原理［Ｍ］．北京：科学出版社， 其中，对于初始状态３，在这种情况下找不到从 １９８３． 初始节点到目标节点的路径，假如不用事先判断而用 ［４］ Ｎｉｍｖａｎ Ａｎｓａｆｉ，Ｅｄｕｗｉｎ Ｈｏｕ．用于最优化的计算智能 改进Ｏｐｅｎ表和Ｃｌｏｓｅｄ表的方法来查找路径，需要 ［Ｍ］．李军，边肇祺译．北京：清华大学出社，１９９９． ９７５７ｓ能得到找不到路径的结论，这也大大优于算法 ［５］霍顿．Ｖｉｓｕａｌ Ｃ＋＋２００５入门经典［Ｍ］．李颂华，康会光 改进前的需要２８１０７ｓ时的效率，这也证明了本方法 译．北京：清华大学出社，２００７． 的优越性。 ［６］求是科技，王正军．Ｖｉｓｕａｌ Ｃ＋＋６．０程序设计从入门到 精通［Ｍ］．北京：人民邮电出版社，２００６．
