２０１１年２月 渭南师范学院学报 Ｆｅｂ．２０１１ 第２６卷第２期 Ｊｏｕｒｎａｌ ｏｆ Ｗｅｉｎａｎ Ｔｅａｃｈｅｒｓ Ｕｎｉｖｅｒｓｉｔｙ Ｖ０１．２６ Ｎｏ．２ 基于迷宫问题的算法新解 遇娜 （天津市红桥区职工大学，天津３００１３１） 摘要：文章从分析深度优先探测法的设计思路入手，得出了该方法的优缺点，并针对其缺点提出了一个基于八方向 跟踪算法的新方法，并详细介绍了该方法的设计思路及求解方法．不仅为计算机解题提供了一个快捷的算法，也为人工和 机器人破解提供了一个无需记忆的便捷方法． 关键词：迷宫；深度优先算法；探测法；八方向跟踪算法 中图分类号：ＴＰ３０１．６ 文献标志码：Ａ 文章编号：１００９—５１２８（２０１１）０２—０ｏ６６—０３ 收稿日期：２０１０—１２－－０３ 作者简介：遇娜（１９７７一），女，天津人，天津市红桥区职工大学讲师，硕士，研究方向：计算机教学． ０引言 迷宫问题是图论、数据结构等领域中的一个经典问题，源自一个心理学的一个古典实验，在实验中把 一只老鼠从一个无顶大盒子的门放人，在盒子中置了很多墙，盒子仅有一个出口，在出口放置一块奶酪，吸 引老鼠在迷宫中寻找道路以到达出口．这就是我们现在很多人研究的迷宫问题，方法很多，如递归算法、 遗传算法、回溯算法等，但大多数方法都需要记住走过的每一步，以免重复或进入死循环，实现过程比较复 杂．本文介绍的是一种基于八方向的跟踪算法，该算法是一种无需记忆的简便快捷的新方法． １迷宫问题的经典解法 １．１ 构造迷宫 首先用一个二维数组ｍａｚｅ［ｉ］［ｊ］表示一个Ｍ Ｎ迷宫，其中１≤ｉ≤ｍ，１≤ｊ≤ｎ，数组元素值为１是表 示该位置是墙壁，不能通行；元素值为０时表示该位置是通路，假设从ｍａｚｅ［１］［１］出发，出口位于ｍａｚｅ ［ｍ］『ｎ］，移动方向可以是８个方向（东、东南、南、西南、西、西北、北和东北），构造迷宫…如图１所示： ０ １ ０ ０ ０ ｌ １ ０ ０ ０ １ ｌ ｌ ｌ ｌ １ Ｏ Ｏ ０ １ １ Ｏ １ １ ｌ ０ Ｏ １ １ ｌ ０ ｌ ｌ Ｏ Ｏ ０ ０ １ １ ｌ １ ０ Ｏ １ ｌ １ １ Ｏ １ ｌ ｌ １ ０ ｌ ｌ ０ １ １ ０ ０ １ ｌ Ｏ ｌ Ｏ Ｏ １ Ｏ ｌ １ １ ０ １ １ ０ ０ ０ １ ｌ Ｏ １ １ ｌ Ｏ １ １ Ｏ ｌ ０ ０ Ｏ １ １ ｌ ｌ ０ ０ ｌ １ ｌ ０ ｌ ｌ １ ｌ Ｏ Ｏ １ ｌ Ｏ ｌ ｌ ０ １ １ １ ｌ １ ０ １ ｌ １ Ｏ ０ Ｏ ｌ ｌ ０ １ １ ０ ０ ０ ０ ０ ０ ０ １ １ １ １ ｌ Ｏ ０ Ｏ １ ｌ １ １ ０ Ｏ ｌ Ｏ Ｏ １ １ ｌ ｌ １ ０ １ ｌ ｌ １ ０ 口 图１迷宫图 １．２设计思想 迷宫中的任一位置可由数组的行、列序号ｉ、ｊ来表示，而从［ｉ］［ｊ］位置出发，可能行进的方向有如下情 况：若［ｉ］［ｊ］周围位置均为０值，则可选８个位置中的任一个作为下一方向，将这８个方向分别记为Ｅ （东）、ＳＥ（东南）、Ｓ（南）、ｓｗ（西南）、Ｗ（西）、ＮＷ（西北）、Ｎ（北）、ＮＥ（东北），但并非每一个位置都有８个 相邻的位置，如果［ｉ］［Ｊ］位于边界上，即ｉ＝１或ｉ＝ｍ，ｊ＝１或ｊ＝ｎ，则相邻位置可能是３个或５个，为了避 免检查边界条件，将数组四周用值为１的边框包围起来．由于迷宫中［ｉ］［ｊ］有多个行进方向可选，这里我 ２０１１年第２期 遇娜：基于迷宫问题的算法新解 ・６７－ 们规定搜索的次序是从东（Ｅ）沿顺时针方向进行，为了简化问题，规定［ｉ］［Ｊ］的下一步位置的坐标是［Ｘ］ ［Ｙ］，并将这８个方位上的ｘ、Ｙ坐标的增量预先放在一个结构数组ｍｏｖｅ［８］中，该数组的每个分量有两个 域ｄｘ和ｄｙ，例如要向东走，只要在Ｊ值上加上ｄｙ就可以得到下一步位置的［Ｘ］［Ｙ］值为［ｉ］［ｊ＋ｄｙ］，搜索 方向的变化只要令方向值ｄｉｒ从０增至７便可以从ｍｏｖｅ数组中得到从［ｉ］［ｊ］点出发搜索到得每一个相邻 点［Ｘ儿ｙ］，为了防止重复走原路，规定已经走过的位置将原值０改为一１，当整个搜索结束时再将所有的 一１改回０，从而恢复迷宫的原样．也就是说，在某个方位上的ｍａｚｅ［Ｘ］［ｙ］＝０表示可通行，按照顺时针 的原则走一步，若ｍａｚｅ［Ｘ］［Ｙ］＝１表示不可通行，须换个方向再试，直至８个方向全试完，说明无路可走， 需退一步，在上一步的下一个方向重新开始探测，因此需设计一个栈来记录所走过的位置和方向 （ｉ，Ｊ，ｄｉｒ）．当退一步时，就从栈中退出一个元素，以便在上一个位置的下一个方向上探测，如又找到新的行 进方向，则把当前位置和新方向重新进栈，并走到新的位置．如果探测到Ｘ＝ｍ，Ｙ：ｎ，则已经到达迷宫的 出口，可以停止检测，输出存在栈中的路径，若在某一位置的８个方向上都堵塞，则退回上一步，继续探测， 如果已退到迷宫的人口，则表示此迷宫无路径可通行． １．３优缺点分析 上述解法的核心是采用深度优先的探测方法，按照顺时针顺序对８个方向进行一步一步的探测，直至 找到迷宫的出口．迷宫之所以被称为是迷宫，是因为对刚进入迷宫的个体而言是未知的，不知通路在何 方，因此用深探法来搜索通路更加合适．尽管深探法不能保证找出最佳路径，但对于走出迷宫为目的的迷 宫求解，能找到出口已经足够了．但是，深探法的每步一记对计算机而言不是什么难事，但对一个变化复 杂的迷宫来说，记忆堆栈到底需要多大？要想给出一个精确的答案恐怕也是棘手的问题．若是一个迷宫 无法数字化，边走边记的方法就更难实现了．现实中的迷宫往往是没有数字化的，甚至是无法数字化的， 若由人或机器人来走迷宫，那就更困难了，因此，有必要对深探法加以改进 基于八方向跟踪算法的迷宫 问题求解就是在此基础上提出来的． ２八方向跟踪算法 ２．１ 显艮踪准则 一般情况下，物体在灰度图像中呈现两种形态：其一为物体亮，背景暗，即物体的灰度比背景高；其二 为物体暗，背景亮，即物体的灰度比背景低．但迷宫可以用二值图像来表示，若０代表通路，１代表障碍 物，则在迷宫跟踪时，物体（迷宫）是暗的，符合物体的第二种形态，故有如下跟踪准则： Ｖ≤Ｔｇｒａｙ＝０ （１） 其中Ｖ为被跟踪点的灰度值，Ｔｇｒａｙ为跟踪的灰度门限．由于是二值图像，灰度值非０即１，故跟踪 准则中的“≤”也可以改为“＝”，此时，跟踪准则可改作： Ｖ＝０ （２） 即判断被跟踪点是否为通路． ２．２ 方向图 跟踪时 还需要一个指导跟踪方向的方向图，八方向跟踪法的方向图如图２所示．根据该方向图， 以（１）式或（２）式为准则，就可进行八方向跟踪． ２．３跟踪算法 （１）跟踪原则．八方向跟踪的原则是：若满足准则，则前 进一步，并向左转９０。开始试探下一步（此举确保跟踪在最外 层），若不满足准则，则按八方向顺时针试探，即每步向右转 ４５。，直至满足准则．简而言之，是通路前进并向左转９Ｏ。，是 障碍物向右转４５Ｏ． （２）跟踪算法．根据以上原则，并结合图１所示的迷宫， 可以得到如下算法． 步骤１：根据迷宫人口选择跟踪起始点和进入的初始方 向． 步骤２：以（２）式为准则，判断被跟踪点是否为通路；若满 足准则，则在图２所示的方向图中按逆时针走向走两格试探 （ｉ＋ｉ，ｊ＞ 选择下一点，即当前的走向Ｄｉ与下一点可能的走向Ｄｉ＋１ 图２八方向跟踪算法的方向图 －６８・ 渭南师范学院学报 第２６卷 有如下式所示的关系： Ｄｉ＋１＝Ｍｏｄ（Ｄｉ＋２，８） （３） 上式中的函数Ｍｏｄ（Ｘ，Ｙ）代表求Ｘ对ｙ的余数． 步骤３：若Ｄｉ＋１指向的那一点满足准则，则该点为下一点，转步骤４；否则按顺时针走向走一格继续 试探选择下一点，即将Ｄｉ＋１代入下面（４）式的Ｄｉ中，重复步骤３． Ｄｉ＋１＝Ｍｏｄ（Ｄｉ＋７，８） （４） 步骤４：当前跟踪点是否走到迷宫出口，即是否满足结束条件；若是，则结束跟踪；否则转步骤２，继续 跟踪． （３）跟踪结果表示．八方向跟踪算法的跟踪结果用Ｆｒｅｅｍａｎ链码来表示，它是一串跟踪时走通过程的 方向码． ２．４左跟踪和右跟踪 上面描述的八方向跟踪算法始终沿着图形边界的左边走，故称之为左跟踪，与之相反的应该还有右跟 踪．可想而知，只要在算法１中将（３）式和（４）式分别改为： Ｄｉ＋１＝Ｍｏｄ（Ｄｉ＋６，８） （５） 和 Ｄｉ＋１＝Ｍｏｄ（Ｄｉ＋１，８） （６） 并且顺时针和逆时针对调，即可实现右跟踪． ３ 用八方向跟踪算法求解迷宫问题 （１）用左跟踪算法求解．现在用左跟踪方法，以从左上角进入，开始跟踪，经过如下Ｆｒｅｅｍａｎ链码所示 的７３步：｛２１３２２７０２２３３２２１２１ １ １２００６３５５６７１０７３４５３５５６６７０１０１５４５６６６７０７１ １２３３５４２７１２１０１２３２２３１００｝．从迷 宫的右下角走出谜宫． （２）用右跟踪算法求解．若用右跟踪方法，同样从左上角进入，开始跟踪，只要经过Ｆｒｅｅｍａｎ链码所示 的４０步｛２１７３２１７０７６００２１７６０３１２６５３２２４３２１００２１４３２２２１０｝． ４ 结论 本文从迷宫问题人手，分析了传统求解迷宫问题经典的深度优先探测法的设计思路及优缺点，并针对 深探法的弊端给出了迷宫问题的另外一种求解算法——八方向跟踪算法，并通过理论和实际论证该算法 实现简便，求解过程无需过多记忆（需要给出通路除外），避免了深探法的诸多问题，特别适合机器人和 人类破解迷宫． 参考文献： ［１］严蔚敏，吴伟民．数据结构（Ｃ语言版）［Ｍ］．北京：清华大学出版社，１９９６．８５—９０． ［２］廖国勇，王广超．用遗传算法解迷宫问题［Ｊ］．华东交通大学学报，２００６，（２）：１３８—１４０． ［３］涂海丽．求迷宫中从入口到出口的路径的算法及实现［Ｊ］．中国科技信息，２００８，（２３）：５４—５６． ［４］朱素英．迷宫问题的图论解法探讨［Ｊ］．湖南人文科技学院学报，２００６，（３）：７３—７５． ［５］孙秋冬．基于八方向跟踪算法的迷宫问题新解［Ｊ］．计算机应用与软件，２００５，（８）：１０３—１０５． ［责任编辑牛怀岗］ Ｔｈｅ Ｎｅｗ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ ｔｈｅ Ｍａｚｅ Ｐｒｏｂｌｅｍ ＹＵ Ｎａ （Ｔｉａｎｊｉｎ Ｈｏｎｇｑｉａｏ Ｄｉｓｔｉｒｃｔ Ｓｔａｆｆ ａｎｄ Ｗｏｒｋｅｒｓ Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉｎ ３００１３１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｂｙ ａｎａｌｙｚｉｎｇ ｔｈｅ ｄｅｐｔｈ—ｆｉｒｓｔ ｅｘｐｌｏｒａｔｉｏｎ ｏｆ ｄｅｓｉｇｎ ｉｄｅａｓ，ｔｈｅ ｐａｐｅｒ ｏｂｔａｉｎｓ ｔｈｅ ａｄｖａｎｔａｇｅｓ ａｎｄ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｉｓ ｍｅｔｈｏｄ，ａｎｄ ｆｏｒ ｉｔｓ ｓｈｏｒｔｃｏｍｉｎｇｓ ｉｔ ｐｒｏｐｏｓｅｓ ａ ｎｅｗ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｄｉｒｅｃｔｉｏｎ ｏｆ ｅｉｇｈｔ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｏ ｄｅｓｃｒｉｂｅ ｉｎ ｄｅｔａｉｌ ｔｈｅ ｄｅｓｉｇｎ ｉｄｅａ ｏｆ ｔｈｅ ｍｅｔｈｏｄ ａｎｄ ｉｔｓ ｓｏｌｕｔｉｏｎ．Ｉｔ ｐｒｏｖｉｄｅｓ ａ ｑｕｉｃｋ ｐｒｏｂｌｅｍ—ｓｏｌｖｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｃｏｍｐｕ￣ｒ ａｎｄ ａｌｓｏ ｐｒｏｖｉｄｅｓ ａ ｃｏｎ— ｖｅｎｉｅｎｔ ｍｅｔｈｏｄ ｗｉｔｈｏｕｔ ｍｅｍｏ￣ｆｏｒ ａｒｔｉｉｆｃｉａｌ ｃｒａｃｋｉｎｇ ａｎｄ ｒｏｂｏｔ ｃｒａｃｋｉｎｇ． Ｋｅｙ ｗｏｒｄｓ：ｍａｚｅ；ｄｅｐｔｈ—ｆｉｓｒｔ ａｌｇｏｒｉｔｈｍ；ｄｅｔｅｃｔｉｏｎ ｍｅｔｈｏｄ；ｅｉｇｈｔ ｄｉｒｅｃｔｉｏｎ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ
