（计算机应用技术专业论文）激励势场算法的复杂性研究.pdf

摘要 当面对求解一个问题的新算法的时候，我们的兴趣在于形成这样一种粗略 的认识：新算法预期能有多好，对于同一个问题它比其他的算法如何。计算复 杂性研究能够提供这种认识。对算法的分析能够帮助我们对算法更深入地理解， 并能够提出有根有据的改进。尤为重要的是，正确分析所需要的仔细全面的审 查常常使得算法更好和更有效地实现。 激励学习因为具有较强的在线自适应性以及对复杂系统的自学习能力，受 到机器人导航研究者的关注。目前，激励学习对于许多现实的问题，如大尺度 和部分可观测环境，仍然是没有解决的问题。这些问题采用传统的算法很难满 意地解决。通过利用人工势场将激励学习问题转换为路劲规划问题。然后为解 决人工势场中的局部最小问题，应用虚拟水流法的概念提出的一种新的人工势 场算法。实验结果表明该方法在激励学习系统中是有效的。但只有当解析的结 果与经验研究一致的时候，我们才会确信算法的合理性以及分析过程的正确性。 为了说明该方法的合理性和正确性，本论文将从解析的结果与经验研究两方面 对此算法进行了分析和研究。 主要工作陈述如下： ( 1 ) 对算法复杂性分析的方法、涉及的数学知识、研究现状和现实意义进 行了综述性介绍。 ( 2 ) 研究了人工势场中斥力势函数和引力势函数的选取，重点研究了如何 将激励学习模型转换成人工势场模型。 ( 3 ) 用网格世界问题对激励势场模型进行了测试。实验结果表明：该算法 能简洁有效地给出理想的解。 ( 4 ) 给出了虚拟水流算法的数学模型，分析在最坏的情况下，其算法时间 复杂度为d ( 掣) 。同时求出了算法的空间复杂度。 关键词：算法分析；激励学习；人工势场；路径规划；虚拟水流法 a bs t r a c t w h 髓s o l v i n gap r o b l e mw i t l lan e wa l g o r i 1 i l l ，i ti so f 妒e a ti n t e r e s tt 0l ( i l o w ：h o w g ( di sm ea l g o r i t h mc o m p a r i n gw i mo t h e 娼t h es t u d yo fc o m p u t a t i o n a lc o m p l e x i t y c a i li l l u s n a t e a n a l y s i so fa 1 9 0 r i t 量l i l lc 觚l e tl l sb 毗e rl l l l d e 璐t a i l da l l di m p r o v ei t e s p e c i a l l 弘t l l ec 0 玎e c ta i l a l y s i so fa l g o r i t l l mr o q u i r e dc o m p d e h e i l s i v er e v i e w ，觚d l l s u a l l ym a k ei tb 甜e ra n dm o r ee f f e c t i v e r e i n 向r c 锄e n tl e 锄i n g ( r l ) h 硒a t t r a c t e d 埘1 0 s tr e s e a r c h e r si nm ea r e ao ff o b o t i c s ， b e c a u s eo fi t ss 仃o n go n - l i n ea d a p t a b i l 时雒ds e l 仁l e 锄i n ga b i l i t y 如rc o m p l e x s y s 蛔n s of 弛r d n 如r c e m 锄tl e 锄i n gs t i l lh 嬲m a n yp r o b l e m st ow a i t i n gf o rs o l v i n g d 嘶n g t l l ep r o c e s s0 fs c a l i n gu pt or e a l i s t i ct a s k s ，i n c l u d i n gm ep r o b l e m s 舔s o c i a t e d w i t l lv e wl a r g es t a t es p a c e s ，p a r t i a l l yo b s e r v a b l es t a t e s ，删陀i yo c c u r r i n gs t a t e sa n d u n k n o w ne i l v i m m n e l l t s b u to n l yw h e i lm er e s u l t so f 姐a l y s i si sm es a n l e 弱m e e i t l p i r i c a ls t u d i e s ，w ew i l lb e l i e v em a tm ea l g o r i t l l l i la n dm e 肌a l y s i so ft h ep r o c e s s t l l m e do u tt 0b ec o m t 锄dr e a s o n a b l e t oi l l u s 仃a t et l l em e t h o db e i n gr e 雒o n a b l e a n dc o m 斌，m i sp 印e rs h o u l dl i k et om i n ka b o u tt 1 1 er e s u l t so fa 1 1 a l 如c a l 觚d 锄p i r i c a lr e s e a r c h i f lt k sr c s 髓f c h ，t h e 雒a l y s i so fv i r t l 膪1w a t e rn o wa l g o r i n l m sa r e s t u d i e d ，t h er e s u l t sa r ep r e s c n t e da s 南l l o w s ： ( 1 ) t 1 1 i sp a p e rp r o v i d e sai n t r o d u c t i o nt 0m em e t h o d s 锄dt i l ep m a 巧t e c h i q u 销 u s e di i lm em a t h e i n a t i c a la i l a l y s i so fa l g o r i t l l n l s ( 2 ) t h er 印u l s i o nf o r c em n c t i o na i l dm e 伊a v i t a t i o nf o r c e6 m c t i o no ft h ep o t e n t i a l f i e l da r ei n t r o d u c e d ar c i n f o r c e m e n tl e 锄i n gp r o b l e mi s 仃锄s f e 盯o dt 0ap a m p l 锄i n gp r o b l e r l lb yl l s i n g 硎1 f i c i a lp o t e n t i a lf i e l da 1 1 di ti st h em a i n c 0 n t e l l t so f l i s 吐l e s i s ( 3 ) t h ep e 墒锄觚c eo fr p f mi s t e s t e db yt h ew c i l k n o w n 鲥d w o 订d p r o b l e m s e x p 嘶m 朗t a lr e s u l t ss h o wt h a tt l l er p f m i ss i m p l ea n de 虢c t i v et o 舀v e a no p t i m a ls o l u t i o n ( 4 ) t h em a t h e m a t i c a ln l o d e “sp r e s e n t e d t h ew o r s t - c a s ea n a l y s i so f ? t h ec o m p l e x i t y a l g 耐m m si sd ( 业岩) 。觚di t i sp r o v e db ym em a t h 锄a t i c a lm 础0 d i t ss p a c e z c o m p l e x 时i sp r e s e n t e d k e yw o r d s ：a n a l y s i so fa l g o r i t h m ；r e i n f o r c e m e n tl e a m i n g ； a r t 浓c i a l p o t e n t i a lf i e l d ；p a t hp l a n n i l l g ；r t l l a lw a t e r _ n o w 1 1 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导_ 卜独立进行研究 所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包 含任何j 他个人或集体已经发表或撰写的成果作品。对本文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到 本卢 ! j j 的法律 彳果由本人承担。 作者签名： 研起议日期：歹矿6 7 年夕月多口 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“v ”) 作者签名：钾葱t 日胎阳年歹即日 导师签名： 日期：一年r 月，8 日 第一章绪论 1 1 机器人路径规划的研究 d u r r a i l l tw 吼ehf 提出了智能移动机器人导航的三个主要的问题：( 1 ) “我 现在哪里? ”( 2 ) “我要往哪里去? ”( 3 ) “如何到达到该处? ”。其中第三个问题就是机 器人如何进行路径规划【l 】。机器人路径规划一直是一个重要研究领域。它的主 要任务是在有障碍物的环境中，根据一定的评价标准，寻找到一条从初始状态 ( 包括位置和姿态) 到达目标状态( 包括位置和姿态) 的无碰路径。路径规划主要应 用在机器人的底层策略中，作为智能机器人基本动作实现的基础，它的优劣将 对动作的实时性及准确性产生直接影响，因此，每个机器人研究者都把其作为 一个研究重点。机器人路径规划研究已渗入其它学科，对于虚拟造型、计算机 动画、计算机图形学、人工生命以及动物行为学等的研究都有非常重要的参考 价值。 路径规划问题产生于计算机几何学的传统研究课题。七十年代中期，智能 机器人的研究不断深入，从而促进了路径规划问题的研究。因为移动机器人、 装配机器人都和路径规划技术紧密联系。目前，国内外对这个课题的研究仍然 非常活跃。根据对环境信息的掌握程度，路径规划可分成：环境信息完全已知 的全局路径规划；环境信息不完全或未知的局部路径规划。最近几年，人们研 究的热点问题是环境信息不完全或者未知的局部路径规划技术。 全局路径规划常用方法主要包括：可视图法、栅格法、自由空间法等【2 j 。 可视图法是将机器人看成是一个点，将机器人，目标点以及障碍物各个顶 点之间进行连线，它要求机器人与障碍物顶点之间，目标点与障碍物各个顶点 之间，以及各障碍物顶点和顶点之间的连线都不能够穿越障碍物，这样便构成 一张图，称之为可视图。因为任意两条直线的顶点都为可视的，所以移动机器 人从起始点沿着这些连线到达目标点的所有路径均是无碰路径。然后利用优化 算法去掉一些不需要的连线以简化可视图，缩短其搜索时间，最终便可以找到 一条无碰撞的最优路径。可视图法主要适用于多边形的障碍物，对于圆形的障 碍物该方法失效。其最大的优点是具有完备解，同时计算较复杂、搜索时间较 长以及占用内存较多也成为它不能广泛得到应用的最终原因。 栅格法是将机器人的工作环境分解成为一系列具有二值信息的网格单元， 每个栅格都有一个累积值，表示在这个方位中存在障碍物的可信度，该值的大 小意味着存在障碍物可能性的大小。选择栅格的大小直接影响了控制算法的性 能，栅格选择得大，抗干扰的能力强，环境信息的存储量小，搜索的速度快， 但是分辨率低，在密集的障碍物环境中找到路径的能力减弱。反之，栅格选择 得小，抗干扰的能力减弱，环境信息的存储量大，搜索的速度慢，但是分辨率 高。栅格法一般是由优化算法来完成路径搜索，主要的路径搜索算法有：a 宰算 法，遗传算法等等。哈尔滨工业大学的薄喜柱教授，通过用栅格法对机器人运 动的空间进行建模，参照了人类在人群中行走的经验，然后对栅格地图进行进 一步的规划，成功的实现了足球机器人的路径规划问题【3 】。 自由空间法通过采用预先定义的如凸多边形和广义锥形等基本的形状构造 自由空间，然后将自由空间表示为连通图，通过对连通图进行搜索完成路径规 划。这种方法的主要优点是灵活，改变起始点及目标点不会造成连通图的重构， 但是算法的复杂度与障碍物的数目成正比，而且并不是任何情况下都能够得到 最优路径。 全局路径规划能够对环境信息完全已知下的移动机器人路径规划问题进行 处理。但当环境发生改变时或者出现了未知障碍物的时候，这种方法就无能为 力了，这时必须通过结合局部路径规划。局部路径规划常用的方法主要有：人 工势场法，模糊逻辑法和遗传算法等等【2 1 。 人工势场法是由k h a t i b 提出的一种虚拟力法。它的基本思想是把机器人在 环境中的运动看成是一种在虚拟的人工受力场中运动。机器人对障碍物所产生 斥力，及对目标点所产生的吸引力，斥力和引力的合力会控制着机器人的运动。 该方法的优势是结构简单，有利于底层的实时控制。不足之处是存在着一些局 部最优解的问题。所以可能会使机器人不能够到达目标点而是停留在局部最优 点上。在国内，清华大学、华中师范大学等院校都在足球机器人的系统中使用 了这种方法。而且从搜集到的资料来看，相关的文献也是非常多的，这也充分 表明了人工势场法在路径规划中具有一定的优势。 模糊逻辑法通过参考人的驾驶经验，然后查表得到规划信息，实现局部路 径规划，这种方法克服了在势场法容易产生的局部最优问题，适合于时变未知 环境下的路径规划，实时性比较好。此外，局部规划法还有细胞神经网法，神 经网络法等。 遗传算法是在6 0 年代初由j h o l l a i l d 提出的，它通过借鉴生物界的自然选 择和遗传机制的搜索算法。大部分的优化算法都是单点搜索算法，非常容易陷 入局部最优，但是遗传算法却是一种多点搜索，能更好的搜索到全局最优解。 其不足之处是该算法因为要进化众多的规划，所以要占据比较大的运算时间和 存储空间，故算法的速度不快，实时性比较差。 2 1 2 存在的问题 人工势场法( a n i f i c i a lp o t e n t i a lf i e l d ) 是实现无碰路径规划的重要方法，得 到广泛的使用。但对于复杂的环境( 尤其是动态环境) ，人工势场法是不适用的： 这种方法容易产生势场的局部最小区域，使得机器人会在局部最小区域里发生 路径来回震荡或者停止运动的现象；另外，人工势场法仅注重于得到无碰路径， 对于路径是否是最优并没有进行考虑。基于智能优化搜索方法通过其对解空间 的全局优化搜索克服了人工势场法中的局部最小问题，并能够生成最优路径， 例如基于模拟退火法的路径规划、基于遗传算法的路径规划等【4 5 】。但是当机器 人的工作空间比较大的时候，解空间也比较大，增加了计算量，使得路径规划 的效率降低，不利于实时规划。本文介绍的采用虚拟水流法解决人工势场模型 中的局部最小问题。该方法不需要记录状态和观测及其值，它和传统的值函数 激励学习不同，故节省了大量的存储空间，为了说明该方法的合理性和正确性， 本文将从解析的结果和经验研究两方面对该算法进行分析和研究。 1 3 本文研究内容 上面主要讲了机器人路径规划的概念、特点、分类以及规划算法的分类与 比较。另外还叙述了路径规划研究意义及国内外的研究现状。在复杂环境特别 是动态时变环境中，机器人路径规划问题特别复杂，而且需要非常大的计算量。 r e i f 和s h a i r 证明了在三维动态环境中，受到速度约束的机器人的运动规律是p 空间难度问题( p s p a c e - h a r d ) ，并且c a i l l l y 证明了即使是受约束的点状机器人 在二维平面上的路劲规划问题也是n p 难度问题烈p - h a r d ) 。近2 0 年的发展中， 大批研究者对人工势场法进行了深入研究，并对其进行了各种不同的改进和发 展。本文就人工势场法容易陷入局部最小问题提出的一种基于虚拟水流的解决 办法进行了叙述，并重点分析该算法的时间复杂度和空间复杂度。 其主要研究工作如下： ( 1 ) 介绍了在进行算法复杂性分析时，需用到的数学方法及其研究现状。 常用的分析方法有：算法的最坏情况复杂性分析、算法的平均情况复杂性分析、 算法的平摊分析和算法的复杂性平滑分析等。事实上，许多最重要的算法都可 以由递推公式相当简单地表示出来，本文在第二章中重点阐述了对于这类算法 分析中产生的递归类型、求解的基本方法及算法分析中经常涉及到的数学知识。 ( 2 ) 将激励学习模型转换为人工势场模型。通过用虚拟水流法解决传统人 工势场法中的局部最小问题。该方法不需要记录状态和观测及其值使得智能体 需要记忆的空间大为减少，同时也使之具有适应性。 ( 3 ) 用网格世界问题对激励势场模型进行了测试。实验结果表明：该算法 能给出简洁有效地理想解。 3 ( 4 ) 由虚拟水流算法抽象得到其数学模型，通过对其进行分析和归纳假设， 最后给出了虚拟水流算法的时间复杂度和空间复杂度。 1 4 ，j 、结 本章叙述了智能机器人路径规划的定义、研究方法分类及其优缺点。路径 规划是实现机器人智能的一项重要的技术，在机器人应用中是极其重要的研究 方向。而路径规划中应用的算法种类繁多，为了说明该算法具有更强的合理性 和适应性，故需要对该算法进行分析以便能够找出它的特性。 4 第二章算法的基本知识 2 1 算法的概念和性质 直观上说，一个算法是一个有定义的计算机程序，它以一个或多个值为输 入，产生一个或多个值作为输出。一个算法就是一个计算步序列，它把输入值 转换为输出值【6 】。算法具有5 个重要特性： ( 1 ) 有限性。 一个算法在有限步骤之后必然要终止。 ( 2 ) 确定性。 一个算法的每个步骤都必须精确地定义；要执行的动作每一步都必须严格 地和无歧义地描述清楚。 ( 3 ) 输入。 一个算法有零个或多个输入，此即在算法开始之前最初赋给它的量，或者 当算法运行时动态地赋给它的量。这些输入是从特定的对象集合取出的。 ( 4 ) 输出。 一个算法有一个或多个输出：和输入有特定关系的量。 ( 5 ) 能行性。 一个算法一般可以认为是能行的( 或称有效的) ，其含义是指它的所有运算 必须是充分基本的。因而原则上人们用笔和纸都可在有限时间内精确地完成它 们。 2 1 1 算法的复杂性概念 算法的复杂性是指运行算法所需要的计算资源。求解一个问题时，通常会 遇到若干个可用于求解问题的算法。这就需要我们通过分析比较从中选出最好 的算法。其中，经验的方法是对待选的几个算法进行编程实验，然后通过给定 一定量的输入实例在计算机上运行它们，对它们的运行结果进行比较分析以确 定所采用的算法；理论的方法是从数学上确定每个算法所需要的计算资源，即 算法的复杂性( 通常用执行时间、所需内存空间等刻划) ，并用一个关于输入实 例规模的函数来表示【7 1 。 输入实例x 的规模，记为，它是指在一个计算机上用某种有明确定义的 编码规则来表示算法的输入实例x 所需要的二进制位数。直观上，输入实例的 规模大小表示在某种度量方式下输入实例中所含的成份个数。 对于给定的函数f ，我们说一个算法具有阶为f ( ，z ) 的复杂性，如果存在正常 数c ，对于所有规模为甩的合法输入实例，算法的复杂性不超过c g ( 力) 。就计算 时间而言，凡是计算时间不超过某一关于输入实例规模的多项式的算法称为多 项式时间算法( p o l y n o m i a lt i m ea l g o r i t h m ) ；计算时间不小于某一个关于输入实 例规模珂的指数函数的算法则称为指数时间算法( e x p o n e n t i a lt i m ea l g o r i t h m ) 。 2 1 2 算法的复杂性分析方法概述 为了确定算法的性能或比较算法性能的优劣，需要对算法的复杂性进行分 析。常用的分析方法有：算法的最坏情况复杂性分析、算法的平均情况复杂性 分析、算法的平摊分析和算法的复杂性平滑分析等。 1 算法的最坏情况复杂性分析 设爿是一个算法，是彳的所有可能输入实例的集合，令s ：，专是关于 输入实例规模的函数。令c ：，一是算法彳关于给定输入实例的复杂性函数。 我们把算法么的最坏情况复杂性定义为如下函数厂：专矿 厂( 甩) = m a x c ( f ) l f ，且s ( f ) = 力 2 算法的平均情况复杂性分析 令p ：，专尺卸是一个具有给定规模的所有可能输入实例上的概率分布。即， 对于任，l ， p ( f ) = 1 拒，j ( f ) ，” 我们把算法a 的平均情况复杂性定义为如下函数g ：一 g ( ，z ) = 艺p ( f ) c ( f ) 拒，( f ) = ” 在这种方法里，必须知道所有输入出现的概率，也就是需要预先知道输入 的分布，但是在很多情况下。即使放宽了一些约束，包括假设有一个理想的输 入分布( 如均匀分布) ，分析也是复杂和冗长的。 3 算法的平摊分析 算法的平摊分析主要用于分析一个作用于某个数据结构的操作序列的开 销。其目的在于说明虽然单个操作的开销很大，但操作序列的平均开销却是小 的。有两种进行平摊分析的基本技术，一种是基于金融模型的会计方法，另一 种是基于能量模型的势能函数方法【1 2 】。 令s 是某一数据结构所有可能状态的集合，占s 记为初始状态。对于状态 j s ，我们把对状态j 执行操作7 所需开销记为c ( 厂( j ) ) 。定义势函数 ：s 一尺卸，使得 ) = o 。设操作y 作用在状态s 上产生状态s 。我们定义该 6 操作的平摊开销为：c ( 7 ( s ) ) + ( s ) 一( s ) 。因此，对于操作序列乃，l ，丑= 占。 令状态岛+ 。是操作乃作用在状态墨后得到，f = l ，l ，m 一1 。则对应于该操作序列 的总平摊开销为： c ( 鹏) ) + 眠) c ( 7 ( s ) ) f = lf = l 在平摊分析中，可以算出算法在整个执行过程中所用时间的平均值。平摊 分析保证了运算的平均代价，进而也保证了算法在最坏情况下的平均开销。这 与平均情况分析不同，在平均分析中，要计算同样大小的所有实例才能得到平 均值，它也不像平均情况分析，不需要假设输入的概率分布。一般来说，平摊 时间分析比最坏情况分析更困难，但是当我们由此导出了一个更低的时间复杂 性时，克服这些困难就值得了。 4 算法的复杂性平滑分析方法【7 】 给定一个算法a ，令x 。表示具有规模为拧的所有可能输入实例所构成的输 入实例空间。对于输入实例x x 。，令c a ( 力表示算法a 关于输入实例工的复 杂性。输入实例的规模通常由包含在输入实例中的变量个数及表示各变量取值 范围所用的二进制位数之和来表示。算法a 的平滑复杂性厂( 刀，盯) 用下面的式子 表示： ( 刀，仃) = 凹b e q ( y ) j 乞 _ 其中y 是输入实例工的随机邻域( 其大小取决于随机扰动幅度盯) 上的一个随 机输入实例，e 表示数学期望。从定义可以看出，算法a 的平滑复杂性就是 中各输入实例z 在指定的随机扰动作用下所得的随机邻域上算法a 的平均 复杂性的上确界。 2 2 数学准备 算法分析中涉及的数学技术通常都有一种特殊的风味：将经常发现我们总 是在对有理数进行有限求和，或者对递归关系进行求解。以下的内容用来简要 说明用于这类问题的计算和技术的类型。 2 2 1 递归算法的数学分析 我们考虑对其进行分析的算法通常都可以表示成递归或迭代，这意味着， 一般我们能够把求解特定问题的开销用求解一些更小的问题的开销来表示。数 学上最基本的处理是使用递推关系。它代表着一种从程序的递归表示到描述其 特性的函数的递归表示间的直接映射的实现方式。算法涉及的输入模型的特定 性质都被封装在相对简单的数学表示之中。许多最重要的算法都可以由递推公 7 式相当简单地表示出来，而它们的分析则导致递归，或者描述平均情形，或者 确定最坏情形的性能的界。下面将论述通常产生于算法分析中的递归类型和某 些基本的求解方法。 1 基本性质町 ( 1 ) 值的计算。递归提供了一种有效的方法计算所考虑的量的值。特别是， 求解任意的递归的最初一步是用它计算一些小的值来获得递归如何增长的一种 感觉。 ( 2 ) 缩放和平移。递归的一个基本性质是依赖于初始值。改变初始值叫做 缩放( s c a l i n g ) 递归；移动初始值叫做平移( s h i 衔n g ) 递归。初始值最常见的 是从问题直接得出，常使用缩放和平移简化通向解的途径。 ( 3 ) 线性性。具有多于一个初始值的线性递归可以通过独立地改变初始值 并将解组合而得到“缩放”。 2 一阶递归 或许最简单形式的递归可以直接化成一个乘积。递归 吒= 毛口纠0 0 ，口o = 1 ) 等价于 q = 兀 l s 七s 玎 这种变换是迭代( i t e r a t i o n ) 的一个简单的例子： 只剩下常数和初始值为止，然后再简化。 定理2 1 ( 一阶线性递归) 递归吒= 口剃+ 以 的显示解为 = 儿+ 乃t + _ + 2 l 吒 l s j o ，= o ) 定理2 1 是将具有常或变系数一阶线性递归变换到和式的变换的完全特征 化，求解递归的问题化成和式求值的问题。 3 非线性一阶递归 当递归有关于口。和口川的非线性函数组成的时候，会出现很多的情况，我 们不能期望向定理2 1 那样有一个封闭形式的解。下面将考虑一些确实能够得 到解的情形。 ( 1 ) 简单收敛。计算初始的一些值的一个令人信服的理由是，许多表面上 复杂的递归实际上收敛到一个常数。例如，考虑方程 口。= 1 ( 1 + 口。一1 )( 以 0 ，= 1 ) 这是所谓的连分式方程，它收敛到一个常数，那么，这个常数必然满足 口= l ( 1 + 口) ，或1 一口一口2 = o ，它导致解口= ( 5 1 ) 2 o 6 1 8 0 3 3 4 。 ( 2 ) 二次收敛和牛顿方法。这个计算函数根的著名迭代方法可以看作是计 算一阶递归的近似解的过程。例如，计算正数平方根的牛顿方法是对下面的 公式进行迭代 吒：昙( 。+ 卫) ( 刀 o ，：1 ) 二一1 在该递归中变换变量，令吃= 吒一口，通过简单的代数整理有： 吃= 主瓮譬 于是，若口= 尸，则大致有吃= 6 i 。这就是二次收敛的情形。 ( 3 ) 缓慢收敛。考虑递归 口。= a ，l ( 1 一口，1 )( 珂 0 ，= 1 2 ) 由于递归中的项是递减的并且是正的，因此不难看出l i m 。，。口。= o 。为了找出收 敛速度，自然要考虑1 口。代入得到 土：上( 士) 口q ll 一口n i = 二( 1 + 吼一l + 口。一1 2 + l ) 口h i 上+ l q 一1 反复套用该不等式则给出1 口。 刀或口。 l 刀。所以口。= d ( 1 刀) 。 上面考虑的三种情形是形式4 。= 厂( 口) 的特殊情形，其中为连续函数。 如果吒收敛到极限口，那么口必然是该函数的一个不动点，且口= 八口) 。上面 的三种情形是下面一般情形的代表：如果oq 厂+ ( 口) i 1 ，口( x ) = 0 ( 工s1 ) ) 则 若口 删：者( x 哟仪一l ，q 定理2 4 ( 分治序列) 如果通过把一个大小为，l 的问题分成夕部分，每部分 大小为靠口+ d ( 1 ) ，并在独立地求解这些子问题时因分割和组合附加开销厂( 咒) ， 而使一个分治算法成功进行，那么当厂0 ) = o ( 以7 ( 1 0 9 刀) j ) 时，总的开销由 若7 l o g ； 口。= o ( n 1 0 8 5 ) 给出。 在复杂性的研究中，常常使用更一般的公式表示，因为可以使用的厂( ”) 的 信息不那么具体。在对厂( ，1 ) 光滑性适当条件下，可以证明 l o 彩( 刀) = d 0 k ；吖)吼= o o b 够) 杉( 力) = o ( 刀b 8 ；)口。= ( ，1 1 。2 多l o g n ) 羞厂( 拧) = q ( ，l 忱”)q = o ( 厂( 玎) ) 这类结果通常用来证明算法渐进性能的上界和下界，方法是选择0 ) 给开销适 当定界。 6 求解递归的方法 我们考虑四种一般的方法【8 】： 变量代换( c h 锄g eo fv 撕a b l e ) ，它通过用另外的变量重新计算递归而将递 归简化； 取值表法( r e p e r t o i r e ) ，它从给定的递归反过来求解空间。这种方法主要适 应于线性递归。包括三个步骤：( 1 ) 通过添加一个附加的函数项将递归松弛；( 2 ) 将一些已知的函数代入到递归中，得到类似于该递归的一些等式；( 3 ) 将这些 等式线性组合，得到恒等于该递归的方程； 自精化方法( b o o t s t r a p p i n g ) ，该法首先求出一个近似解，然后利用递归本 身在求出更精确的解，如此继续直到得到足够精确的答案或者不太可能有进一 步的改进为止。非正式地分为如下步骤：( 1 ) 使用递归计算一些数值；( 2 ) 猜测 解的近似形式；( 3 ) 把近似解代回到递归；( 4 ) 根据所猜测的解和代入的情况， 证明解的更接近的界； 扰动( p e 内l 而a t i o n ) 法，该方法研究将递归变换为一个类似的、更简单的、 具有已知解的递归的效果。前两种方法常常得到递归的准确解，后两种方法更 经常用于获得近似解。分为如下步骤：( 1 ) 将递归进行微小的修改，使变成一 个已知的递归；( 2 ) 变换变量使获得已知的界并变换成一个关于解的( 更小的) 未知部分的递归；( 3 ) 定界或求解未知的“误差”项。 递推关系自然地对应迭代和递归程序，而它们在算法分析的各种应用中能 够很好地为我们服务，因此我们综述了能够发生的递推关系的类型和使用它们 进行模拟的某些方法。为能够获取描述重要性能特征的递推关系而足够准确地 理解一个算法常常是分析该算法的重要的第一步。 计算复杂性研究常常依赖于求解为算法性能特征进行估计和定界的递归。 特别地，“分治 递归在计算复杂性文献中出现得特别多。大部分这种递归都 有类似的结构，它们反映在算法设计中平衡的程度。 2 2 2 生成函数 在递归关系中，算法分析的目的是要导出序列，q ，口：，l 中诸项的值的具 体表达式，这个序列是度量某种性能的参数，而生成函数则用一个单一的数学 对象表示整个序列。它不仅是求解递归和计算矩的必需的技巧性很强的工具， 而且它在以下两者之间建立了一种自然的联系：我们所研究的算法对象和探讨 其性质所必需的解析方法。生成函数可提高两方面的服务：既可作为组合学工 具进行计数的研究，又可作为解析工具对所感兴趣的量做精确的估计。 生成函数分为常规和指数型两种类型。 定义2 1 给定序列口。，喁，口：，l ，吼，l ，我们称下面的函数 么( z ) = 畋z 七o 为该序列的常规生成函数( o g f ) ，用记号【z 】彳( z ) 表示系数吼。 定义2 2 给定序列，q ，口：，l ，吼，l ，我们称下面的函数 ，i 么( z ) = 咏云 l 拍 ： 为该序列的指数生成函数( e g f ) ，用记号七! 【z m ( z ) 表示系数吒。 在算法分析的大量应用中，在典型分析的第一部分，我们通过细致地对照 可以探讨幂级数与算法之间的形式上的关系，从而导出生成函数的显示公式。 在典型分析的第二部分，我们可以得到生成函数详细的解析性质，从而导出描 述算法基本性质的显式公式。生成函数提供了用于求解许多递推关系的很机械 的方法。给定一个表示某序列国。) 脚的递归，通常按以下步骤进行求解： ( 1 ) 在递推式的两边乘以z 4 ，然后关于以求和。 ( 2 ) 处理所得的各个和，导出一个o g f 的函数方程。 ( 3 ) 解这个函数方程，导出o g f 的显示公式。 ( 4 ) 将o g f 展开为一个幂级数，从而得到系数表达式( 这些系数就是原来 的序列中的元素) 。 同样的方法也适用e g f ，只是两边乘以z 升拧! ，然后在第一步关于疗求和。 究竟使用o g f 还是e g f 更方便，依赖于递归。 2 2 3 渐进逼近 在算法分析中，我们最初的想法一般都倾向于导出准确的数学结果。然后 这种准确的解并不总是能够得到的，或者如果能够得到准确解，它们也可能太 复杂，而没有多大用处。下面将介绍考查导出问题的近似解或逼近准确解的一 些方法。对渐进展开式的基本性质给出一个综述，给出操作这些展开式的方法 以及那些在算法分析中最常遇到的展开式。 在分析算法的复杂性时，有以下几种常用的渐近表示： ( 1 ) 如果存在两个正常数c 和，使得对于所有的以n 。，有l 厂( 疗) c k ( ，1 ) l i 1 2 贝0 记作( 刀) = d ( g ( 玎) ) 。 ( 2 ) 如果存在两个正常数c 和，使得对于所有的以刀。，有l 厂( 刀) c l g ( 以) 则记作厂o ) = q ( g ( ，1 ) ) 。 ( 3 ) 如果存在正常数c 。，c ：和，使得对于所有的刀以。，有qk ( 刀) l i 厂( 万) l 乞l g ( ，1 ) i 则记作0 ) = o ( 9 0 ) ) 。 ( 4 ) 如果对于任一正常数c ，存在正常数甩。，使得对于所有的刀以o ，有 l 厂( ，1 ) 几。 2 引力势函数 目标点对机器人的势函数同样也是基于距离的概念。目标点离机器人的距离 越远，吸引的作用越大，也就是机器人离目标点越远，所具有的势能就会越大； 反之，当距离越近时，其具有的势能越小。如果距离为零时，那么机器人的势能 为零，这时机器人到达终点。这个性质和重力势能及弹性势能相似。而重力势能 和距离成正比，弹性势能和距离的平方成正比。这样就得到下面两种势函数。 ( 1 ) 采用重力势函数和由重力势函数所产生的力： ( x ) = 疋矽，) ( 3 7 ) 瓦= 疋 ( 3 8 ) ( 2 ) 采用弹性势函数和由弹性势函数所产生的力： 1 【么) = 寺k 妒( x ，五删) 2 ( 3 9 ) 二 毛2 k 。矽( x ，xg o a i ) ( 3 1 0 ) 式中：吃为引力势场常量，t 。，为目标位置向量，引力的方向指向目标点。 这两种势函数所得到的引力通常是不相同的，采用弹性势函数在距离p ( x ，t 埘，) 很大或者很小时，所产生的引力差别会很大，如果障碍物所产生的斥力不大但是 引力较大时，会使机器人和障碍物相撞。如果采用的是重力势函数，那么所产生 的引力是常值。不过a n d r c w s 提出了通常被称为二次抛物曲线拟合方法的引力势 函数，即引力势场眈。会随着机器人远离目标而增加( 像当我们远离地球表面时 势能会增加一样) 。用等式( 3 1 1 ) 描述如下： 州= 瑟g i f ( 功剑 ( 3 1 1 ) i f ，( x ) d 其中，x 表示机器人的方位向量，p 删( 功= 忙一川表示从石到目标点 的欧氏距离，d 为引力源影响半径，丸为引力场强系数。引力f 毗可以从这个 引力势场的负梯度方向得到，即： 卜吒。一毛。，)i f 瓜) d 瓦 卜坷蹦加卜蠢讦嘣咖d 。j 2 3 1 2 全局势场的生成 全局势场可通过引力势场与斥力势场的和得到。运用叠加原理可以得到 u ( x ) 如下： u ( x ) = q 玎( x ) + u 二( x ) ( 3 1 3 ) 2 i 合力的计算公式如下： ，( x ) = 一v u ( 工) = 一v 么( x ) 一v 【厂，印( x ) = f 乙( x ) + f 乙( z ) ( 3 1 4 ) 3 2 激励势场模型 激励势场( r e i n f o r c 锄e n tp o t e i l t i a lf i e l d ，l 冲f ) 模型是通过结合激励学习与人 工势场的优点，然后应用虚拟水流法所构建的一个具备记忆学习功能的模型。 激励势场相对于q 学习等方法在计算的时间复杂度和所需的空间复杂度方面都 有所降低