（计算机应用技术专业论文）基于启发式搜索算法的地图寻径的研究.pdf

摘要 摘要 随着计算机技术及因特网技术在中国的发展，中国游戏产业逐渐形成规模。 尤其是这几年，国家提倡电脑游戏软件的自主研发，因此各种游戏引擎软件中的 技术和算法成为了人们研发的热点，其中地图寻径算法是游戏引擎软件中最重要 的算法之一。最常用的地图寻径算法是一种启发式搜索算法 ，i c 算法。而传统 的a 木算法在数据结构优化方面没有做足够的研究，因此在这方面还有优化的余 地。其次，各种对a 木算法的研究过于理论化，而将a 水算法实际的使用在项目当 中的研究极少，这也是地图寻径算法研究的一个欠缺。 本文针对以上所述的两点不足进行了研究和探讨。首先，通过设计算法演示 程序研究了a 水算法在地图寻径中的执行过程，对其整个过程中的各种操作进行 了详细分析，针对分析结果提出了几种数据结构的设计，并将新设计的数据结构 用于算法当中，通过算法的执行，对各种优化结果做比较，得到最优的数据结构 设计。其次，本文将抽象的胁算法实例化，对算法进行适应实际应用的扩展， 并对实际中出现的各种问题进行研究和探讨，设计出相应的解决方案，并设计一 个小型的演示程序，使优化后的胁算法应用于实际的地图寻径中，实现真实的 地图寻径程序，对理论做出验证，达到本文所提出的目标，弥补目前对这方面研 究的欠缺，对后人有一定的借鉴意义。， 关键词启发式搜索；地图寻径；胁算法 a b s t r a c t 曼曼皇蔓曼皇鼍皇曼鼍曼曼! 皇曼曼曼曼! 曼i | 一 i 鼍曼曼曼! ! 曼皇鼍! 曼蔓曼! 量曼寰! 皇 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n dt h ei n t e r a c tt e c h n o l o g yi n c h i n a , t h ec h i n e s ec o m p u t e rg a m ei n d u s t r yf o r m st h es c a l eg r a d u a l l y e s p e c i a l l yi i l r e c e n ty e a r s 。n a t i o n a la d v o c a t ec o m p u t e rg a m e ss o f h n a r e si n d e p e n d e n tr e s e a r c h ， t h e r e f o r et h ea l g o r i t h m si nt h eg a m ee n g i n es o f t w a r eh a v eb e c o m et h ef o c u sw h i c h t h ep e o p l er e s e a r c h ，t h em a pp a t hf i n d i n ga l g o r i t h mi so n eo fm o s ti m p o r t a n t a l g o r i t h m si n t h eg a m ee n g i n es o f t w a r e t h em o s tc o m m o n l yu s e dp a t hf i n d i n g a l g o r i t h mi sah e u r i s t i cs e a r c ha l g o r i t h m - a * a l g o r i t h m t r a d i t i o n a la 串a l g o r i t h m s d a t as t r u c t u r eo p t i m i z a t i o ni sn o te n o u g h ，s oi te x i s t sr o o mf o ro p t i m i z a t i o n s e c o n d l y , t h er e s e a r c ha b o u ta a l g o r i t h mi st o ot h e o r e t i c a l ，t h ea a l g o r i t h m sa p p l i c a t i o ni n t h ep r o je c ti sal a c ko fr e s e a r c h i nt h i sp a p e r , t w op o i n t sa b o v eh a v eb e e ns t u d i e d f i r s to fa l l ，t h r o u g ht h ed e s i g n a l g o r i t h md e m op r o g r a mt os t u d yt h ea a l g o r i t h m si m p l e m e n t a t i o np r o c e s s ，t h e e n t i r ec o u r s eo ft h ev a r i o u so p e r a t i o n si sc a r r i e do u tad e t a i l e da n a l y s i s ，b a s e do n a n a l y s i so ft h er e s u l t s ，t h ep a p e rd e s i g n e dan e wd a t as t r u c t u r e ，a n dp u tt h en e w d e s i g n e d d a t as t r u c t u r e si n t ot h e a l g o r i t h m a c c o r d i n g t ot h e a l g o r i t h m s i m p l e m e n t a t i o na n dt h ec o m p a r i s o no ft h ev a r i o u sd a t as t r u c t u r e s ，t h ep a p e rg o tt h e b e s td e s i g no ft h ed a t as t r u c t u r e s e c o n d l y , t h i sa r t i c l ep u tt h ea b s t r a c ta a l g o r i t h m i n t ot h ep r a c t i c a la p p l i c a t i o n , a n de x p a n dt h ea a l g o r i t h ma c c o r d i n gt op r a c t i c a l ， d e s i g n e dt h ec o r r e s p o n d i n gs o l u t i o n s ，a n dd e s i g n e das m a l ld c m op r o g r a m ，s ot h a tt h e o p t i m i z e da a l g o r i t h mi sa p p l i e dt ot h ea c t u a lp a t hf i n d i n g ，v e r i f yt h et h e o r y , a c h i e v e t h eo b j e c to ft h i sp a p e r , m a k eu pt h el a c ko fr e s e a r c hi nt h i sa r e a , h a v er e f e r e n t i a l s i g n i f i c a n c ef o ro t h e rp e o p l e k e y w o r d sh e u r i s t i cs e a r c h ；m a pp a t hf i n d ；a a l g o r i t h m i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：单导师签名： 眺帮 第1 章绪论 第1 章绪论 1 1课题的背景及意义 随着计算机多媒体技术的发展，计算机游戏逐渐成为了人们数字娱乐生活中 重要的一部份。近几年，中国的计算机游戏产业逐渐发展成熟，行业已经形成了 一定的规模。但是中国的游戏软件研发能力薄弱，技术研发仍远落后于发达国家 水平。国家相关部门在最近提出了要发展民族游戏产业，通过多项措施和政策来 提倡国人的自主研发能力。因为游戏软件的本质就是多媒体技术和人工智能算法 的应用，所以这为多媒体技术和人工智能技术的发展提供了很好的发展机遇。多 媒体技术的研发和人工智能已经成为了人们研发的热点。 本课题就是关于人工智能中启发式搜索算法在地图寻径中的应用。地图寻径 问题就是人工智能搜索技术的一个重要应用领域。在图论中，寻径问题通常是人 们研究的热点问题之一 其所要解决的问题是如何设法从图中寻找到一条从起点到目标点的通路，算 法中需要解决的最基本问题是如何避开障碍物：而在游戏软件中，地图寻径问题 并非如此简单，必须考虑多方面的因素，比如算法的运行效率、动态障碍物等。 启发式搜索算法有多种，他们的搜索原理都是一样的，都是利用启发信息进行图 搜索，只是搜索的策略不同而取不同的名字。本课题中使用的是启发式搜索中最 具有代表性和效率最高的a 水算法。 本课题的研发很有意义，从大的环境来说，随着国家提倡自主研发和中国游 戏产业的成熟，游戏引擎研发中的各种技术的研发成为热点。 其次在学术研究方面有以下的意义：从算法效率方面讲，本课题将对算法原 有的未优化过的数据结构进行优化，使得算法的效率得到提高。因为游戏软件不 同于其他的应用软件，游戏软件是实时性的，对算法的效率要求很高。而原有的 胁算法中使用的数据结构需要实时的分配内存、对队列进行排序查找等操作，这 些操作随着节点的增加而变得越来越慢，算法的效率于是变得很低。本课题将使 用时间复杂度低的数据结构进行操作，这将在一定程度上提高效率，使得这个算 法更加适应于游戏软件的应用。 从应用的方面讲。把a 木算法应用到实际的地图寻径当中，会有很多实际问 题需要解决。例如游戏中电子地图是表格化的，而路径应该是像素化的，这就需 要对寻找到的路径进行细化和处理。还有一些其它问题，如地图地形的改变，动 态障碍物等问题需要处理。在这些问题上的研究较少，可借鉴的资料也不多。本 课题将对实际的应用进行研究，对各种问题进行处理。 北京工业大学工学硕士学位论文 1 2 研究现状 1 9 6 8 年，p e h a r t ，n j n i l s s o n 和b r a p h a e l 共同发表了一篇在启发式搜 索方面具有深远影响力的论文：“p e h a r t ，n j n il s s o na n db r a p h a e l af o r m a lb a s i sf o rt h eh e u r i s t i cd e t e r m i n a t i o no fm i n i m u mc o s tp a t h si n g r a p h s i e e et r a n s s y s t s c i a n dc y b e r n e t i c s ，s s c 一4 ( 2 ) ：1 0 0 1 0 7 ，1 9 6 8 。 从此，一种精巧、高效的算法斛算法诞生了，并在相关领域得到了广泛的应用。 最初斛算法被用来解决各类数学问题n ，。 随着人工智能的发展，a 木算法被用来解决寻路问题。在此之后的时间里，对 a ，i c 算法的研究和改进成为一个热门的课题。研究的兴趣主要表现在对其数据结构 的优化。主要表现在以下几个方面：对开启队列和关闭队列分别采用数组、链表 等来提高操作的效率；对内存进行提前分配来避免运行期间分配堆内存的时间； 对地图进行预处理来提高某些操作的效率等等。各种各样的优化和设计对提高算 法的效率起到了很大的作用。未排序数组或者链表使插入操作很快而集体关系检 查和删除操作非常慢。排序数组或者链表使集体关系检查稍微快一些，删除( 最 佳元素) 操作非常快而插入操作非常慢。二元堆让插入和删除操作稍微快一些， 而集体关系检查则很慢。伸展树让所有操作都快一些。h o t 队列让插入操作很快， 删除操作相当快，而集体关系检查操作稍微快一些。索引数组让集体关系检查和 插入操作非常快，但是删除操作不可置信地慢，同时还需要花费很多内存空间。 在应用方面的研究多为实际的项目设计，比如微软公司的a g e 游戏软件使用 的就是a 半算法。而纯粹的研究较少。实际中的又有些问题有一定的研究，如组 运动。一种解决方案是利用胁算法的中间状态。这个状态可以被朝着相同目标 移动的多个物体共享，只要物体共享相同的启发式函数和代价函数。当主循环退 出时，不要消除o p e n 和c l o s e d 集；用斛上一次的o p e n 和c l o s e d 集开始下一 次的循环馏1 。 1 3 研究目的及内容 本课题有两个研究目的。第一个是对算法中使用的数据结构进行重新设计和 优化，使得优化后算法的效率得到提高。第二个是对抽象的算法进行实例化研究， 使之适应于具体应用，并运用于实际的地图寻径中。 本课题研究内容是启发式搜索算法以及地图寻径。 首先引入状态空间搜索的概念。状态空间搜索，就是将问题求解过程表示为 从初始状态到目标状态的路径寻找过程。由于求解问题的过程中有很多的分支， 求解过程中存在求解条件的不确定性，不完备性，从而使得求解的路径也很多， 这就构成了一个图，我们称这个图为状态空间图。问题的求解实际上就是在这个 图中找到一条最短路径，可以从开始到结果。而这个寻找的过程就是状态空间搜 第1 章绪论 索嘲。 启发式搜索中的对启发信息的利用是用通过估价函数体现的。估价函数的任 务就是估计待搜索结点的重要程度，给它们排定次序。估价函数f ( x ) 可以是 任意一种函数，如定义它是结点x 处于最佳路径上的概率，或是x 结点和目标结 点之间的距离等等。一般来说，评价一个结点的价值，必须综合考虑两方面的因 素：已付出的代价和将要付出的代价。因此，估计函数f ( n ) 定义为从初始结 点经过n 结点到达目标结点的最小代价路径的代价估计值。它的一般形式是： f ( n ) = g ( n ) + h ( n ) 其中f ( n ) 是结点n 的估价函数，g ( n ) 是在状态空间中从初始结点到n 结点 的实际代价，h ( n ) 是从n 结点到目标结点最短路径的估计代价。其中主要是h ( n ) 体现了搜索的启发信息，因为实际代价g ( n ) 可以根据生成的搜索树实际计算 出来，而估计代价h ( n ) 却依赖于某种经验估计，它来源于我们对问题的解的 某些特性的认识，这些特性可以帮助我们更快地找到问题的解h 1 。 地图寻径问题要解决的问题是如何从图中找到一条从起点到目标点的通路。 在游戏中，人物或车辆从一个位置a 移动到另外一个位置b ，就必须找出a 到b 之间的通路，因为a b 之间的直接连线可能会穿过障碍物，而人物或车辆不能穿 透障碍物。人物或车辆的移动在游戏中又非常普遍，所以游戏地图的寻径算法就 成了游戏中一个至关重要的基础性算法。本课题是利用启发式搜索算法进行地图 寻径。 利用启发式搜索算法进行地图寻径就是把地图中的每一个瓷砖看成是一个 状态，每次移动都是从一个状态进入另一个状态。在这个状态空间图中，我们的 目的就是找到目标状态，从而完成寻径哺1 。这就是基于启发式搜索算法的地图寻 径的基本思路，也是本课题研究的主要内容。 1 4 论文的组织结构 本论文分为四章。 第一章是绪论，介绍本课题的研究背景、研究意义、研究目的以及研究内容。 第二章是对搜索算法的简介，阐述了非启发式搜索算法与启发式搜索算法的 内容，如状态空间、产生式系统、状态图示法、回溯法、宽度优先搜索、深度优 先搜索等，最后引出了本课题所使用的启发式搜索算法a 木算法，对a 术算法的基 本原理和应用情况进行了介绍。 第三章是对于a 木算法数据结构的优化问题，在这章节中，首先通过运行演示 软件来分析胁算法的执行过程，包括单步执行和正常执行，在执行结束后，记 录下来各种执行期间的数据统计，并以图表的形式反映出来。之后根据分析结果 提出两个原理并加以证明，为之后数据结构的优化提供了设计基础。接着进行数 据结构的优化。具体的优化方案是：第一，将哈希表的数据结构作为a 水算法的 北京工业大学工学硕士学位论文 o p e n 集合，使用估计值作为哈希表的关键字，采用链地址法进行冲突的处理； 第二，使用二维数组对每个结点进行标记，使得查找每个结点的集合归属运算效 率大大提高。最后，通过运行测试软件进行测试，经过多个地图多次测试后证明 之前优化方案的正确与否。 第四章是胁算法的实际应用。在这章节中，首先分析了a 术算法在具体应用 中可能会出现的问题。为了解决这些问题，在这章节中设计了协调算法。接着， 通过设计一个演示模型软件，将斛算法和协调算法运用到了实际的寻径当中， 对章节中所设计的算法进行测试，并得出测试结论。 第2 章搜索算法简介 第2 章搜索算法简介 2 1 概述 搜索技术是人工智能的基本技术之一，在人工智能各应用领域中被广泛地使 用。早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智 能程序都是以搜索为基础的。例如，a n w e l e l 和h a s i m n o 等人编写的t l ( l o g i c t h e o r i s t ) 程序，j s l a g l e 编写的符号积分程序s a i n t ，a n e w e l l 和h a s i m o n 编写的g p s ( g e n e r a lp r o b l e ms o l v e r ) 程序，h g e l e r n t e r 编写的g e o m e t r y t h e o r e mp r o v i n gm a c h i n e 程序，r p i k e s 和n n i l s s o n 编写的s t r i p s ( s t a n f o r d r e s e a r c hi n s t i t u t ep r o b l e ms o l v e r ) 程序以及a s a m u e l 编写的c h e c h e r s 程序 等，都使用了各种搜索技术。现在，搜索技术渗透在各种人工智能系统中，可以 说没有哪一种人工智能的应用不用搜索方法，在专家系统、自然语言理解、自动 程序设计、模式识别、机器人学、信息检索和博弈都广泛使用搜索技术1 。 搜索问题是a i 核心理论问题之一。一般一个问题可以用好几种搜索技术解 决，选择一种好的搜索技术对解决问题的效率很有关系，甚至关系到求解问题有 没有解。 2 2 状态空间 我们所碰到的每种问题的求解方法都需要某种对解答的搜索。不过，在搜索 过程开始之前，必须先用某种方法或某几种方法的混合来表示问题。这些表示问 题的方法，可能涉及状态空间、问题归约或谓词公式，或者把问题表示为一条要 证明的定理，等等。任何比较复杂的求解技术都离不开两方面的内容：表示与搜 索。 问题求解涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的 核心概念。在分析了人工智能研究中运用的问题求解方法之后，就会发现许多问 题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解 空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是 状态空间法，它是以状态和算符为基础来表示和求解问题的。 2 2 1 状态空间描述 首先对状态和状态空间下个定义： 状态是为描述某类不同事物间的差别而引入的一组最少变量q o ，q l ， q n 的有序集合，其矢量形式如下： q = q o ，q l ，q n 北京工业大学工学硕士掌位论文 上式中每个元素q i ( i = o ，1 ，n ) 为集合的分量，称之状态变量。给定 每个分量的一组值就得到一个具体的状态，如： q = q o k ，q l k ，q n k 使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为 走步、过程、规则、数学算子、运算符号或逻辑符号等。 问题的状态空间是一个表示该问题全部可能状态及其关系的图，它包含三种 说明的集合，即所有可能的问题初始状态集合s 、操作符集合f 以及目标状态集 合g 。因此，可把状态空间记为三元状态( s ，f ，g ) 口1 。 2 2 2 状态图示法 为了对状态空间图有更深入的了解，这里介绍一下图论中的几个术语和图的 正式表示法。 图有节点的集合构成，节点可能是有限的或无限的。一对节点用弧线连接起 来，从一个节点指向另一个节点，这种图叫做有向图。如果某条弧线从节点n i ， 指向节点n j ，那么节点n j 就叫做节点n i 的后继节点或后裔，而节点n i 叫做节 点n j 的父辈节点或祖先。在各种图中，一个节点只有有限个后继节点。一对节 点可能互为后裔，这时，该对有向弧线就用一条棱线代替。当用一个图来表示某 个状态空间时，图中各节点标上相应的状态描述，而有向弧线旁边标有算符。 如果从节点n i 至节点n j 存在有一条路径，那么就称为节点n j 是从节点n i 可达到的节点，或者称节点n j 为节点n i 的后裔，而且称n i 为节点n j 的祖先。 可以发觉，寻找从一种状态变换为另一种状态的某个算符序列问题等价于寻求图 的某一路径问题阻，。 给各弧线指定代价以表示加在相应算符上的代价常常是方便的。用c ( n i ， n j ) 来表示节点n i 指向节点n j 的那段弧线的代价。两节点间路径的代价等于连 接该路径上各节点的所有弧线代价之和。对于最优化问题，要找到两节点间具有 最小代价的路径。 对于最简单的一类问题，需要求得某指定节点，即初始状态节点与另一节点， 即目标状态节点之间的一条路径，可能具有最小代价。 一个图可由显式说明也可由隐式说明。对于显式说明，各节点及其具有代价 的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及 连接弧线的代价。 2 2 3 显式状态空间搜索 。 显式图搜索方法涉及到在图节点上传播“标记”。我们把开始节点标记为o ， 然后顺着图的边，连续传播更大的整数直至遇到目标节点。然后，顺着数字下降 序列从目标点回溯到开始节点。顺着开始点到目标点路径上的动作序列就是获得 第2 章搜索算法简介 目标应该采取的动作。这种方法需要0 ( n ) 步，n 是图中的节点数目，如果只有 一个目标节点，这个过程也可以从相反方向实现，从目标节点开始，直到某个整 数遇到了开始节点。搜索过程中放在节点上的数字可以作为该节点上的一个函 数，并且开始节点有一个全局最小值。相反路径，从目标到开始顺着这个函数的 “梯度 下降。 把标记一个节点的后继节点的过程称为扩展。扩展将标记放在所有己标记过 的节点的未标一记的相邻节点上。应将哪一个已标记但还没有扩展的节点作为下 一个扩展点是一个很重要的效率问题。在广度优先搜索中，下一个要扩展的节点 是其节点标识数不大于任何其他没有扩展的节点标识数的节点。也就是说，在扩 展标识为j 的节点之前，先要扩展标识为j 的所有节点，条件是i j 。其他搜索 算法有不同的节点扩展选择，这些将在后面详细讨论。 因此，所谓状态空间搜索，就是将问题的求解过程表示为从初始状态直到目 标状态的全过程。由于求解过程中求解条件的不确定性及不完备性，一般会出现 多条求解路径，所有求解路径构成的图即所谓的状态空间。问题的求解过程实际 上是要在状态空间中寻找一条从起点到目标点的路径，称该寻找过程为状态空间 搜索。状态空间搜索法存在着一个自身缺陷：需要在一个给定的状态空间中实施 穷举嘲。 2 3 传统搜索算法 搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的 可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩 展规则构造一棵解答树并寻找符合目标状态的节点的过程。 所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分：控制 结构和产生系统，而所有的算法的优化和改进主要都是通过修改其控制结构来完 成的。 传统搜索技术是不利用问题的有关信息，而根据事先确定好的某种固定的搜 索方法进行搜索。典型的传统搜索方法是宽度优先搜索，亦称广度优先搜索，和 深度优先搜索，这是两种基本搜索方法。这里先介绍回溯策略的一般策略，然后 再介绍宽度优先搜索和深度优先搜索。 2 3 1 回溯法 回溯算法是所有搜索算法中最为基本的一种算法。优先搜索法按条件向前搜 索以达到目的但当搜索到某一步时，发现原先选择并不优或达不到目标，就退 回上一步重新选择，这种走不通退回再走的技术称为回溯法n 们。 其采用了一种“走不通就掉头”思想作为其控制结构，其相当于采用了先根 遍历的方法来构造解答树，可用于找解或所有解以及最优解。 北京工业大学工学硕士学位论文 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基 本思想是：不是按某种固定的计算方法来设计算法，而是通过尝试和纠正错误来 寻找答案。用回溯算法解决问题的一般步骤为： 1 定义一个解空间，它包含问题的解。 2 利用适于搜索的方法组织解空间。 3 利用深度优先法搜索解空间。 4 利用限界函数避免移动到不可能产生解的子空间。 回溯算法的一个重要特性是问题的解空间通常在搜索问题的解的过程中动 态产生的。它对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在 解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相 同的问题中使用，以免产生循环n 1 1 。 2 3 2 宽度优先搜索 宽度优先搜索算法是最简便的图的搜索算法之一，这一算法也是很多重要的 图的算法的原型。d i j k s t r a 单源最短路径算法和p r i m 最小生成树算法都采用了 和宽度优先搜索类似的思想。 如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索算法就叫 做宽度优先搜索，如图2 一l 所示。从图2 - 1 可见，这种搜索是逐层进行的，在对 下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。 图2 - 1 宽度优先搜索示意图 f i g u r e 2 - 1b r e a d t h s e a r c hd i a g r a m 己知图g = ( v ，。e ) 和一个源顶点s ，宽度优先搜索以一种系统的方式探寻g 的 边，从而发现s 所能到达的所有顶点，并计算s 到所有这些顶点的距离，即最 少边数，该算法同时能生成一棵根为s 且包括所有可达顶点的宽度优先树。对从 s 可达的任意顶点v ，宽度优先树中从s 到v 的路径对应于图g 中从s 到v 的最 第2 章搜索算法简介 短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。 之所以称之为宽度优先算法，是因为算法自始至终一直通过己找到和未找到 顶点之间的边界向外扩展，就是说，算法首先搜索和s 距离为k 的所有顶点，然 后再去搜索和s 距离为k + l 的其他顶点。 宽度优先搜索算法如下： 1 把起始节点放到未扩展节点o p n e 表中( 如果该起始节点为一目标节点，则 求得一个解答) 。 2 如果o p e n 是个空表，则没有解，失败退出，否则继续。 3 把第一个节点n 从o p n e 表移出，并把它放入己扩展节点c l o s e d 表中。 4 扩展节点n ，如果没有后继节点，则转向上述第2 步。 5 把n 的所有后继节点放到o p e n 表的末端，并提供从这些后继节点回到n 的指针。 6 如果n 的任一个后继节点是个目标节点，则找到一个解答，成功退出，否 则转向第2 步。 宽度优先搜索算法流程图如图2 - 2 所示： 图2 - 2 宽度优先算法流程图 f i g u r e 2 - 2b r e a d t h s e a r c hf l o wc h a r t 这一算法假定起始节点本身不是目标节点，要检索起始节点是目标节点的可 能性，只要在第1 步的末了，加上一句“如果起始节点为一目标节点，则求得一 北京工业大学工学硕士学位论文 个解答”即可做到，正如第l 步括号内所写的。这个搜索过程产生的节点和指针 构成一棵隐式定义的状态空间树的子树，我们称之为搜索树n 刳。 显而易见，宽度优先搜索方法能够保证在搜索树中找到条通向目标节点的 最短路径，这棵搜索树提供了所有存在的路径，如果没有路径存在，那么对有限 图来说，我们就说该法失败退出，对于无限图来说，则永远不会终止。 2 3 3 深度优先搜索 另一种盲目搜索叫做深度优先搜索。正如算法名称那样，深度优先搜索所遵 循的搜索策略是尽可能深的搜索图。在深度优先搜索中，对于最新发现的顶点， 如果它还有以此为起点而未探测到的边，就沿此边继续探下去。当结点v 的所有 边都己被探寻过，搜索将回溯到发现结点v 有那条边的始结点。这一过程一直到 已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中 一个作为源结点并重复以卜过程，整个进程反复进行直到所有结点都被发现为 止。 在深度优先搜索中，首先扩展最新产生的节点，即最深的，如图2 - 3 所示。 深度相等的节点可以任意排列。定义节点的深度如下： 1 起始节点( 即根节点) 的深度为0 。 2 任何其它节点的深度等于其父辈节点深度加l 。 首先，扩展最深节点的结果使得搜索沿着状态空间某条单一的路径从起始节 点向下进行下去，只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代 的路径。替代路径前面已经试过的路径不同之处仅仅在于改变最后n 步，而且保 持n 尽可能小。 第2 章搜索算法简介 图2 - 3 深度优先搜索示意图 f i g u r e 2 3d e p t h - s e a r c hd i a g r a m 对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比 某个可接的解答序列的已知深度上限深度还要深。为了避免考虑太长的路径，防 止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度：深度 界限。任何节点如果到了深度界限，那么都将把它们作为没有后继节点处理。值 得说明的是，即使应用了深界限的规定，所求得的解答路径并不一定就是最短路 径。 和宽度优先搜索类似，每当扫描己发现结点u 的邻接表从而发现新结点v 时， 深度优搜索将置v 的先辈域为u 。和宽度优先搜索不同的是，前者的先辈子图形 成一棵树，后者产生的先辈子图可以由几棵树组成，因为搜索可能由多个源顶点 开始重复进行n 钉。 有深度界限的深度优先搜索算法如下： 1 把起始节点s 放到未扩展节点o p n e 表中，如果此节点为一目标节点，则 得到一解。 2 如果o p e n 为空表，则失败退出。 3 把第一个节点n 从o p e n 表移到已扩展节点c l o s e d 表中。 4 如果节点n 的深度等于最大深度，则转向( 2 ) 。 5 扩展节点n ，产生其全部后裔，并把它们放入o p e n 表的前头。如果没有 后裔，则转向( 2 ) 。 6 如果后继节点中有任一个为目标节点，则求得一个解，成功退出，否则， 转向( 2 ) 。 有界深度优先搜索算法的程序框图如图2 - 4 所示： 北京工业大学工学硕士学位论文 图2 4 深度优先搜索流程图 f i g u r e 2 - 4d e p t h - s e a r c hf l o wc h a r t 2 4 启发式搜索算法 上面讲的深度优先搜索和宽度优先搜索都没有用到本身的信息，搜索完全是 盲目的按照固定顺序进行。盲目搜索的效率低耗费过多的计算空间与时间。如 果能够找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩 展，那么，搜索效率将会大大提高。在许多情况下，能够通过检测来确定合理的 顺序，称这类搜索为启发搜索或有信息搜索。因此，从有无信息导引这个角度， 可将搜索方法分为以下三大类： 1 无信息导引搜索，它可分为深度优先搜索和宽度优先搜索，其搜索与所给 第2 章搜索算法简介 题信息无关，是人为安排的固定顺序，毫无根据的。 2 信息导引搜索，它可分为爬山策略和最小代价搜索，其搜索是利用向目标 搜索的好坏来判断向哪个方向搜索，即搜索的顺序是有根据的。 3 启发式信息搜索，其搜索是利用具体领域的知识( 具体体现在评价函数 中) ，以提高算法的效率。 2 4 1 启发式搜索的必要性 从理论上说，如果计算机可以使用的时间和空间是无限的，那么仅仅有盲目 搜索算法也许就己经满足了，但实际情况并不是这样，更何况还有个搜索速度问 题。现在己经发现了许多计算复杂性很高的问题，如旅行推销员问题，布尔表达 式的化简问题等等。这些问题的现有算法都是具有指数复杂性的。 现实的困难迫使人们转而求援于启发式算法。这种算法的本质是部分地放弃 算法“一般化，通用化的概念，把所要解的问题的具体领域的知识加进算法中 去，以提高算法的效率。如宽度优先算法几乎可以用于解一切搜索问题，比如九 宫图( 八数码难题) ，河内塔( 焚塔问题) ，旅行推销员，华容道，以及魔方等等。 但是实际使用时，效率也许低得惊人，甚至根本解不出来( 例如魔方问题) 但如 果为每类问题找出一些特殊规则，和宽度优先法配合起来使用，那结果就可能完 全不一样m 1 。 根据启发信息，在生成各种搜索树时可以考虑种种可能的选择，如： 1 下一步展开哪个节点? 2 是部分展开还是完全展开? 3 使用哪个规则( 或算子) 9 4 怎样决定舍弃还是保留新生成的节点? 5 怎样决定停止或继续搜索? 6 如何定义评价函数? 7 如何决定搜索方向? 等等。由于这些选择的不同，就得到了不同的启发式搜索算法。 启发式搜索是利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降 低问题复杂度的目的，这种利用启发信息的搜索过程都称为启发式搜索方法。在 研究启发式搜索方法时，先说明一下启发信息应用，启发能力度量及如何获得启 发信息这几个问题，然后再来讨论算法及一些理论问题。 一般来说启发信息过弱，产生式系统在找到一条路径前将扩展过多的节点， 即求得解路径所需搜索的耗散值，也就是搜索花费的工作量较大，相反引入强的 启发信息，有可能大大降低搜索工作量，但不能保证找到最小耗散值的解路径( 最 佳路径) 。因此实际应用中，希望最好能引入降低搜索工作量的启发信息而不牺 牲找到最佳路径的保证。这是一个重要而又困难的问题，从理论上要研究启发信 北京工业大学工学硕士学位论文 息和最佳路径的关系，从实际上则要解决获得启发信息方法的问题。 比较不同搜索方法的效果可用启发能力的强弱来度量。在大多数实际问题 中，笔者认为感兴趣的是使路径的耗散值和求得路径所需搜索的耗散值两者的某 种组合最小，更一般的情况是考虑搜索方法对求解所有可能遇见的问题，其平均 的组合耗散值最小。如果搜索方法1 的平均组合耗散值比方法2 的平均组合耗散 值低，则认为方法l 比方法2 有更强的启发能力。 启发式搜索过程中，要对o p e n 表进行排序，这就需要有一种方法来计算待 扩展节点有希望通向目标节点的不同程度，总是希望能找到最有希望通向目标节 点的待扩展节点优先扩展。一种最常用法是定义一个评价函数f ( e v a l u a t i o n f u n c t i o n ) 对各个节点进行计算，其目的就是用来估算出“有希望”的节点来。 如何定义一个评价函数呢? 通常参考的原则有：一个节点处在最佳路径上的概率： 求出任意一个节点与目标节点集之间的距离度量或差异度量：根据格局或状态的 特点来打分。即根据问题的启发信息，从概率角度、差异角度或记分法给出计算 评价函数的方法n 副。 2 4 2 评价函数 评价函数的任务就是估计待搜索结点的重要程度，给它们排定次序。评价函 数f ( x ) 可以是任意一种函数，如定义它是结点x 处于最佳路径上的概率，或是x 结点和目标结点之间的距离，或是x 格局的得分等等。一般来说，评价一个结点 的价值，必须综合考虑两方面的因素：已付出的代价和将要付出的代价。在此， 我们把评价函数f ( n ) 定义为从初始结点经过n 结点到达目标结点的最小代价路 径的代价估计值。它的一般形式是： f ( n ) = g ( n ) + h ( n ) 其中g ( n ) 是从初始结点到n 结点的实际代价，h ( n ) 是从n 结点到目标结点 的最佳路径的估计代价，主要是h ( n ) 体现了搜索的启发信息。因为实际代价g ( n ) 可以根据生成的搜索树实际计算出来，而估计代价h ( n ) 却依赖于某种经验估计， 它来源于我们对问题的解的某些特性的认识，这些特性可以帮助我们更快地找到 问题的解n 引。 2 4 3 有序搜索算法 用评价函数士、来排列o p e n 表上的节点。根据习惯，o p e n 表上的节点按照 它们f 函数值的递增顺序排列。根据推测，某个具有低的估价值的节点较有可能 处在最佳路径上。应用某个算法选择o p e n 表上具有最小f 值的节点作为下一个 要扩展的节点。这种搜索方法叫做有序搜索或最佳优先搜索，而其算法叫做有序 搜索算法或最佳优先算法。可见它总是选择最有希望的节点作为下一个要扩展的 节点。有序搜索又称为最好优先搜索。 第2 苹搜索算法简介 有序状态空间搜索算法如下： 1 把起始节点s 放到o p n e 表中，计算f ( s ) 并把其值与节点s 联系起来。 2 如果o p e n 是个空表，则失败退出，无解。 3 从o p e n 表中选择一个f 值最小的节点i 。结果有几个节点合格，当其中 有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点 i 4 把节点i 从o p e n 表中移出，并把它放入c l o s e d 的扩展节点表中。 5 如果i 是个目标节点，则成功退出，求得一个解。 6 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： ( 1 ) 计算f ( j ) 。 ( 2 ) 如果j 既不在o p e n 表中，又不在c l o s e d 表中，则用评价函数f 把它添 入o p e n 表。从j 加一指向其父辈节点i 的指针，以便一旦找到目标节点时记住 一个解答路径。 ( 3 ) 如果j 已在o p e n 表上或c l o s e d 表上，则比较刚刚对j 计算过的f 值和 前面计算过的该节点在表中的f 值。如果新的f 值较小，则 以此新值取代旧值。 从j 指向i ，而不是指向它的父辈节点。 如果节点j 在c l o s e d 表中，则把它移回o p n e 表。 7 转向( 2 ) ，即g ot o ( 2 ) 。 宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对 于宽度优先搜索，我们选择f ( i ) 作为节点i 的深度。对于等代价搜索，f ( i ) 是 从起始节点至节点i 这段路径的代价。 有序搜索的有效性直接取决于f 的选择，如果选择的f 不合适，有序搜索就 可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么f 的选择将涉及两个方面的内容，一方面是一个时间和空间之间的折衷方案，另一 方面是保证有一个最优的解或任意解。 2 4 4 斛算法 a 木算法是一项古老的技术，最初它被用来解决各类数学问题。在人工智能研 究的早期它被用来解决寻路问题。 目前常用寻路算法是a 水方式，原理是通过不断搜索逼近目的地的路点来获 得。搜寻法是是一种最佳化的搜寻方法，是当前用的最多也是最先进的算法， 在比较简单的地图上它的速度非常快，能很快找到最短路径( 确切说是时间代价 最小路径) ，而且使用张算法可以很方便地控制搜索规模以防止程序堵塞。 a 木算法是一种有序搜索算法，其特点在于对评价函数的定义上。对于一般的 有序搜索，总是选择f 值最小的节点作为扩展节点。因此，f 是根据需要找到一 北京工业大学工学硕士学位论文 条最小代价路径的观点来估算节点的，所以，可考虑每个节点n 的评价函数值为 两个分量：从起始节点到节点n 的代价以及从节点1 3 到达目标节点的代价。 具体的a 水算法步骤如下： 1 、生成一个只包含开始节点n 0 的搜索图g ，把n o 放在一个叫o p n e 的列表 里。 2 、生成一个列表c l o s e d ，它的初始化为空。 3 、如果o p e n 为空，则失败退出。 4 、选择o p e n 上的第一个节点，把它从o p n e 中移入c l o s e d ，称该节点为n 0 。 5 、如果r l 是目标节点，顺着g 中，从1 3 到n o 的指针找到一条路径，获得解 决方案，成功退出( 该指针定义了一个搜索树，在第7 步建立) 。 6 、扩展节点n ，生成其后继节点集m ，在g 中，i i 的祖先不能再m 中。在g 中安置的成员，使它们成为n 的后继。 7 、从m 的每一个不在g 中的成员建立一个指向n 的指针( 例如，既不在o p e n 中，也不在c l o s e d 中) 。把m 的这些成员加到o p e n 中。对m 的每一个已在o p e n 中或c l o s e d 中的成员m ，如果到目前为止找到的到达m 的最好路径通过n ，就把 它的指针指向n 对已在c l o s e d 中的m 的每一个成员，重定向它在g 中的每一个 后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。 8 、按递增f 值，重排o p e n ( 相同最小f 值可根据搜索树中的最深节点来解 决) 。 9 、返回第3 步。 在第7 步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径 代价低，一就要重定向指向该节