（计算机应用技术专业论文）随机时间依赖网络中的自适应k期望最短路径.pdf

摘要 在交通网络和数据网络中，网络特征( 如弧的权值、结点耗费等) 既具有随机性又具 有时间依赖性，这样的网络称之为随机时间依赖网络，简记为s t 3 网络。在实践中，s t d 网络模型比传统网络模型具有更广泛的应用。由于随机性和时间依赖性引入到网络模型 中，使得最短路径问题变得复杂化和多样化，传统的最短路径算法己不再适应这样复杂 的网络环境，这就迫使人们寻求新的解决方法。 在随机时间依赖的交通网络中，对于一组给定的起始点和目的点，通常要选择一条 期望时间最短的路径行走。但在现实的网络中，由于其它原因最短路径走不通时，可以 选择第二最短路经，第三最短路径直到第k 最短路径，因此需要一个k 最短路径集。本 文在基于自适应路径和k 期望最短路径的基础上提出了求解随机时间依赖网络中自适应 k 期望最短路径的算法( ak e s p 算法) ，算法得出的结果是一组策略集，这样就可以根据 到达的具体时刻的不同而选择不同的路径，具有自适应性。a k e s p 算法不仅适用于先进 先出的网络而且适用于非先进先出的网络。 首先，本文给出了s t d 网络模型，提出了s t d 网络中的路径优化条件和求解k 期望 最短路径的相关理论：其次设计并实现了s t d 网络中的ak e s p 算法：然后，文章从理 论上分析证明了a k e s p 算法的正确性和算法的时间复杂度：最后设计试验对ak e s p 算 法的性能进行测试，并且给出了一个实例测试。理论证明和试验测试都表明，ak e s p 算法对于解决s t d 网络中的自适应k 期望最短路径问题有重要意义。 关键词：自适应；随机时间依赖网络；k 期望路径；最短路径 大连理工大学硕士学位论文 a d a p t i v ek e x p e c t e ds h o r t e s tp a t h si ns t o c h a s t i c ，t i m e v a r y i n g n e t w o r k s a b s t r a c t as t o c h a s t i ca n dt i m e d e p e n d e n tn e t w o r kf i e s t dn e t w o r k ) i san e t w o r kw h e r ea r ct r a v e l t i m e sa r er a n d o mv a r i a b l e sw i t ht i m e d e p e n d e n t p r o b a b i l i t yd i s t r i b u t i o n s s t o c h a s t i ca n d t i m e d e p e n d e n tp r o p e r t i e sa r ef o u n di nm a n ym o d e r nc o m m u n i c a t i o na n dt r a n s p o r t a t i o ns y s t e m s f a s te x p a n s i o no fs u c hs y s t e m sh a sm a d et h es t u d yo fs t dn e t w o r k sv e r yu s e f u la n de v e nm o r e c h a l l e n g i n g s ot h es t u d yo f s h o r t e s tp a t hp r o b l e mi ns t d n e t w o r k si so f t i m e l yi m p o r t a n c e i ns t o c h a s t i c ，t i m e - d e p e n d e n t ( o rs t d ) t r a n s p o r t a t i o nn e t w o r k s ，o n ec a nm a k er o u t i n g d e c i s i o n se nr o u t ea st r a v e r s a lt i m e so nt r a v e l e da r c s a r ee x p e r i e n c e da n da r r i v a lt i m e sa t i n t e r m e d i a t el o c a t i o n sa r er e v e a l e d f o re a c hg i v e no 畦g i l ld e n n a t i o np a i ra tas p e c i f i cd e p a r t u r e t i m e ，as m n ep a t hm a yn o tp r o v i d ea na d e q u a t es o l u t i o n ，t h u s ，as e to fks h o r t e ns t r a t e g i e s ， r e f e r r e dt oa sh y p e r p a t h s ，a r eg e n e r a t e dt op r o v i d ed i r e c t i o n st ot h ed e s i m a t i o nn o d ec o n d i t i o n e d u p o na r r i v a lt i m e sa ti n t e r m e d i a t el o c a t i o n s i nt h i sp a p e r , w ep r o v i d ea na l g o r i t h m ( a _ k e s p ) b a s e do na d a p t i v ep a t h sa n dk e x p e c t e ds h o r t e s tp a t h sf o rd e t e r m i n i n gt h ea d a p t i v eke x p e c t e d s h o r t e s tp a t h si ns t dn e t w o r k s a n dt h ea l g o r i t h mi sn o to n l ya p p r o p r i a t ef o rf i f on e t w o r k sb u t a l s oa p p r o p r i a t ef o rn o n - f i f on e t w o r k s f i r s t ，t h es t dn e t w o r km o d e l ，t h eo p t i m a l i t yc o n d i t i o n so fs t dn e t w o r ka n dt h ea s s o c i a t e d t h e o r i e sa l ep r o p o s e di nt h i sp a p e r s e c o n d l y ，t h eak e s pa l g o r i t h mi sp r e s e n t e d n e x t ，t h i sp a p e r p r o v e st h ec o r r e c t n e s so fa k e s pa l g o r i t h ma n da n a l y z e si t st i m ec o m p l e x i t y f i n a l l y ，a n e x l j e f i r n e n ti sd e s i g n e dt o t e s tt h ea l g d r i t h m sp e r f o r m a n c ea n da ni l l n s t r a t i v ee x a m p l eo ft h e a l g o r i t h mi sp r o v i d e d a n dt h ee x p e r i m e n tr e s u l t ss h o w t h a tt h ea _ k e s p a l g o r i t h mi se f f i c i e n t k e yw o r d s ：a d a p t i v er o u t i n g ；s t o c h a s t i ca n dt i m e - d e p e n d e n tn e t w o r k ；k - e x p e c t e d p a t h s ；s h o r t e s tp a t h s 1 1 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均己在论文中做了明确的说明并表示了谢意。 作者签名：鍪亵日期：鲨! 至! ：i ! r 日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复e 口件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：麴 导师签名：遁! 咝 型年业月丛日 1 绪论 1 1 最短路径问题的研究背景及意义 11 1 最短路径问题的提出 最短路径问题是现实生活中很常见的一个问题。例如，如果司机用汽车运输使物从 a 地到b 地，他就会考虑走路程最短或时间最省的那条路径，这是考虑路程或时间的最 短路径问题。又如，要在a 地到b 地之间铺设煤气管道，首先，将a ，b 两地间的长方 形区域划分格子点。然后，根据地形、土壤、是否经过江河、泥塘、农田、村庄、郊区、 城镇、公路、铁路等各种情况，将从一格子点到另一格子点的铺设费用估计出来，最后， 求出由a 地到b 地铺设煤气管道经过哪些格子点才能使总的造价最小，这是考虑费用 的最短路径问题。另外，在线路安排、设备更新、厂区布局、城市规划、电子导航、交 通转车等方面均需要考虑到最短路径问题。 从上述可知，“最短”一词在不同情况下有不同的含义，或者是距离最短，或者是 时间最省，或者是费用或代价最少，等等。 1 1 2 最短路径算法的分类体系 最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。 国内外大量专家学者对此问题进行了深入的研究。经典的图论与不断发展完善的计算机 数据结构及算法的有效结合使得新的最短路径算法不断涌现。它们在空间复杂度、时间 复杂度、易实现性及应用范围等方面各具特色u “。 针对串行计算机的最短路径算法，已经几乎达到理论上的时间复杂度极限【1j 。现在 的研究热点，一是针对实际网络特征优化运行结构【3 “】，在同一时间复杂度的基础上尽 可能地提高算法的运行效率；二是对网络特征进行限制，如要求网络中每条弧具有先进 先出的特性 5 _ 8 1 以便于降低问题的求解难度；三是采用有损算法，如限制范围搜索 2 6 l 、 限定方向搜索口7 1 以及限制几何层次递归搜索【2 8 】；四是采用拓扑排序算法【2 9 1 ，或者采用 拓扑层次编码路径视图1 3 0 】，对最短路径进行部分实例化编码存储：五是采用并行算法， 为并行计算服务【3 。”j 。 由于问题类型、网络特征及实现技术的纷繁复杂，最短路径算法表现出多样性。总 的来说，可以分别按照问题类型、网络特征及实现技术对最短路径算法进行系统的分类 【1 1 。 ( 1 1 问题类型 张勇：随机时间依赖网络中的自适应k 期望最短路径 按照起终结点及路径的数目和特征，最短路径问题可分为如下5 种类型：单对结点 间的最短路径问题、所有结点间的最短路径问题、k 最短路径问题、实时最短路径问题 和指定必经结点的最短路径问题。其中又可衍生出其他一些特殊的最短路径问题，如限 制弧段数目的最短路径、含环路径等。基于问题类型，最短路径算法的完整分类体系如 图1 1 所示。 图1 1 基于问题类型的最短路径算法分类体系 f i g 1 1c l a s s i f i c a t i o ns y s t e m f o r t h es h o r t e s tp a t ha l g o r i t h m s b y p r o b l e m t y p e 在这里面，本文主要关注多源点到单目的结点间的k 最短路径问题。 ( 2 ) 网络特征 按照网络特征及表示方法的差异，最短路径算法可按图1 2 所示体系进行分类。 图1 2 基于网络特征的最短路径算法分类体系 f i g1 2c l a s s i f i c a t i o ns y s t e mf o rt h es h o r t e s tp a t ha l g o r i t h m sb yn e t w o r kc h a r a c t e r i s t i c s 这里所说的概率分布既可以是连续的也可以是离散的。在网络工程中，权可以表示 时间、费用、里程或者代价等等。在这墨丽，本文主要关注网络中每条弧的权重服从离 敞的概率分布。 ( 3 ) 实现技术 另一种最短路径算法分类方法是按照实现技术进行分类。完整的分类体系如图1 3 所示。其中路径搜索技术中的通用技术是最短路径算法研究的重点所在，也是本文所要 关注的。 卤1 i 砷 卤己卤1 r 函 盯1 卤砷卣菌 百面卣两羁甑矗商 画萄五由点商卣五癌菌岛岛 图1 ，3 基于实现方法的最短路径的最短路径算法分类体系 f i g 1 3c l a s s i f i c a t i o ns y s t e mf o rt h es h o r t e s tp a t ha l g o r i t h m sb ys o l u t i o nt e c h n i q u e s 如图1 3 所示，路径搜索通用技术进一步又可分为代数技术和组合技术两种。代数 技术通过运筹学中的线性规划形式化、所定义代数系统中的联立线性方程组形式化和矩 阵乘法等方法来解决最短路径问题。组合技术主要是指标号算法( l a b e l i n ga l g o r i t h m s ) 。 标号算法也是绝大多数最短路径算法的核心部分【3 5 3 7 】。按照不同的标识结点处理策略， 标号算法又可分为标号设置( l a b e ls e t t i n g ，简记为l s ) 算法和标号修正( l a b e l c o r r e c t i n g ，简记为l c ) 算法两大体系。这两种算法都是循环的、迭代的，都是在每次 迭代过程中给结点指定距离标记，这个距离标记是对源结点到该结点最短路径的种估 计，或者说是其最短路径的一个界限。这两种算法的不同之处在于：标号设置算法每一 步产生一个永久的标记( 最优的距离标记) ，而标号修正算法则将所有的距离标记都看成 是暂时的距离标记，直到最后一步所有的标记都成为永久的距离标记。 d i j k s t r a 算法是典型的标号设置算法，这类算法适用于解决以下两种网络中的最短 路径问题：非循环图上的任意边长的最短路径问；非负边长的最短路径问题。这 类算法包括d i a l 算法、基于二分堆的d i j k s t r a 算法、基于dh e a p 的d i j k s t r a 算法、基 张勇：随机时间依赖网络中的自固壹k 期望最短路径 于f i b o n a c c i 堆的d i j k s t r a 算法、j o h n s o n 算法和最新的基于基数堆的d i j k s t r a 算法都是 属于标号设置算法。 标号修正算法则更加通用，适合与各种问题类，包括含有负边环的网络中的最短路 径问题。b e l l m a n f o r d m o o r e 算法和p a l l o t t i n o 算法都属于标号修正算法。标号设置算法 有更好的最坏时间复杂度，效率更高。标号修正算法不仅适用于通用的问题类，而且具 有更好的算法灵活性。标号设置算法可以看成是标号修正算法的一个特例。 实际上，所有的l s 或l c 算法都可总结为一种更为一般性的算法的特例。不同之 处在于它们处理图中所标识结点时采用的优先级队列系统各不相同。另外，l s 算法不能 处理含负边权的网络，而l c 算法则可以处理含负边权的网络【1 1 。 1 1 3 随机时间依赖网络中的最短路径问题 目前，静态网络中的最短路径算法已经十分完善。但是，在实践中，网络特征( 如 弧的权值、结点耗费等) 可能会时刻发生变化，要求最短路径算法必须实时地自动更新。 这类问题主要集中在交通网络的实时导航、通勤、调度和计算机互联网的数据传递路由 等方面。网络特征时刻发生变化的网络为动态网络( d y n a m i cn e t w o r k s ) ，这种随时间变 化而变化的特性称之为时间依赖性( t i m e d e p e n d e n t ) 。在动态网络中，弧的权值、结点耗 费等均为时间t 的函数，既可以是离散函数2 1 ，也可以是连续函数【6 - 8 , 3 3 - 3 6 1 。在假设网 络中的每条弧具有先进先出( f i r s t i n f i r s t - o u t ) 特性的前提下，任何静态的l s 和l c 算法 均可以扩展为时间依赖的最短路径算法i l l 。 在现实交通网络中，由于交通拥挤程度随着时间的变化而变化，因此，每条弧上的 实际旅行时问都是随时间变化而变化的量，并且带有不确定性。这种不确定性是由司机 和车辆特性的变化以及其他不可预测事件( 如恶劣天气或塞车等) 的可能发生所导致的。 现在，概念上已经接受，实验上已经证明了交通网络中的随机性和时间依赖性【3 8 j 。这种 网络特征( 如弧的权值、结点耗费等) 既具有随机性又具有时间依赖性的网络称之为随机 时间依赖( s t o c h a s t i ca n dt i m e d e p e n d e n t ) 网络，简记为s t d 网络。现实交通网络是典型 s t d 网络，其中每条弧的实际旅行时间都是具有时间依赖概率分布的随机变量p 。 在通信系统、智能交通系统、紧急服务运输系统等数据网络中，也同样存在随机性 和时问依赖性。在数据网络中，一条消息被分解成许多个数据包，每个数据包都被有序 地发送到目的地以便传输该消息。在传输过程中，每个数据包都将被多个路由器( 被设 计用来为数据包提供合适传输路径) 处理。由于这些路由器在体系结构上或其他方面可 能有所不问，因而可能具有不同的处理速度。在拥挤的数据网络中，传输一条信息到目 的地所花费的时间主要依赖于数据包被这些路由器处理的时问。数据包在每个路由器上 的等待时间不仅依赖于这个路由器的处理速度，而且还依赖于该路由器的服务要求( 如 路山器上的队列l 丈度等) 。和现实交通网络斗月似，数据网络中的服务要求电随着时叫的 变化而变化，并带有不确定性。所以，数据瑚络也是典型的s t d 网络j 。 可以将s t d 网络理解为“二二维约束”的网络，一维约束是概率，另一维约束是时间。 从时间方面划分，又分为离散时间的s t d 网络( 如图1 4 ) 和连续时间的s t d 网络( 如图 1 5 ) 。如果单从概率维来考虑，忽略时间因素，那么s t d 网络就会退化为静态网络。 比如，无论什么时候，你从家里出发到单位上班，如果天气好的话，路上可能花2 0 分 钟；否则，可能花3 0 分钟。就是说，路上花的时间只受随机因素的影响而不受时间因 素的干扰。然而，实际情况往往并非如此，即使在天气好的情况下，上班所花费的时间 也不会恒为2 0 分钟。这是因为，如果你从家出发的很早，恰逢交通空闲期，则很可能 只花1 0 分钟就可以到达单位；但如果你出发的很晚，正赶上交通拥挤期，即交通高峰 期，那么你可能要花上3 0 分钟的时间也到不了单位。所以，在研究现实交通网络以及 类似网络( 如数据网络) 时，必须考虑二维约束才更具有实际意义。特别是，近年来计算 机网络与通信、智能交通系统的蓬勃发展使得随机、时变最短路径问题进一步复杂化和 多样化。因此，s t d 网络中的最短路径问题的研究就显得非常重要。 图1 4 离散时间的s t d 网络 f i g 1 4s t dn e t w o r kw i t hd i s c r e t et i m e 图1 5 连续时间的s t d 网络 f i g 1 5s t dn e t w o r kw i t hc o n t i n u o u st i m e 然而，s t d 网络中的最短路径问题的算法又主要分为以下几类：一、期望最短路径 算法，寻找网络中任意节点间的最短期望路径；二、最小可能时间路径算法，计算网络 中任意节点间的可能的最小期望时间路径；三、自适应期望最短路径算法，它实际上是 一种策略算法，出发者可以根据到达的具体时刻选择不同的最短路径；四、k 期望最短 路径算法，主要是针对先进先出网络计算最短到第k 短的期望路径。 f 1 ) 期望最短路径算法 期望最短路径算法按适用范围可以分为两大类，先进先出s t d 网络中的期望最短 路径算法和非先进先出s t d 网络中的最短路径算法。 张勇：随机时问依赖网络中的白适应kj 毋望最短路径 对于先进先出网络，h a l l 4 0 1 提出了一个结合分枝限界( b r m a c h a n d b o u n d ) 和k 最短 路径技术的算法，来确定单源点和单目的地间的预先( ap r i o r i ) 期望最短路径( 有时也称 为最小期望时间路径) 。该算法需要计算每条路径的期望时间和最小的可能时问，却没 给出计算这些值的具体步骤。该算法需要计算每条路径的最小的可能时间，但不能保证 在所有路径的期望值被估算完之前结束。并且该算法没有考虑期望最短路径具有个或 多个环的可能性，因此，它仅仅能被应用到非循环网络或具有先进先出特性的循环网络 中1 0 1 。m p w e l l m a n t 6 】利用随机优势的概念在一定程度上缩小了问题的求解空间，给出 了一个算法；但是，文献 6 采用的概率分布函数服从指数分布的假设存在着局限性。 目前研究不同类型概率分布也是在这方面有待研究的问题【3 9 】。 相对于先进先出网络，非先进先出网络中算法就比较复杂。比较有代表性的算法是 m i l l e r h o o k sa n dm a h m a s s a l f i i o l 提出的最短期望时间路径算法，该算法是一个特殊的标 号修正( 1 a b e l c o r r e c t i n g b a s e d ) 算法，它计算出每个节点在任意出发时刻到达目的节点的 最短期望时间路径。他们将弧的旅行时间表示成离散的随机变量，并且不允许个体在中 间结点处等待。 期望最短路径算法的提出从一定程度上解决了随机时间依赖网络中的最短路径问 题，能够为智能交通系统和通信网络提供较好的解决方案。 ( 2 ) 最小可能时间路径算法 m i l l e r h o o k sa n dm a h m a s s a n i 9 1 提出了随机时间依赖网络中的最小可能时间路径算 法，算法是基于标号修正算法的，计算出每个节点到目的节点的最小可能时间路径，整 个网络处在一个离散的时间集合，算法结束可计算出每个出发时刻的最小可能时间和相 关的实现概率。 但由于没有考虑到所有的相关风险，因此，这样的路径可能不是最好的。并且，无 论是可能旅行时间最小的路径还是最长的路径，它们的发生概率都非常小，从概率统计 的角度上讲，这些都是小概率事件，而小概率事件实际上是很难发生的，所以，它们根 本就不能代表通常情况，实际应用价值值得探讨。 ( 3 ) 自适应期望最短路径算法 h a l l 4 0 1 还提出了一个动态规划算法，来确定能为路线决策( e r l r o u t ed e c i s i o n s ) 的最优 策略以反应已经历弧的旅行时间h a l l 认为这样的时间自适应( t i m e a d a p t i v e ) 路线选择 能找到比预先最优化( ap r i o r io p t i m i z a t i o n ) 具有较低期望旅行时间的路径这其实和追索 问题是一样的，一旦实现了一个或多个随机变量的值，就可以获取追索策略( 见 4 1 ) 对 于最优性的一个相似观点，p s a r a f t i sa n dt s i t s i k l i s l 4 2 1 考虑最优策略，来确定非循环动态随 机网络中单源点和单目的地间的最小期望耗费路径从每个结点衍生出的当前弧( 即正 6 在其上旅行的弧) 的耗费是那个结点状态的函数，只有到达浚结点时才能知道其具体状 态，其他网络结点的状态是随机变化的但非时间依赖的 m i l l e r h o o k s “3 提出了一种随机时间依赖网络中的白适应期望最短路径算法，其实 这个算法早在她最短期望时间路径算法的文章中【1 。】作为期望最短路径算法的下界而提 出。算法是一个特殊的标号修正算法，在每个节点的每一个可能出发时刻保留一个最短 路径，通过从目的节点向始节点的搜索，中间节点出不允许等待，逐步迭代，最终找到 每个节点到目的节点的自适应期望最短路径。 当然还有考虑允许中问节点出等待的自适应期望最短路径算法，y a n gb a i y u 4 3 1 提 出了这样的一种算法，考虑网络中各节点的等待是一种随机性的情况( 只知道概率值) 。 f 4 1k 期望最短路径算法 有些时候，在许多实际应用领域，如用户在使用咨询系统或决策支持系统时，除了 希望得到最优决策参考外，还希望得到次优、再次优决策参考m 。反映在最短路径问题 上就是说，不仅要寻找从单源点到单目的地的最短路径，而且还要确定第二短路 径，一直到第丘短路径。譬如【3 3 , 3 4 1 ，在通信网络和交通网络的路径选择中， 某条链路拥塞或崩溃，就需要寻求其它的次最短路径；当计算模型中的输入数据是 近似值时，计算出的结果可能不是最优的；当引入其它限制条件时，计算出的最短 路径可能是不可行或不可接受的方案，因此可行或可接受的方案要从世最短路径集合中 选取。在高级旅行信息系统 “j 中，对于旅行者的多种类型的需求，比如，除了要求路径 期望耗费最少以外，可能还要求行走时间小于某个常数，或者要求换车次数不大于某个 值。在这种情况下，简单地求出期望耗费第一短的路径不定就能满足用户的需求。 g a n gl i u 等【1 6 1 给出了一个寻找服从多重约束的k 最短路径的算法。d e n g f e n gc h a i 等【舭】研究了前n 条最短路径问题的算法及应用。但是，文献 1 6 ，4 4 中所涉及的网络都 只是静态网络，而实际上很多网络的网络特征( 如弧的权值、结点耗费等) 都是动态变化 的。 文献 7 将随机优势作为有效的判别标准，给出了用于求解s t d 网络中单源点和单 目的地间的k 期望最短路径问题的kp f s d 算法，并对其进行了并行化【3 3 】。g u o z h e nt a n 和x i a n g f ux i a 研又从可靠性理论的角度求解了s t d 网络中单源点到单目的点的期望时 间最短路径问题【4 。成功地解决了先进先出s t d 网络中的k 期望最短路径问题。 对于非先进先出s t d 网络中的k 期望最短路径问题目前未查到有相关文献。 1 2 本文的主要工作 本文的研究工作得到了国家自然科学基金资助项目( 6 0 3 7 3 0 9 4 ) ，国家“9 7 3 ”计划 重点基础研究发展基金资助项目( 2 0 0 2 c b 3 1 2 0 0 3 ) 的资助。 张勇：随机时问依赖网络中的白适应k 期望最短路径 对于自适应路径问题和k 期望最短路径问题都有相关的大量的研究，但是尚没有人 对两者的结合进行研究。本文正是在这两个问题的基础上提出了自适应k 期望最短路径 问题。 本文要解决的主要问题是，s t d 网络中，对于每个结点在任意时刻出发到达目的地 结点的自适应k 期望最短路径问题，在中间结点处不允许等待，弧的旅行时间是相互独 立的而且其概率分布函数是已知的。 具体说来，本文的主要工作可以概括为以下几点： ( 1 ) 建立s t d 网络模型，通过实例阐述了自适应路径问题并将它应用到求解k 期 望最短路径算法中，推导出适用于先进先出s t d 网络和非先进先出s t d 网络的路径优 化条件。接着，给出了求解第二期望最短路径到第k 期望摄短路径的方法。 ( 2 ) 将自适应性应用到实际算法中，设计并实现了求s t d 网络中多源点到单目的 地结点问的自适应k 期望最短路径的ak e s p 算法。接着，从理论上论证了算法的正 确性并总结了算法的性质。 ( 3 ) 首先分析了ak e s p 算法的迭代过程，证明了ak e s p 算法不是枚举算法。 然后利用周期和k 期望最短路径树从理论上对ak e s p 算法的复杂性进行了分析和论 证，主要是对其时间复杂度进行了分析和论证。 ( 4 ) 设计试验，利用不同规模的s t d 网络对算法进行测试，并且利用k 的取值不 同和时刻数的不同对其性能进行了分析和比较；测试实例表明，ak e s p 算法能正确地 求解出s t d 网络中地k 期望最短路径。 ( 5 ) 最后，总体评价本文计算方法的优缺点，对进一步的工作进行了展望。 1 3 本文的组织结构 本文余下部分组织如下： 第二章介绍传统的网络模型和k 最短路径问题，并对传统k 最短路径算法包括标 号修正算法和标号设置算法进行了深入的分析。 第三章首先给出了s t d 网络模型，然后通过一个实例简单地介绍了自适应路径问 题；并且推导出s t d 网络中的路径优化条件。接着，给出了求解第二期望最短路径到 第k 期望最短路径的理论基础和求解方法。 第四章将自适应性应用到k 期望最短路径算法中，设计实现了用于求解自适应k 期望最短路径问题的ak e s p 算法，并从理论上论证了算法的正确性。 第五章从理论上分析了ak e s p 算法的迭代过程，并且详细地对ak e s p 算法的 时间复杂度进行了分析和论证。 第六章试验测试。酋先陶建s i d 网络，然后通过利用不同规模的s t d 网络对算法 进行测试，并目利用k 的取值不同和时刻数的不同对其性能进行了分析和比较；最后通 过实例验i i e ta k e s p 算法。 第七章总结全文并展望今后的研究工作。 张勇：随机时间依赖网络中的白适应k 期望最短路径 2 传统网络模型与k 最短路径问题 2 1 传统网络模型定义 用( n ，a ) 表示一个给定的网络。这里n = v ，v 。) 或者n = l ，”) 是一个含有n 个元素的有限集，称做节点集。a = a ，n 。) 是含有m 个元素的有限集，称做边集。 网络图中的每条弧a k 都是一个节点对( i ，j ) ，如果这些节点对是无序的，则称( n ，a ) 是 无向网络。否则称( n ，a ) 是有向网络。在下面的表示中，不失一般性，除非明确指出， 否则所说的( n ，a ) 都是指有向网络。 s 和t 表示，a ) 中给定的两个节点。在( n ，a ) 中从s 到t 的一条路径是节点和边 的交替序列，其格式是： s = v ；，以：，v ；，口口：+ v t ，其中： ( 1 ) 对任意的k = l ，2 ，r 一1 都有a ：a ；对任意的k 1 ，r 都有v ：n 。 ( 2 ) 对任意的k 【1 ，r 一1 】，都有a ：= ( v ：，v ：+ 。) 。 令c ( 吼) = 勺表示边a k 的权值( 实数) ，c ( p ) = c f 表示网络( n ，a ) 中的一个节点对 ( j ，j ) e p 之间的路径p 的长度。用p i l 表示网络州，a ) 中从节点i 到节点j 的路径的集合。在以后的 表示中，本文假定对于任何属于n 的节点i 都有：只o 且只o 。不失一般性，本文 假定所有从s 到t 的路径都有r 3 。事实上， 节点s 和t 以及两条长度为0 的弧( s ，s ) ( t ， 假定是不失一般性的。 因为可以在给定的网络中添加两个不同的 t ) ，显然b ，和己是一种双射关系，所以上述 无环路径：如果从s 到t 的路径上没有重复节点，那么该路径称为无环路径。 环：是从一个节点到其自身的路径，并且路径上除了起始节点与终止节点相同之外 不再有其他的重复节点。 负环：如果一个环的权值小于0 ，即c f t h e nb e g i n - 一e l e n l e n t dh - 1 ( j ) f w h i c h m = m b it h _ 1 “) i f ( 霄+ 。廿 ，得到节点i 。若已经计算出了i 的所有k 最短路， 则将7 ( k ) 与k 条路径当中的最大的标号比较，若丌( 1 ( ) 小，则修正最大的标号为石( k ) 。 人、童二一# r 火学硕l 学位论文 若没有计算出j 的所有k 最短路，则对j 进行扩展，新得到的 ! r 爬节点加入到x 中。x = 中时，算法结束。 基于b e l l m a n 的k 最短路径算法描述如图2 3 所示。 a l g o r | t h m3 一g e n e r a l i z a t i o no ft h eb o a l m a n - f o r d - m o o r ef o r mw i t hs i n g l el a b e l s x 3 0 t t n f i e j ， s e q u e n c eo fn o d e eo f n t h ee n l a r g e ds e td o d n u m b e ro f p a t h at h a tw e r ed e 蛔i n e dh o mft oi ， n u m b 口o f e l e m e n t so f $ ， u 咄- 0 ha l l i e l m l h ( 8 f m ) 一苗h - i ( b ) - 一 e f 呐_ ；h 。一0 盖- 一扛f m w h i l e x 士0 d o b e g i n 蠹+ 一f i r s td 日脚n t d x 工一z 一 1 ) f h h ( t 1 f o re a c hn i c ( i ，j ) d o b e g i i f ( h n = k ) t h e nb e g i 丑 一e l e m e n t0 fh - i ( j ) f hw h i c h 耽= m 强 b it _ 1 ( j ) ) f f ( f + q 毗) t h e nb e g m i f x t h e n xb x 一牡 n 。n + q ；b i x - x t 2 z a n d i s t h e l a s td 衄t0 f z e n d i e 丑d e l s eb e g i n - ( e o u n t ( k ) ， g i ，n 一e l m + 1 z d m n + o 玎；f i h - u n 如+ 一c o u n f l + 1 ( e j 呻一土h - 1 0 ) - 一h - 1 ( j ) u e j m ) x 一x 1 , 2 e t m t de l mi st h el 瞳e l e m e n to f z e n d e n d e n d f j n dt h eks h o r t e s tp 醯h 日 图2 3 基于b e l l m a n 的k 最短路径算法 f i g 2 3g e n e r a l i z a t i o no f t h eb e l l m a n - f o r d - m o o r ef o r mw i t hs i n g l el a b e l s 2 ，2 3k 最短路径标号设置算法 算法的思想和d i j k s t r a 的思想很类似：初始时h ( 1 ) = s ，石( 1 ) = o ，扩展结点l 被放入x 集合。算法执行时，每次将所有新加入h 的结点所对应的扩展结点放入x 集合，然后从 1 5 张勇：随机时间依赖网络中的自适应k _ l 望最短路径 x 集合中搜索一个7 c 值最小的扩展结点k ，将k 从x 中删除掉，如果k 所对应的结点i 已经计算出了所有的k 最短路，此次操作结束，重复下一轮循环；否则若i 正在计算第 t 条k 最短路( 1 t s k ) ，则将i 的所有后继结点加入h 数组，将这些后继结点相应的路径 值加入7 1 数组，并且当i = k 时将结点u 设为已标记结点。重复下一轮循环；直到目的点 t 计算出了所有的k 最短路，或者x _ o 时，算法结束。 k 最短路径标号设置算法描述如图2 4 所示。 a l g o r i t h m4 一g e 舒且l i 卫且t i o o fd i j k s t r a sa l g o r i t h m , w i t hs i n g l el a b e l s # x s u b s e to f t h ee n h x g e ds e tdn o d e 日 c o r n e l n u l n b e ro f p a t h st h a t r ed e t e r m i n e df r o mst oi 口 m n t w n b e fo f e l e m m t ao f + t m n 卜0 ，f o ra l l f p f ，n 一l 万m ) 一qh - a ( 5 ) 一 e f m ) ；丌。h 一0 p x j r - 一- e 。t ” v t r h i l e ( c d 疵t k a n d x o ) d o b e g i n t he l e m e n to f xs u c ht h a ti 蔓k ，f a ra n y x z - 一x 一忙) i + 一耐 u n 一c o u n t i + 1 i f ( i = f ) t h e nb e g i n d 扣一d “bf r c u 1t o