（应用数学专业论文）网络的k最短路算法研究.pdf

哙尔演理t 人学理学硕i ：学位论文 网络的k 最短路算法研究 手两斐 网络的最短路问题在现代计算机网络及交通系统中扮演着极其重要的角 色，是最优化问题中的一个经典问题，它在实际生产生活中有着广泛的应 用。在许多情况下，不仅仅要考虑最短路也要考虑次短路、次次短路，即 k 最短路。k 最短路应用涉及很多领域，如通信、网络、交通工程、人工 智能等。对该问题的研究不仅具有重要的理论意义，而且具有很大的实用价 值。 本文从图沦的基本概念出发，对网络及其算法进行了深入的讨论和研 究。从图论、最优化理论及蚁群算法等几个角度考虑这个问题，给出了基于 相应的经典算法的高效、实用的k 最短路算法，并给出了算法的时i 、日j 复杂 性分析。 论文首先介绍了图及网络的基本概念、相关算法以及目前国内外的研 究现状。对图论和网络的最短路经典的算法进行了详细的研究，详细地分析 了d i j k s t r a 、f l o y d 等算法，并总结各个算法的优点和不足。 通过对最优化理论中的动念规划方法的详细分析，结合已有最短路算 法，给出了基于动态规划方法的k 最短路算法，形成了一套实现方便、运 行高效的k 最短路算法。 对最小生成树的结构和k r u s k a l 、p r i m 、广度优先搜索、深度优先搜索 算法进行了深入分析，并总结各个算法的优点和不足。在求最小生成树算法 的基础上，给出了基于最小生成树的k 最短路算法，此算法具有高效和很 强的实用性。 最后，讨论了蚁群算法。蚁群算法是一种用于求解优化问题的新型模拟 进化算法，该算法在许多相当困难的优化问题的求解中体现了极强的寻优能 力和较好的性质。论文尝试着利用蚁群算法来解决网络最短路问题的算法， 给出了相应的算法。 关键词动态规划法；k 最短路；信息素；蚁群算法 哈尔滨理t 人学理学颂i j 学住论史 a l g o r i t h m r e s e a r c h0 1 1k - s h o r t e s tp a t h so f n e t w o r k 4b s t r a c t t h es h o r t e s tp a t hp r o b l e mi nn e t w o r kp l a y sa ni m p o r t a n tr o l ei nm o d e m c o m p u t e rn e t w o r ka n dt r a n s p o r t a t i o nn e t w o r k i ti s ac l a s s i c a lp r o b l e mi nt h e o p t i m i z a t i o n i th a sw i d ea p p l i c a t i o n si np r o d u c t i o na n do u rr e a l l i f e i nm a n y c a s e s n o to n l yt h es h o r t e s tp a t hi sn e e d e d ，b u ta l s ot h es e c o n ds h o r t e s t ，t h et h i r d s h o r t e s te t c ，w h i c hi sk - s h o r t e s tp a t h t h ea p p l i c a t i o n so fk s h o r t e s tp a t hc a nb e f o u n di nm a n yf i e l d ss u c ha sc o m m u n i c a t i o n ，n e t w o r k ，t r a m ce n g i n e e r i n ga n d a r t i f i c i a li n t e l l i g e n c e t h er e s e a r c ho nt h i sp r o b l e mh a sn o to n l yi m p o r t a n t t h e o r e t i cs i g n i f i c a n c eb u ta l s og r e a tp r a c t i c a la p p l i c a t i o nv a l u e t h i sp a p e rs t a r t sw i t ht h eb a s i cc o n c e p t so fg r a p ht h e o r y t h e n ，t h ed e t a i l e d r e s e a r c h e so nt h ec l a s s i ca l g o r i t h m so ft h es h o r t e s tp a t hi ng r a p ht h e o r ya n d n e t w o r kh a v eb e e nm a d e t h ek s h o r t e s tp a t hp r o b l e mi ss t u d i e df r o mt h ev i e w s o fg r a p ht h e o r y , t h eo p t i m i z a t i o nt h e o r ya n dt h ea n tc o l o n yo p t i m i z a t i o n ，a n d s o m ek s h o r t e s tp a t ha l g o r i t h m sb a s e do nc o r r e s p o n d i n gc l a s s i ca l g o r i t h m sa r e o b t a i n e d t h en e wa l g o r i t h m sa r ee f f e c t i v ea n dp r a c t i c a l m o r e o v e r , t h e i rt i m e c o m p l e x i t i e sa r eg i v e n f i r s to fa l l ，b a s i c c o n c e p t s ，r e l a t e da l g o r i t h m s a n dt h ed o m e s t i ca n d i n t e m a t i o n a ld e v e l o p m e n ts t a t ei nt h i sr e s e a r c ha r e aa r ei n t r o d u c e d d e t a i l e d r e s e a r c h e sh a v e b e e nd o n eo nc l a s s i cs h o r t e s tp a t ha l g o r i t h m si ng r a p ht h e o r ya n d n e t w o r k ，i n c l u d i n gd i j k s t r aa l g o r i t h ma n df l o y da l g o r i t h m t h e i ra d v a n t a g e sa n d d i s a d v a n t a g e sa r es u m m e du p d y n a m i cp r o g r a m m i n g b a s e dk - s h o r t e s tp a t ha l g o r i t h mi sg i v e nt h r o u g ht h e d e t a i l e da n a l y s i sf o rd y n a m i cp r o g r a m m i n gi no p t i m i z a t i o nt h e o r yb yc o m b i n i n g e x i s t i n gs h o r t e s tp a t ha l g o r i t h m ，w h i c hi se a s yt oi m p l e m e n ta n de f f e c t i v e d e e pa n a l y s i si sm a d eo nm i n i m u mg e n e r a t i o nt r e e ，k r u s k a la l g o r i t h m ，p r i m a l g o r i t h m ，d e p t hp r i o r i t ya l g o r i t h ma n dw i d t hp r i o r i t ya l g o r i t h m ，m e a n w h i l e t h e i r a d v a n t a g e s a n dd i s a d v a n t a g e sh a v e b e e ns u m m e d b a s e do nc o n s t r u c t i o n a l g o r i t h mo fm i n i m u mg e n e r a t i o nt r e e m i n i m u mg e n e r a t i o nt r e e b a s e dk 。s h o r t e s t i i p 警蜘“m m i s p r o p o s e d ，w h i c hh a sah i g he 硒c i e n c y a n dp r a c t i c a la pplicationvalue a ：1 a s l t h e a n ，t c 。1 。n y 。p t i m i z a t i 。ni sd i s c u s s e d i ti san e w k i n d 。fi mitatinge a v a l u a i o na l g o ，r n 梳1 1 8 e d 幻s o l v e o p t i m i z a t i 。np r o b l e m s ，a n ds h o w s ：蒜耋b i l i t 竺梳y t o s 个e a 。r c h o p t i m a l s o l u t i o n s i n d i 塌c u l t s i t u a t i o n sa n d h a s l o t s ：) 若二三 p 裟坨文n e a n tc o l o n yo p t i m i z a t i o ni s t r i e d t 0s o l v e t h es h o r t e s tp a t h 黼u e u m u ，a n d t h ec o r r e s p o n d i n ga l g o r i t h m i sg i v e n p 一“ k e l w o r d s d y n a m i c p r 。g r a m m i n g ，k - s h 。r t e s t p a t h ，p h e r 。m o n e ，a n tc 。1。nvo p t i m i z a t i o n 。 。7 i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文网络的最短路算法研究， 是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期问独立进行研究工作 所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写 过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确方 式注明。本声明的法律结果将完全由本人承担。 作者签名：秀臣甜式 同期： 2 0 0 8 年 弓月枷r 哈尔滨理工大学硕士学位论文使用授权书 网络的k 最短路算法研究系本人在哈尔滨理j 大学攻读硕士学位期间在 导师指导下完成的硕士学位沦文。本论文的研究成果归哈尔滨理工人学所有， 本论文的研究内容f 、= 得以其它单位的名义发表。本人完全了解哈尔滨理工人学 关于保存、使用学位沦文的舰定，同意学校保留并向有关部门提交论文和电子 版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、缩印 或其他复带0 手段保存论文，可以公布沦文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密团。 ( 请在以上相应方框内打4 ) 作者签名： 痞函以r 期： 2 0 0 8年 弓月弓d 日 导师签名：弓岖缅嚼 同期：2 0 0 8年弓月；。日 哈尔滨婵- e 人学理学顺i j 学位论文 第1 章绪论 1 1 研究目的及意义 在远占时代，一开始，人就构造出林中路，并且把树构造成网络，在农业 社会中，人又构造出各种大型的“水利网络”，航海的网络，资本主义才走向 世界，在工业社会，普通的小路被公路，铁路网络所代替，休闲散步的路被高 速公路所淹没，人的世界成为公路和铁路的网络，在今天的信息时代，各个国 家f 致力于建设自己的信息高速公路，即新型的信息网络，如今，移动通信 网，i n t e m e t w w w 网络已经基本覆盖整个世界。现在，人类就生活于网络之 中，人类的演化就是在给自己增加着的各种网络的演化。人的存在方式就是技 术的存在，人把自己的生活世界变成了网络，人也就成了网络动物，网络越有 效，越发达，世界就越小，人的社会性就越得到强化。今天的社会已经成了网 络社会，在今天的自然科学中，网络研究也成为重要课题。 电信业是l 删络型基础行业。作为网络型行业，电信业有比其它如电力等网 络行业更具有网络经济性，任何一个电信都f i 是孤立存在的，而是与其它蚓络 相互联系的，紧密连接成整体。互通互连决定着竞争足否能够有效实现。互通 互连的实施i 叮以极大的扩大电信网络的价值。随着各个通信网络互连互通的不 断推广。连接某个被叫可能涉及多个运营商，在各个运营商之f h j 就要进行收入 的分配。即需要参网问话费进行结算，今后电信业竞争会更加激烈。互联结算 问题也更为突出。因此通信网之问费用如何结算成为电信业需要解决的问题。 对网问话费进行公平，合理的结算，首先在模型上准确识别通信数据传递的路 径。 在高速公路领域中，各国高速公路的发展，大多以人口集中，工商业发 达，汽车数量多的城市外环和辐射路线以及城际交通量较大的路段开始，由点 串线，由线融面。最终形成一个国家或地区的高速公路网。伴随着我国高速公 路网络的不断完善。高速公路“一卡通”联网收费系统规模不断扩大。由此带 来许多急需解决的问题。高速公路树关结构逐渐演化为网关结构。当路网形成 环状时，就会产生二义性路径，由于出行目标的多元化，司机会视具体的情况 选择不同的行驶路径。导致车辆出行存在着多种可能性。随着高速公路交通量 的增加，根据交通出行路径选择规律。多路径出行比例将会明显增加。为计算 联网高速公路有效多路径上交通量，需要对高速公路网的多路径问题进行研 究。 哈尔滨理t 人学理学硕i j 学位论文 还有许多实际应用领域，都用到k 最短路的分析问题。如用户在使用咨询 系统或决策支持系统时，除了希望得到最优决策参考外，还希望得到次优。次 次优决策参考。反映在最短路问题上就是说，不仅要寻找从单源点到单目的点 的最短路，而且还要确定第二最短路，一直到第k 最短路。当引入其它 限制条件时，计算出的最短路可能是不可行或不可接受的方案，因此可行或可 接受的方案要从k 最短路集合中选取。在高级旅行信息系统中，对于旅行者的 多种类型的需求，比如，除了要求路径期望耗费最小以外，可能还要求行走时 间小于某个常数，或者要求换车次数不大于某个值，在这种情况下，简单地求 出期望耗费第一短的路径不能满足用户的需求。 k 最短路问题是网络分析，系统工程，图论等领域中的基本问题，对k 最 短路行进分析具有重要的理论意义和实际意义。 1 2 国内外研究现状分析 网络分析的重点是路径分析，而路径分析的核心为最优路径算法。以最短 路为主的最优路径问题一直足计算机科学，运筹学，交通工程学。地理信息科 学等学科的一个研究热点。它是资源分配，路线设计及分析等优化问题的基 础。很多网络相关问题，如最短路问题，最可靠路径问题，最大容量路径问 题，可达性评价问题和各种路径分析分配问题均可纳入最优路径问题的范畴之 中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的 最短路算法不断涌现。针对不同的网络特征，应用需求及具体的软硬件环境， 各种最短路算法在空间复杂度，时间复杂度，易实现性及应用范围等方面各具 特色。 最短路问题是图论中的一个经典问题，它的研究起源于2 0 世纪5 0 年代木 期，至今大约有两千多篇文献讨沦此问题，其中大部分都是出现在关于图的总 体组合优化的杂志或会议论文中还有一些是发表在各种专业学术期刊中。它已 经应用于许多涉及到统筹规划的领域，其中最普遍的一个应用领域就是交通运 输领域。最短路问题的计算机求解从来都是交通运输分析与规划中必不可少的 一个环节。这也正随着大规模数学模型的应用越来越广泛。寻求一种高效，快 速的最短路算法变得越来越重要的原因。目前在交通运输问题及计算机网络通 讯问题中所普遍采用的最短路问题算法主要是d i j k s t r a 算法( d i j k s t r a ， 1 9 5 9 ) ，此算法找出一个给定顶点与图中各个其它顶点相连的最短路，求图中 任意一对顶点之问的最短算法由福劳德( f l o y d ，1 9 6 2 ) 和但茨希( d a n t a i g ，1 9 6 7 ) 提出【2 3 ，4 5 】，二重扫描算法可以求出图中一个给定顶点和所有其它顶点之间第 2 哈尔演理t 人学理学坝l j 学位论文 k 条最短路的长度推广的福劳德算法( g e n e r a l i z e df l o y da l g o r i t h m ) 和推广的但 茨希算法( g e n e r a l i z e dd a n t i ga l g o r i t h m ) 【6 7 8 9 1 ，这两个算法可以求出图中每一对 顶点之间第k 条最短路的长度，以上各种最短算法都利用了加法运算和求极小 值运算。还有一种就是彳算法【l o ，1 1 ，1 2 ，】，这种算法主要应用于极大规模的网 络中，网络中的节点数量往往达到指数级，但是这种情况一般只在计算机网络 通讯中出现，而在实际的交通路网中不常见。 在我国关于最短路算法的研究除了计算机网络通讯技术领域的应用外，在 交通运输中的应用丰要是交通运输网络优化中的网络平衡分析及智能交通运输 系统( i t s ) 中车辆诱导子系统内的最优路径( o p t i m a lp a t h ) 求解，其中吉林大学 交通学院i t s 研究实验室及同济大学的i t s 研究中心在这方面取得了一定成 果，在交通领域的另外一个应用就是动态交通分配( d t a ) 巾的路径优化选择 ( r o u t i n g ) ，清华大学的交通研究所在此方面取得了一定成果。 最短路问题是一个著名问题，它在实际牛产生活中有广泛应用。在许多情 况下，我们不仪仪要考虑最短路也要考虑次短路、次次短路、，即k 最短路 i u j 题i i 引。k 最短路算法涉及很多领域，如在交通 ：程、通信、人工智能等方面 有实际意义。人们从不同的角度研究了它的许多变形，大多数算法都是针对有 向图简单路径的【1 5 】。d a v i de p p s t e i n 给出了一个算法，对于有向图上的路径允许 环的存在【l6 1 。j o h nh e r s h b e r g e r 等人在路径替换的基础上给出了一个新的简单 路径的仃效算法【1 7 j 。z u w a i r i ei b r a h i m 等从d n a 计算角度考虑这一问题【1 8 1 。 w m a t t h e wc a r l y l e 等人给出接近最短路的简单路径的k 最短路算法【1 9 1 。g a n g l i u 等人给出了一个满足多个限制的算法【2 0 1 。m h m a c g r e g o r 考虑了在通信网 络中k 最短路问题【2 1 1 。关于网络有效路径问题研究已取得不少有意义的成 果，文献【2 2 ，2 3 ，2 4 ，2 5 ，2 6 1 给出有效路径的定义为o d 对之间的有效路径指它所包含 的所有路段都令司机离其起始点越来越远、离其终点越来越近；文献【2 7 】中对有 效路径进行重新定义，并引入路径伸展系数，但只是给出路径伸展系数的经验 值。 1 3 本文主要研究内容 本课题来源于黑龙江省教育厅资助项目。 本论文首先针对最短路的发展现状及其相关技术进行讨论，然后深入描述 最短路经典算法的数学模型，以及对动态规划算法进行的深入的分析，并将动 态规划方法与最短路算法相结合，提出更加有效的求足最短路的算法。 具体地，要进行如下几个方面的工作： 哈尔滨理t 人学理学顾i j 学位论文 对图与网络的基本概念进行深入的分析，讨论经典的最短路的算法，并分 析其不足之处和改进的地方。 将最短路算法与动态规划算法进行结合，研究利用动态规划算法中比较成 熟的算法对网络经典算法进行处理，更好地把最优化方法中的一些成熟技术和 方法应用到k 最短路算法研究中。 结合与支撑树算法相关的一些基础算法，对k 最短路算法进行研究，并得 出基于支撑树的最短路算法。 通过对当今正在蓬勃发展的蚁群算法的基本原理进行深入的分析，讨论蚁 群算法的数学模型，并山此给出基于蚁群算法的最短路算法，最后，分析蚁群 算法的一些不足和改进地方。 4 哈尔滨胖3 - 人学删! 倾f j 学竹论文 第2 章图与网络的基本概念及其算法 2 1 图的基本概念 定义2 1 一个图是由点集v = i ) i ) 和矿中元素的无序对的一个集合e = e ) 所构成的二元组，记为g = ( v ，e ) ，v 中的元素，f 叫做顶点，e 中的元素e 女叫 做边。当v ，e 为有限集合时，g 称为有限图，否则称为无限图。本论文只讨 论有限图。 定义2 2两个点“，v 属于v ，如果边( “，v ) 属于e ，则称“，v 两点相邻， u , v 称为边( ，) 的端点。两条边e ，e ，属于e ，如果它们有一个公共端点 “，则称 e ，e ，相邻，边e ，已，称为点“的关联边。 定义2 3 用朋( g ) = lei 表示图g 中边数，用门( g ) = ivi 表示图g 的顶点个 数。对于任一条边( y ，) 属于e ，如果边( 1 ，f ，1 ，) 端点无序，则它是无向 边，此时图g 称为无向图。如果边( 1 ，1 ，) 端点有序，即它表示以为始 点，v ，为终点的有向弧，这时图g 称为有向图。 定义2 4 一条边的两个端点如果木h 同，称此边为环，两点之问多于一条 边的，称为多重边。 不含坏和多重边的图称为简单图，含有多重边的图称为多重图。 定义2 5在一般图g = ( v ，e ) 中，与顶点x 相关联的边的数目叫做该顶点 的度数或者次，记为d e g ( x ) ，如果a = ( 五x ) 是一个坏，则a 使x 的度数增加2 。 定义2 6 设g 是一个一般图，形如公式2 1 的m 条边的序列称为长度为 x o , x ，) ， x ，以) ， i r a - i ) ( 2 - 1 ) m 的条途径，且这条途径连接顶点确和x 肌也可以把这条途径表示为公式2 2 x o x ，一而一一一l 一 ( 2 - 2 ) 途径是开的还是闭的取决于：c o = 还是x o ，一条途径中可能有重复的 边，如果途径中没有重复的边，就称它为一条迹。此外，如果途径中也没有重 复的顶点，就称此途径是一条路径，一条闭的路径叫做圈。 定义2 7 一个一般图g 是连通的，即对它的任意一对顶点x 和y ，都有一 条连接它们的途径( 或等价的说，一条连接它们的路径) 。否则称g 是非连通 的。在一个不连通的一般图中，至少存在一对顶点x 和y ，使人无法沿着g 中 的边从工“走到”y ( 或者从y 走到x ) 。 定义2 8在一个连通图中，d ( x ，y ) 表示连接顶点x 和y 的途径的最短长 度，并称其为x 和y 的距离。对任意一顶点x ，我们规定d ( x ，x ) = o 。 哈尔滨理t 人学理学顺i j 学位论文 定义2 9 有向图d ：( y ，爿) 有一个叫做顶点的元素集合v 和一个叫做弧的有 序顶点对的集合a ，其中，每条弧的形式为 a=(x,y)(2-3) 其中，x 和y 是顶点，我们把弧a 看作离开x 并进入y ，即从x 指向y 。在有向 图中，既可能同时包含弧( x ，y ) 和弧( y ，曲。也可能包含形如( x ，x ) 的环，坏( x ，x ) 进入和离开的是同一个顶点x 。 定义2 1 0一般有向图d = ( v ，a ) 的一个顶点x 可能有两种度数。x 的出 度是起始于顶点x 的弧的个数。x 的入度是终止于顶点x 的弧的个数。 定义2 1 l在一般有向图中，顶点的入度之和等于出度之和，且都等于图 中弧的个数。 定义2 1 2 设d = ( v ，a ) 是一般有向图，形如 ( x o ，x ，) ，( x ，x 2 ) ，( x 川，x 。) ( 2 - 4 ) 的n 个弧的序列称为从顶点誓，到x ，的长度为n 的有向途径，途径的起始顶点是 ，终止顶点是x 。当= x 。时，有向图足闭的，否则有向图是开的，我们也 可以把有向图表示为 x o z ，一叠一一一1 一 ( 2 5 ) 如果途径中的弧都是不同的，则称此途径是有向的：如果有向迹中的顶点也都 不棚同( 除x o = x 。除外) ，则称它为路径：封闭的路径叫做有向幽。 定义2 1 3图g = ( v ，e ) ，若e 是e 的子集，v7 是v 的子集，且e 中的 边仅与y 中的顶点相关联，则称g = ( v 7 ，) 是g 的一个子图，特别是，若 v v ，则称g7 称为g 的生成子图( 支撑子图) 。 2 2 树 定义2 1 4 连通且不含圈的无向图称为树，树中度为1 的点称为树叶，度 大于1 的称为分枝点。树t = ( v ，e ) ，lv | - n ，lei = m ，则以下关于树的说法 是等价的。 1 丁是一棵树； 2 丁无圈，且m = n l ； 3 丁连通，且m = n l ； 4 丁无圈，但每加一新边即得唯一个圈； 5 r 连通，任意舍去一边就不连通； 6 丁中任意两点，有唯一链相连。 定义2 1 5 若图g 的生成子图是一棵树，则称该树为g 的生成树( 支撑 6 哈尔演理t 人学珲学颀i j 学位论文 树) ，容易知道，图g = ( v ，e ) 有生成树的充分必要条件为g 是连通图。 定义2 1 6 连通图g = ( y ，e ) ，每条上有非负权上( e ) 。一棵树生成树所有 树枝上权的总和，称为这个生成树的权。具有最小权的生成树称为最小生成树 ( 最小支撑树) 简称为最小树。 2 3 图的表示形式 描述一个图的最直观的方法是用一个图形来表示，但是要把图输入到计算 机中去，最简单的方法是用一个矩阵或一个表格来记录图。 2 3 1 令| j 接矩阵 设g = ( 矿，e ) 是任意图，其中v = v iv 2 ，k ) ，e = e i , e 2 ，巳) ，则刀阶 方阵a = 和f ，) 称为g 的邻接矩阵。其中a 6 为图中以v i 为起点且以v j 为终点的 边的数目。 2 3 2 关联矩阵 设g = ( v ，e ) 是一个非空无环图，定义 i1 ，若点v i 和边e ，关联 聊f ，。j &否则(2-6) 这样得到的ivi lei 矩阵m ( g ) = ( m f ，) 称为g 的关联矩阵。关联矩阼完整地表 达了图中顶点与边的关系。图的关联矩阵有下列明显的性质： 1 每一列恰好有两个非零元素l ： 2 每一行的元素之和等于对应顶点的度： 3 将一个关联矩阵中两行或两列互换，相当于在同一个图中将两个对应 的顶点或边的编号互换。 2 3 3 可达矩阵 对于无重边的有向图d = ( y ，e ) ，其中v = v 1v 2 ，以) ，称n xn 阶矩阵 p = ( p o ) 。为d 的可达矩阵，其中 f 1 ， 珊2 1 0 ， 2 4 最短路径 最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以使用 7 、， 7 - 2 i e e 盛 、，、， v v ， ， 屹屹 ，-，j 哈尔滨胖t 人学理学坝ij 学位论文 这个模型，如设备更新，线路安排，管道铺设等。 定义2 1 7 设g = ( y ，e ) 是连通图，图中各边( ，f ，v _ ，) 有权乃( 1 0 = 表示v i ，v 问无边) ，y 。，v ，为图中任意两点，求一条道路，使它从y ，到y ，的所有路中总 权最小的路。即三( ) = z l , j 最小。 2 5 d i j k s t r a 算法 荷兰数学家d i j k s t r a 1 于1 9 5 9 年所发明了一个算法是解决指定两点v ，v ，问 的最短路i u j 题的最有效算法之一。目前被认为是求无负权网络最短路问题的最 好的办法，算法基本思路璀于以下基本原理：序列 v s ，嵋，k _ ，k ) 是从v ，剑 1 ，盯的最短路，则序列以，v l ，一，心小v n ) 必为从v 。到v n - i 的最短路。 2 5 1 d i j k s t r a 最短路算法 以下用伪代码实现，d i j k s t r a 算法设置了一个顶点集合s ，从源点s 到集 合中的顶点的最终最短路的权值均已确定，算法反复选择具有最短路f f i 计的顶 点“v s ，并将“加入到s 中，对u 的所有边出边进行松驰。在下面的算法 实现中，用到了顶点的最小优先队列q ，排序的关键字为顶点的d 值。 算法2 1 d i j k s t r a 算法 d i j k s t r a ( gws ) 1 i n i t i a l i z e s i n g l e s o u r c e ( g ，s ) 2s 卜西 3 q 卜v g 】 4w h i l eq 矽 5d ou 卜e x t r a c t - m i n ( q ) 6 s - - - s u u ) 7f o re a c hv e r t e xv , 4 d j t u 8d or e l a x ( g ，v ，w ) 2 5 2d i j k s t r a 算法分析 d i j k s t r a 算法的执行速度如何呢? 它通过调用三种优先队列操作维护最小 优先队列q ，i n s e r t ( 第三行) ，e x t r a c t - m i n ( 第五行) ，和d e c r e a s e k e y ( 第8 行调用的r e l a x 中) ，同e x t r a c t - m i n 类似，i n s e r t 也是每个 哈尔滨理t 人学胖学顾i j 学位论文 顶点调用一次，因为每个顶点1 ，v 被加入到集合s 中仪有一次，所以在算法 中，邻接表彳力 1 ，】的每条边在第7 8 行算法中的f o r 循环中仅检查一次，由于 所有邻接表中的边的总数为iei ，因而f o r 循环中总共有le1 次迭代，共有至多 ie1 次d e c r e a s e k e y 操作。 d i j k s t r a 算法的运行时i 、h j 依赖于最小队列的具体实现，首先考虑第一种情 况，利用从l 至ivi 编好号的顶点，简单地将d i v i 存入一个数组的第v 项，每一 个i n s e r t 和d e c r e a s e k e y 操作都是o ( 1 ) 时| 、日j ，而每一个e x t r a c t - m i n 操作为d ( v ) 时间( 因为需要搜索整个数组) ，总计运行时间为 o ( v 2 + e ) = o ( v 2 ) 。 如果用斐波那契堆来实现优先队列，可以将运行时问提升到o ( v l g v + e ) 。 y1 个e x t r a c t - m i n 操作的每个平摊代价为o ( i g v ) ，而且至多ie1 个 d e c r e a s e k e y 操作的每个平摊时问为o ( 1 ) ，从经验上来看，d i j k s t r a 算法 中，d e c r e a s e k e y 的调用比e x t r a c t - m i n 的调用一般要多得多，所以任 何能够在不增加e x t r a c t - m i n 操作的平摊时间的同时，减小每个 d e c r e a s e k e y 操作的平摊时问剑o ( 1 9 矿) 的方法，从渐进的意义上来说，都 能够扶得比二叉树更快的实现。 2 6f l o y d 算法 在某些问题中，要求网络上任意两点i n j 的最短路，也就是所谓的伞源最短 路，这类问题可以用d i j k s t r a 算法依次改变起点的办法计算，是过于繁琐，这 里介绍的f l o y d 算法( 1 9 6 2 年) 可以直接求出网络中任意两点问的最短路。 2 6 1 f l o y d 算法基本步骤 令网络的权矩阵为d = ( 如) ，乞为到v ，的距离。在交通网络中它可 以表示两地问的运输开销。在计算机网络中它可以表示两节点问传输数据的开 销等。 其中办= 竺当( i ，i 其, v 它j ) e c 2 8 ， 算法基本步骤为： 、 1 输入权矩阵d ( o ) = d ； 2 计算d 。= ( d 扩) 删， ( k = 1 ，2 ，3 ，n ) ； 其中d 扩= m i n d 5 k - 0 , d 娑一+ d 够一】 9 ( 2 9 ) 哈尔演罡l ! t 人学理学f 磺l j 学位论文 3 d 伽) = ( d 扩) n 。n 中元素d 扩就是v f 到1 ，的的最短路长。 2 6 2 f l o y d 算法复杂度分析 f l o y d 算法的计算量可大致估计如下：因为v 1 k n ，需要计算 ( 聆一1 ) ( ，l 一2 ) 个算式d 扩= m i n d 5 , k - 1 ，d - 1 + d 。 ，k - o ，每个算式要作一次加法和 一次比较，所以f l o y d 算法的复杂性为o ( n 3 ) 。 2 7 本章小结 历史上，图和网络的理论曾经被许多数学家各自独立地建立和研究过。瑞 士数学家e u l e r 于1 9 7 3 年解决了七桥问题，被认为足图论的第一篇论文。后 来，k i r c h h o f f ( 18 4 7 ) 矛ic a y l e y ( 18 5 7 ) 在各自研究中独立地发现了树。 本章主要介绍了图的基本概念、术语、记号、图的表示以及顶点度、路、 迹、圈的若干基本结果，这些是后续各章算法的基础。本章讲述了各种求最短 路的算法，是分析k 最短路的基础。d i j k s t r a 算法出现在1 9 7 5 年，但并未提及 优先队列，不同的数据结构实现d i j k s t r a 算法有着不f 一的运行时问。f l o y d 算 法的运行时间为o ( n 3 ) ，即使对于中等规模的输入图米说，f l o y d 仍然具有相当 的实用性。 1 0 哈尔演理丁人学理学舰f 学位论文 第3 章基于动态规划法的k 最短路算法 鬈最短路问题一般是指有向图中上的路径。因为在许多问题，如计算机网 络领域，交通领域，两点间的边大多数是没有方向约束的。这些问题直接的数 学模型就是无向图，这样处理更有普遍意义。利用动态规划思想，先计算出各 个点到源点的距离，利用这些数据包含的信息，从目的点反向逆推。考虑各个 路径对最短路路径长度的增加量，依次给出所找的k 最短路。最短路路径的长 度增加当然是零。如果算法能够不重复，不遗漏的有序地给出路径的长度增量 中的最小的k 个，那么就相当于给出k 最短路路径。 3 1 动态规划方法 动念规划法是由美国数学家r b e l l m a n ( 1 9 5 7 ) 等人提出的。动态规划法解 决问题的方法是把( 多阶段决策) 问题变换为一系列相互联系、形式上相似的 ( 单阶段) 子问题，然后逐个加以解决，而每个子问题的求解往往比较简单。 动态舰划法是考查问题的一种新途径，是求解问题某类问题的一种方法，因此 必须对具体问题进行具体的分析处理。 3 1 1 基本概念 使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划 模型，要用剑一些概念： 下面来说明这些概念。 定义3 1 阶段：将所给的问题的过程，按时问或者空问特征分解为若干个 相互联系的阶段，从而使求解方便，描述阶段的变量称为阶段变量，以下用f 表示。 定义3 2 状态：每个阶段开始时间问题或系统所处的自然状念或客观条件 叫做状态，它描述了问题过程中的不可控因素。状态既是该阶段的某个起点， 又是前一阶段的某个终点。通常一个阶段有若干个状态。描述各阶段状态的变 量称为状态变量，它可以是一个数，也可以是一个变量。常用s ，表示第t 阶段 的变量，第t 阶段所有可能状态的集合( 称为可达状态的集合) 记为s ，动态 规划中的状态应具有如下性质：当某个阶段状态给定以后，在这阶段以后过程 的发展不受这阶段以前各段状念的影响。也就是说，当前的状态是过去历史的 一个完整总结，过程过去的历史只能通过当前状态去影响它未来的发展，这称 为无后效性。如果所选的变量不具备无后效性，就不能作为状态变量来构造动 态规划模型。 吮尔演理丁人学删学烦l 学位论文 定义3 3 决策：当各段的状念取定以后，就可以做出不同的决策( 或选 择) ，从而确定下一阶段的状态，这种决定称为决策。在最优控制中也称为控 制。描述决策的变量称为决策变量。以f 用葺( 墨) 表示第t 阶段状态为s ，时的 决策，它是状态变量的函数，实际上中决策变量的取值往往限制在称之为允许 决策集合的某一范围之内。若用d ，( s ，) 表示第t 阶段从状态s ，出发时的允许决 策集合，则有x f ( s f ) d f ( s f ) 。 定义3 4 策略：各个阶段决策一个有序集合称为策略。由过程的第t 阶段 开始到终止状念为止的过程称为问题的后部子过程或者t 子过程，而称由相应 每段的决策按顺序排列组成的决策函数序列 誓( s ，) ，x r ( s ，) ) ( 这罩t 为总的 阶段函数) 为t 子过程策略，简称子策略。记为p t 丁( s ，) ，即 p ，7 ( s ，) 2 x ，( s ，) ，x ，+ i ( s ，+ 1 ) ，x r ( s7 1 ) ) ( 3 1 ) 当t = 1 时，此决策函数序列称为全过程的一个策略，简称策略，记为 p 1 7 _ ( s 1 ) 。实际中，可供选择的策略有一定的范围，此范围称为允许策略集 合，用p 表示，称p 中到达最优效果的策略称为最优策略。 定义3 5 状态转移方程：若给定第t 阶段状态变量s ，的值，则一旦确定了 该阶段的决策变量x ，则t + l 阶段状念变量s 川也就随之完全确定。即s 川的值 随s ，和x ，的变化而变化，这种对应关系为s 川= o t ( s ，x t ) ，它描述了由t 阶段到 t + l 阶段的状态转移规律，称之为状态转移方程，缈，称为状态转移函数。 它表示了由k 段到k + 1 段的状念转移规律，所以称为状念转移方程。 定义3 6 效益函数与最优值函数：用来衡量所选策略优劣( 表现在所实 现过程的优劣) 的某种数量指标称为效益函数，它是定义在全过程和所有后部 子过程上的数量函数，用g 汀表示t 子过程的效益函数，则有 g t t = g r 7 ( j ，x t ，s f + l ，s t + i ) ，t = l ，2 ，3 ，r ( 3 2 ) 对于要构成动态规划模型的效益函数，应具有可分离性，并满足递推关 系，即应有 g f r ( ，s t + l ，s t + i ) = 缈，( s t ，t ，g ，+ i 7 ( t + l ，s t + i ) ) ( 3 - 3 ) 实际问题中最常见，满足上述要求的效益函数有两种：一种是任一子过程 的效益函数是它所包含所有各个阶段效益之和，即 g 仃( t ，t ，s t + i ) = 艺：，g j ( s j ，t ) ( 3 - 4 ) 这里g j ( s i , x j ) 为第阶段的阶段效益，这时( 3 4 ) 式可以写成 g f ，7 ( 5 ，s 川) = g j ( s ，x y ) + g f + 1 r ( s f + l ，誓+ l ，s 川) ( 3 5 ) 另一种是任一子过程的效益为它所含各阶段效益的乘积，即 1 2 哈尔滨删丁人学理学颂l j 学位沦支 g f ，r ( 薯，s t + i ) = 1 1 1 ，= ，g j ( s ，x j ) ( 3 6 ) 此时相应地有 6 t ，r ( s ，s t + i ) = g 心，x j ) g , + 1 7 ( s f + l ，x t + i ，s t + i ) ( 3 - 7 ) 效益函数的最优值，称为最优值函数，记为z 小，) ，它所表示从第t 阶段的墨 状态开始，到第t 阶段的终止状态的过程，在采取最优策略时所得到的效益函 数值，即 z r ( s t ) = o p tg f 7 ( 薯，s 川) ( 3 8 ) x t p ，x l 其中“o p t ”是最优化( o p t i m i z a t i o n ) 的缩写。 当t = 1 时，z l ( s 1 ) 就是从初始状态s l 到全过程结束的整体最优函数。 3 1 2 基本思想 动态规划方法的基本思想如下： 1 将多阶段决策过秤划分阶段，恰当地选取状态变量、决策变最及定义 最优指标函数，从而把问题化成一族i 刊