Ｓ０ＦｒＷＡＲＥ ＤＥＶＥＬ０ＰＭＥＮＴ ＡＮＤ ＤＥＳＩＧＮ 软件开发与设计 基于八数码游戏的两种搜索策略比较 俞露。许建华 （南京师范大学计算机科学与技术学院，南京２１００ｏ０） 摘要：利用状态空间法描述八数码问题，将其抽象成为一个从起始状态搜索到达目标状态的路径的问题，并在 Ｖｉｓｕａｌ ｃ＋＋６．０环境下，用Ｃ＋＋语言实现了其盲目搜索和启发式搜索算法。其中，盲目搜索采用的是宽度搜索和深度 搜索，启发式搜索策略采用的是有序搜索。通过比较两种搜索策略的时间复杂度和空间复杂度，在搜索步骤较多的 情况下，启发式搜索具有明显的优势，并在此结论的基础上分析了启发式搜索具有优势的原因。 关键词：八数码；搜索策略；盲目搜索；启发式搜索 Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｔｗｏ Ｓｅａｒｃｈ Ｓｔｒａｔｅｇｉｅｓ Ｂａｓｅｄ ｏｎ Ｓｕｄｏｋｕ Ｇａｍｅ ＹＵ Ｌｕ，ＸＵ Ｊｉａｎ－ｈｕａ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｓａｎｊｉｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｓａｎｊｉｎｇ，２１００００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｕｓｅｓ ｓｔａｔｅ－ｓｐａｃｅ ｍｅｔｈｏｄ ｔｏ ｄｅｓｃｒｉｂｅ Ｓｕｄｏｋｕ ｐｒｏｂｌｅｍ ｗｈｉｃｈ ｉｓ ａｂｓｔｒａｃｔｅｄ ａｓ ａ ｓｅａｒｃｈ ｐａｔｈ ｐｒｏｂｌｅｍ ｆｒｏｍ ｉｔ＂ｓ ｉｎｉｔｉａｌ ｓｔａｔｅ ｔｏ ｉｔ＂Ｓ ｔａｒｇｅｔ ｓｔａｔｅ．Ｉｎ Ｖｉｓｕａｌ Ｃ＋＋６．０ ｅｎｖｉｒｏｎｍｅｎｔ．ｔｈｅ ｂｌｉｎｄ ｓｅａｒｃｈ ａｎｄ ｈｅｕｒｉｓｔｉｃ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｒｅａｌｉｚｅｄ ｕｓｉｎｇ Ｃ＋＋ｌａｎｇｕａｇｅ．Ｔｈｅ ｂｌｉｎｄ ｓｅａｒｃｈ ａｄｏｐｔｓ ｔｈｅ ｗｉｄｔｈ ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ ａｎｄ ｔｈｅ ｄｅｐｔｈ ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ．ｔｈｅ ｈｅｕｒｉｓｔｉｃ ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ ａｄｏｐｔｓ ｏｒｄｅｒ ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ．Ｂｙ ｃｏｍｐａｒｉｎｇ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｓｐａｃｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｔｗｏ ｋｉｎｄｓ ｏｆ ｓｅａｒｃｈ ｓｔｒａｔｅｇｉｅｓ，ｉｎ ｔｈｅ ｃｏｍｐｌｅｘ ｃａｓｅ，ｈｅｕｒｉｓｔｉｃ ｓｅａｒｃｈ ｈａｓ ｏｂｖｉｏｕｓ ａｄｖａｎｔａｇｅ．Ａｌｓｏ，ｔｈｉｓ ｐａｐｅｒ ａｎａｌｙｚｅｓ ｔｈｅ ｓｏｕｒｃｅｓ ｏｆ ａｄｖａｎｔａｇｅｓ ｂａｓｅｄ ｏｎ ｔＩｌｅ ｃｏｎｃｌｕｓｉｏｎ． Ｋｅｙ ｗｏｒｄｓ：Ｓｕｄｏｋｕ；ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ；ｂｌｉｎｄ ｓｅａｒｃｈ；Ｈｅｕｒｉｓｔｉｃ ｓｅａｒｃｈ 八数码游戏（也称九宫格问题）是一个经典的智力小游 戏，即在一个３ｘ３的棋盘里摆放着８个写着数字的棋子，留 下一个空位。与空位相邻的棋子可以滑动到空位中。玩家需 要移动棋子，让棋盘从初始状态达到目标状态。 （５）把ｎ的所有后继节点放到ＯＰＥＮ表的末端，并提供 从这些后继节点回到ｎ的指针。 （６）如果ｎ的任一个后继节点是个目标节点，则找到一 个解（反向追踪得到从目标节点到起始节点的路径），成功退 １状态空间法表示 采用一维数组的方式存储每一步的状态，空位用０表示。 例如：某一时刻的状态为： ２ １ ７ ８ Ｏ ６ ３ ４ 出，否则转向第②步。 —５ （二 ＝二） 用一个一维数组加以表示： ｉｎｔ ａｒｔ【９】＝｛２，８，３，ｌ，０，４，７，６，５｝ 二 ＝＝） ２八数码游戏的盲目搜索技术 ２．１宽度优先搜索 以接近起始节点的程度依次扩展节点．先扩展出来的节 点随后优先被扩展（生成其所有的后继节点）。 ２．１．１算法描述 如图１所示。 是一厂— 广］ 、 －．．．．．．．．．．．．．．，．／ （１）把起始节点放到ＯＰＥＮ表中ｆ如果该起始节点为一目 标节点，则得到解）。 （２）如果ＯＰＥＮ为空表，则无解，失败退出，否则，继 续下一步。 图１ 作者简介：俞露（１９９２一），女，本科，研究方向：嵌入式： 许建华（１９６４一），男，教授，研究方向：模式识别、神经 网络。 （３）把第一个节点（记作节点ｎ）从ＯＰＥＮ表移出，并把 它放入ＣＬＯＳＥＤ表中。 （４）扩展节点ｎ，如果没有后继节点，则转向第②步。 收稿日期：２０１３—０２—１６ 淼 电脑编程技巧与维护 ２．２深度优先搜索 沿着一条路径进行下去，直到深度界限为止．每次扩展 的节点加到０ＰＥＮ表的最前面。 ２．２．１算法描述 （１）把起始节点Ｓ放到未扩展节点的ＯＰＥＮ表中（如果 此节点为一目标节点，则得到解）。 （２）如果ＯＰＥＮ为空表，则无解，失败退出。 （３）把第一个节点（记作节点ｎ）从ＯＰＥＮ表移到ＣＬＯＳ ＥＤ表中。 （４）如果节点ｎ的深度等于最大深度，转向②。 （５）扩展节点ｎ，产生其全部后继节点，并把它们放人 ＯＰＥＮ表的前头。如果没有后继节点，则转向②。 （６）如果后继节点中有任一个节点为目标节点，则求得 一个解（反向追踪从目标节点到起始节点的路径），成功退 出；否则，转向②。 ２＿２．２算法流程图 如图２所示。 ＿弄 ］ 目 是 二 ］ 是 》一是一［ ］ 把ＯＰＥＮ表中第一个节 点Ｎ移人ＣＬＯＳＥ表中 是———＜： 点Ｎ的深度是 扩展节点Ｎ．把它的后继 结点放人ＯＰＥＮ表的前 端．提供回到Ｎ的指针 戛售 蓦誊 为日标结点／ ～Ｌ是 二 图２ ３八数码游戏的启发式搜索技术 利用启发信息来引导搜索，对待扩展的节点进行排序，选 择最有希望的节点加以扩展，即优先扩展估价函数值小的节点。 估价函数：ｆ（ｎ）＝ｇ（ｎ）＋ｈ（ｎ） ｆ（ｎ）：表示节点ｎ的估价函数值，是从起始节点通过节点 ｎ到达目标结点的最小代价路径上的一个估算代价 ｇ ｎ）：表示搜索树中节点ｎ的深度 ｈ ｆｎ１：节点ｎ的状态与目标状态之间数码错位的个数 算法描述： （１）把起始节点Ｓ放到ＯＰＥＮ表中，计算ｆ（Ｓ）。 （２）如果ＯＰＥＮ表是个空表，则无解，失败退出；否则 ２０１３．１０ 电麓臁技巧 与壤 继续。 （３）从ＯＰＥＮ表中选择一个ｆ值最小的节点作为代扩展节 点ｉ。如果有几个节点同时最小，当其中有一个目标结点时，选 择此目标结点，否则就选择其中任一个节点作为带扩展节点ｉ。 （４）把节点ｉ从ＯＰＥＮ表中移出放入ＣＬＯＳＥ表扩展节点 表中。 （５）如果ｎ是目标节点，问题得解，退出。否则继续。 （６）扩展节点ｉ，生成其全部后继节点。对于ｉ的每一个 后继节点ｉ。 １）计算ｆ（ｉ）。 ２）如果ｉ既不在ＯＰＥＮ表中，又不在ＣＬＯＳＥＤ表中，则 用估价函数ｆ把它加入ＯＰＥＮ表相应位置。从ｉ加一个指向其 父辈节点ｉ的指针，以便于反向追踪解的路径。 ３）如果ｊ已在ＯＰＥＮ表（处理与父节点的关系）或 ＣＬＯＳＥＤ表（处理与父节点和子节点的关系）中，则比较新的 ｆ（Ｊ）值和前面计算出来的ｆ（ｊ）值。如果新的ｆ（ｊ）值 较小．则 ①用新的值取代旧的值。 ②改变指针，从ｊ指向ｉ，删除原来的父辈节点指针。 ③如果节点ｊ在ＣＬＯＳＥＤ表中，则把它移回ＯＰＥＮ表 （意味着：扔掉原来的子节点）。 （７）转向②。 算法流程图如图３所示。 ～～～…～一一置……～…～～ 扩艟爷点ｔ，得到后继节点 ｊ，捉ａ 返 【的指引，利｝ ｆＵ）对ＯＰＥＮ丧簸新摊搿．鞫 整亲子戈系及指针 用供价函数ｆ￣＇ＥｊＤｒｉ入 ＯＰＥＮ袭的榭麻俺臀 图３ ４结语 步骤不多时，利用宽度搜索、深度搜索、有序搜索３种 搜索策略解决八数码问题，３种搜索算法的搜索的时间接近 ０ｍｓ。在测试步骤较多的例子时（如搜索步骤为７时），可以 发现宽度搜索、深度搜索、启发式搜索的ＣＰＵ耗时依次降低。 （下转第１９页） ＳＯＦＩＷＡＲＥ ＤＥＶＥＬＯＰＭＥＮＴ ＡＮＤ ＤＥＳＩＧＮ 软件开发与设计 易错字练习：学习者可以专门针对易错字进行练习，系 码的汉字笔画数据库支持中小学语文的汉字笔画教学，丰富 统会根据易错字的出错频率从高到低抽取练习，不仅可以抽 语文汉字笔画教学的资源，方便教师教学、学生学习以及纠 取学习者自己的易错字还可以抽取其他学习者的易错字。 正自己的汉字笔画书写的不良习惯，从而对我国汉字笔画书 试卷练习模块：系统随机抽取试卷，学习者在系统规定 写顺序的传承起到保护的作用。 时间内进行测试，交卷后系统自动评定成绩。成绩分为优秀、 参考文献 良好、中等、及格、不及格４个等级。数据库只记录练习过 ［１】高更生．现行汉字规范问题【Ｍ１．北京商务印书馆， 程中的易错字不记录练习的成绩。 ２００６，１０． 试卷测试模块：学习者测试后，数据库不只记录测试过 ［２】林民，韩冬妹，宋柔．基于ＧＤＩ＋路径技术的汉字笔顺和 程中的易错字并且记录测试的成绩，可以用于汉字笔画书写 部件自动绘制［Ｊ】．计算机应用研究，２００７，２４（８）： 顺序等级测试。 ２２８－２３０． ４结语 ［３】赵希武，吕生荣．小学汉字书写笔画顺序练习系统的设计 论述了基于计算机的汉字笔画顺序纠错模型的设计与实 ［Ｊ】．内蒙古农业大学学报（自然科版），２０１０，３１（１）： 现．并面向应用设计了基于计算机模拟人的手写过程的汉字 ２３６－２４０． 笔画顺序书写练习与纠错系统，可以在国家大政方针的指导 ［４］王素坤，赵希武．计算机辅助汉字笔顺书写的研究［Ｊ】． 下 加强汉字书写的训练，为高校学生（特别是师范院校的 内蒙古师范大学学报（自然科版），２０１０，３９（４）：４２８— 学生）以及即将上岗的教师、 文秘、记者等进行岗前汉字书 ４３２． 写的一项指标测试提供服务 。 同时通过建立基于笔画顺序编 （上接第１６页） 表４ 综合考虑时间和空间的复杂度，评价３种搜索算法的效 搜索步骤为７ ０ＰＥＮ表大小 Ｃ【ＤＳＥＤ表大小 ＣＰＵ耗时（ｍｓ） 率：宽度搜索＜深度搜索＜启发式搜索，其中启发式搜索具有 宽度搜索 ７２ ９５ １０ 很明显的优势。 深度搜索 ４ １２９ ２ 表１ 搜索步骤为１ ０ＰＥＮ表大小 ＣＬＯＳＥＤ表大小 ＣＰＵ耗时（ｍｓ） 有序搜索 １１ １ｌ Ｏ 宽度搜索 ３ ｌ ０ 启发式搜索技术较盲目搜索技术具有优势的主要原因是 深度搜索 ３ １ ０ 引入了启发信息，而启发信息在以下３个作用： 有序搜索 ２ ２ Ｏ （１）启发信息决定了要扩展的下一个节点，避免宽度优 表２ 先或深度优先搜索中的盲目（人为规定）地选择扩展节点。 搜索步骤为４ ＯＰＥＮ表大小 ＣＬＯＳＥＤ表大小 ＣＰＵ耗时（ｍ） （２）扩展一个节点的过程中，启发信息用于决定要生成 宽度搜索 ｌ１ １６ Ｏ 哪一个或哪几个后继节点，避免盲目地同时生成所有可能的 深度搜索 ３ ２３８ Ｏ 后继节点。 有序搜索 ６ ６ ０ （３）启发信息决定了某些应该从搜索树中抛弃或修剪的 表３ 节点。 搜索步骤为５ ＯＰＥＮ表大小 ＣＬＯＳＥＤ表大小 ＣＰＵ耗时（Ｉｌｌｓ） 参考文献 ［１１】 蔡自兴，徐光佑．人工智能及其应用［Ｍ】．北京：清华 宽度搜索 ２８ ３３ Ｏ 大学出版社．２０１１：３３—９４． 深度搜索 ５ ５ ０ 有序搜索 ８ ８ ０ （上接第７页） 而探究构造函数的调用．有利于更进一步地理解类机制的运 程序运行的结果是：Ｂａｓｅｌ Ｓ ｃｏｎｓｔｒｕｔｏｒ，Ｂａｓｅ２ Ｓ ｃｏｎｓｔｒｕｃｔｏｒ，Ｄｅ— 行过程。 ｉｒｖｅｄ Ｓ ｃｏｎｓｔｒｕｃｔｏ 参考文献 ３结语 ［１】钱能．Ｃ＋＋程序设计教程．２版．北京：清华大学出版社， 构造函数是Ｃ＋＋类机制的重要组成部分，用来初始化对象 ２００５． 的数据成员，通过探究构造函数的一些作用。特别是默认构 【２】谭浩强．Ｃ＋＋程序设计．北京：清华大学出版社，２００４． 造函数、拷贝构造函数以及具有赋值和转型功能的构造函数 ［３】余苏宁，王明福．Ｃ＋＋程序设计．北京：高等教育出版社， 的一些作用，有利于在学习和编程过程中更好的运用类机制。 ２００３