（计算机应用技术专业论文）随机时间依赖网络中的路径规划算法.pdf

摘要 在交通网络和数据网络中，网络特征( 如弧的权值、结点耗费等) 既具有随机性又 具有时间依赖性，这样的网络称之为随机时间依赖网络，简记为s t d 网络。在实践中， s t d 网络模型比传统网络模型具有更广泛的应用。由于随机性和时间依赖性引入到网络 模型中，使得最短路径问题变得复杂化和多样化，传统的最短路径算法已不再适应这样 复杂的网络环境，这就迫使我们寻求新的解决方法。 本文求解的问题是，s t d 网络中，在任意时刻从单源点出发到达单目的地的路径预 先规划( 口p r i o r i ) 问题。该问题包含两个子问题，一个是期望最短路径问题，另一个是 k 期望最短路径问题。 本文将可靠性理论应用于s t d 网络中单源点和单目的地间的路径预先规划问题的 求解中，建立了s t d 网络的可靠性理论模型，并推导出该模型的一些重要特性，同时 将s t d 网络中的路径预先规划问题转化为系统可靠性问题。基于可靠性理论，本文推 导出新的优势判别法，使得传统判别法中的参数由二维降到一维，减少了路径间不可比 较的可能性，既节省了大量存储空间又加快了搜索速度。接着，设计并实现了求解期望 最短路径问题的r e l s p 算法和求解k 期望最短路径问题的kr e l s p 算法，并从理论 上分别证明了它们的正确性。然后，设计试验分别对r e l s p 算法和kr e l s p 算法的性 能进行测试和比较，试验结果表明，它们在解决大规模s t d 网络中的路径预先规划问 题上非常有效。最后，本文还推导出用于计算某条路径期望旅行时间的正向和逆向递归 公式，为今后设计求解s t d 网络中期望最短路径问题的正向和逆向递归算法作了前期 准备工作。 关键词：随机时间依赖网络；可靠性理论；预先规划；路径规划算法 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 k ( i e s t dn e t w o r k ) i san e t w o r kw h e r ea r c t r a v e lt i m e sa r er a n d o mv a r i a b l e s 、析t ht i m e d e p e n d e n tp r o b a b i l i t yd i s 仃i b u t i o n s s t o c h a s t i c a n dt 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 mc 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 n s y s t e m s f a s te x p a n s i o n o 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 d e v e nm o r ec h a l l e n g i n g s ot h es t u d yo fs h o r t e s tp a t hp r o b l e mi ns t dn e t w o r k si so ft i m e l y i m p o r t a n c e a p r i o r ip r o b l e mo fp a t h - p l a n n i n gf r o mas i n g l eo r i g i nt oas i n g l ed e s t i n a t i o nf o re a c h d e p a r t u r et i m ei ns t dn e t w o r k si st a k e ni n t oc o n s i d e r a t i o ni nt h i st h e s i s ，i n c l u d i n gt w o s u b p r o b l e m s ：e x p e c t e ds h o r t e s tp a t hp r o b l e ma n dke x p e c t e ds h o r t e s tp a t h sp r o b l e m t h er e l i a b i l i t yt h e o r yi sa p p l i e df o rt h es o l u t i o no fp a t h p l a n n i n gp r o b l e mi ns t d n e t w o r k s t h er e l i a b i l i t yt h e o r ym o d e lo fs t dn e t w o r k si sb u i l ta n ds o m ei m p o r t a n tp r o p e r t i e s o ft h a ta r ec o n c l u d e d a tt h es a m et i m e ap r i o r ip r o b l e mo fp a t h - p l a n n i n gi ns t dn e t w o r k si s t r a n s f o r m e di n t ot h ep r o b l e mo fs y s t e mr e l i a b i l i t y f i r s t ，an e wd o m i n a n c ed i s c r i m i n a n c ei s p r o p o s e di nt h i st h e s i s w h i c hm a k e st h ep a r a m e t e rs p a c ei nt r a d i t i o n a ld i s c r i m i n a n c ed r o p f r o mt w od i m e n s i o n st oo n ed i m e n s i o na n dr e d u c e st h ei n c o m p a r a b i l i t ya m o n gp a t h s 。s e c o n d ， r e l s pa l g o r i t h m st os o l v eap r i o r ip r o b l e mo fe x p e c t e ds h o r t e s tp a t ha n dkr e l s p a l g o r i t h mt os o l v eap r 幻r ip r o b l e mo fke x p e c t e ds h o r t e s tp a t h sa r ep r o p o s e da n d i m p l e m e n t e di nt h i st h e s i s ，a n dt h e na ne x p e r i m e n ti sd e s i g n e dt ot e s tt h e s ea l g o r i t h m sa n d c o m p a r et h e i rp e r f o r m a n c e f i n a l l y ，t w or e c u r s i o n sf o rc a l c u l a t i n gt h ee x p e c t e dt r a v e lt i m eo f c e r t a i np a t hi ns t dn e t w o r k si si n f e r r e da n dd e d u c e d ，w h i c hd o e ss o m ep r e l i m i n a r yw o r k s f o rd e s i g n i n gt h er e c u r s i v ea l g o r i t h m si ns t dn e w o r k si nt h ef u t u r e k e yw ords ：s t dn e t w o r k s ；r e l i a b i l i t yt h e o r ym o d e l ；ap r i o r i ；p a t h - p l a n n i n ga l g o r i t h m 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版 权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等 复制手段保存和汇编学位论文。 保密叫在年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“ ) 作者签名：复盏宝 指导导师签名遽【挺 随机时间依赖网络中的路径规划算法 o 前言 o 1 最短路径问题的研究背景及意义 o 1 1最短路径问题的提出 最短路径问题是现实生活中很常见的一个问题。例如，如果司机用汽车运输货物从 彳地到b 地，他就会考虑走路程最短或时间最省的那条路径，这是考虑路程或时间的最 短路径问题。又如，要在4 地到丑地之间铺设煤气管道，首先，将彳，b 两地间的长方 形区域划分格子点。然后，根据地形、土壤、是否经过江河、泥塘、农田、村庄、郊区、 城镇、公路、铁路等各种情况，将从一格子点到另一格子点的铺设费用估计出来，最后， 求出由彳地到曰地铺设煤气管道经过哪些格子点才能使总的造价最小，这是考虑费用 的最短路径问题。另外，在线路安排、设备更新、厂区布局、城市规划、电子导航、交 通转车等方面均需要考虑到最短路径问题。 从上述可知，“最短”一词在不同情况下有不同的含义，或者是距离最短，或者是 时间最省，或者是费用或代价最少，等等。 o 1 2最短路径算法的分类体系 最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。 国内外大量专家学者对此问题进行了深入的研究。经典的图论与不断发展完善的计算机 数据结构及算法的有效结合使得新的最短路径算法不断涌现。它们在空间复杂度、时间 复杂度、易实现性及应用范围等方面各具特色【l 引。 针对串行计算机的最短路径算法，已经几乎达到理论上的时间复杂度极刚。现在 的研究热点，一是针对实际网络特征优化运行结构【3 锄j ，在同一时间复杂度的基础上尽 可能地提高算法的运行效率；二是对网络特征进行限制，如要求网络中每条弧具有先进 先出的特性【5 8 】以便于降低问题的求解难度；三是采用有损算法，如限制范围搜索【2 6 1 、 限定方向搜索【2 7 】以及限制几何层次递归搜索【2 8 】；四是采用拓扑排序算法【2 9 1 ，或者采用 拓扑层次编码路径视图1 3 0 ，对最短路径进行部分实例化编码存储；五是采用并行算法， 为并行计算服务【3 1 删。 由于问题类型、网络特征及实现技术的纷繁复杂，最短路径算法表现出多样性。总 的来说，我们可以分别按照问题类型、网络特征及实现技术对最短路径算法进行系统的 分类【l j 。 随机时间依赖网络中的路径规划算法 0 1 2 1 问题类型 按照起终结点及路径的数目和特征，最短路径问题可分为如下5 种类型：单对结点 间的最短路径问题、所有结点间的最短路径问题、k 最短路径问题、实时最短路径问题 和指定必经结点的最短路径问题。其中又可衍生出其他一些特殊的最短路径问题，如限 制弧段数目的最短路径、含环路径等。基于问题类型，最短路径算法的完整分类体系如 图1 所示。 图1 基于问题类型的最短路径算法分类体系 f i g 1 c 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 yp r o b l e mt y p e 在这里面，本文主要关注单对结点间的最短路径问题和k 最短路径问题。 0 1 - 2 2网络特征 按照网络特征及表示方法的差异，最短路径算法可按图2 所示体系进行分类。 图2 基于网络特征的最短路径算法分类体系 f i g 2 c 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 k c h a r a c t e r i s t i c s 随机时间依赖网络中的路径规划算法 在这里面，本文主要关注网络中每条弧的权重服从概率分布。当然，这里所说的概 率分布既可以是连续的也可以是离散的。在网络工程中，权可以表示时间、费用、里程 或者代价等等。 0 1 2 3 实现技术 另一种最短路径算法分类方法是按照实现技术进行分类。完整的分类体系如图3 所示。其中路径搜索技术中的通用技术是最短路径算法研究的重点所在，也是本文所要 关注的。 图3 基于实现方法的最短路径的最短路径算法分类体系 f i g 3 c 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 如图3 所示，路径搜索通用技术进一步又可分为代数技术和组合技术两种。代数技 术通过运筹学中的线性规划形式化、所定义代数系统中的联立线性方程组形式化和矩阵 乘法等方法来解决最短路径问题。组合技术主要是指标号算法( l a b e l i n g a l g o r i t h m s ) 。 标号算法也是绝大多数最短路径算法的核心部分p 。按照不同的标识结点处理策略，标 号算法又可分为标号设定( l a b e ls e t t i n g ，简记为l s ) 算法和标号修正( l a b e lc o r r e c t i n g ， 简记为l c ) 算法两大体系。实际上，所有的l s 或l c 算法都可总结为一种更为一般性 的算法的特例。不同之处在于它们处理图中所标识结点时采用的优先级队列系统各不相 同。另外，朋算法不能处理含负边权的网络，而三c 算法则可以处理含负边权的网络【i 】。 0 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 的函数，既可以是离散函数 9 - 1 2 j ，也可以是连续函数【6 - 8 , 3 3 - 3 6 】。在假设 随机时间依赖网络中的路径规划算法 机优势判别法含有两个参数，路径间不可比较的可能性很大。j b o y a 等4 3 1 基于可靠性理 论研究了随机网络中的调度策略问题，他们考虑乘客在车站等待公交车的等待时间，并 且当等待时间是具有递增失效率的相互独立的随机变量时，给出了一个最优调度算法， 但是他们没能实现该算法，并且，所涉及的网络也只是静态网络。 0 2 本文的主要工作 本文的研究工作得到了国家自然科学基金项目( 6 0 3 7 3 0 9 4 ) 的资助。 本文要解决的主要问题是，s t d 网络中，在任意时刻从单源点出发，到达单目的地 的路径预先规划问题( a p r o r i p r o b l e m ) 。将可靠性理论巧妙地应用于该问题的求解中， 并将该问题转化为系统寿命问题。实际上，该问题包括两个子问题：一个是s t d 网络 中单源点和单目的地间的期望最短路径问题，另一个是s t d 网络中单源点和单目的地 间的k 期望最短路径问题。 假定s t d 网络中每条弧上的旅行时间都是相互独立的( 无论是在时间上还是在空 间上) 随机变量，并且允许个体在某中间节点处等待。我们考虑从单源点到单目的地间 的整条路径的旅行时间，目的是找出统计意义上的最优结果。该问题违反了标准动态规 划原理，使得问题求解变的非常困难。 具体说来，本文的主要工作可以概括为以下几点： i 将可靠性理论应用于s t d 网络中单源点和单目的地间的路径预先规划问题的求 解中，将该问题转化为系统寿命问题，建立了舳d 网络的可靠性理论模型，并 推导出该模型的一些重要特性。然后，基于可靠性理论推导出新的优势判别法， 使得传统判别法【6 7 翔l 中的参数由二维降到一维，减小了路径间不可比较的可能 性，进一步缩小了问题的求解空间，这样，既节省了大量存储空间又加快了搜 索速度。接着，推导出计算某条路径期望失效时刻和期望寿命的公式。 i i 设计并实现了求解s t d 网络中单源点和单目的地间的路径预先规划问题的算 法。该算法包括两个子算法：一个是求解s t d 网络中期望最短路径问题的r e l s p 算法，另一个是求解s t d 网络中k 期望最短路径问题的kr e l s p 算法。然后， 分别从理论上证明了这两个算法的正确性。实际上，人们早已意识到s t d 网络 中的最短路径问题是尸完全问题脚j ，现在绝大部分工作都是针对实际网络特 征优化运行结构，在同一时间复杂度的基础上尽可能地提高算法的运行效率【1 1 ， 本文也正是这样做的。 i i i 设计试验，利用不同规模的s t d 网络分别对r e l s p 算法和kr e l s p 算法进行 测试，并对它们的性能进行比较分析。试验结果表明，r e l s p 算法和kr e l s p 算法的平均性能比传统算法【6 ，7 】要好，尤其在大规模的s t d 网络中性能表现特别 优越。 i v 推导出用于计算s t d 网络中某条路径期望旅行时间的正向和逆向递归公式，为 下一步设计求解s t d 网络中单源点和单目的地间的期望最短路径问题的正向和 逆向递归算法做了前期准备工作。 随机时间依赖网络中的路径规划算法 o 3 研究环境 本文的研究环境是w i n d o w s 2 0 0 0 操作系统，p c 机的硬件配置如下： 硬盘：4 0 g 内存：2 5 6 m c p u ：p i i l l 0 g 网卡：3 c o mf a s te t h e r l i n kx l1 0 1 0 0 m bt xe t h e m e tn i c o ，4 本文的组织结构 本文余下部分组织如下： 第一章先简要介绍可靠性理论的基础知识以方便后面内容的理解：然后，将可靠 性理论应用于s t d 网络中单源点和单目的地间的路径预先规划问题( 该问 题包含两个子问题：一个是期望最短路径问题，另一个是k 期望最短路径 问题) 的求解中，将该问题转化为系统寿命问题，建立了s t d 网络的可靠 性理论模型，并推导出该模型的一些重要特性。 第二章分别设计并实现了用于求解期望最短路径问题的r e l s p 算法和用于求解 k 期望最短路径问题的kr e l s p 算法，并从理论上证明了它们的正确性。 实际上，人们早已意识到s t d 网络中的最短路径问题是p 完全问题j ， 现在的绝大部分工作都是针对实际网络特征优化运行结构，在同一时间复 杂度的基础上尽可能地提高算法的运行效率【l 】。本文也正是这样做的。 第三章基于可靠性理论推导出新的优势判别法，使得传统判别法【6 。7 3 3 】中的参数由 二维降到一维，减少了路径间不可比较的可能性，既节省了大量存储空问 又加快了算法的收敛速度；接着，设计试验，利用不同规模的s t d 网络分 别对r e l s p 算法和kr e l s p 算法进行测试，并对它们的性能进行比较分 析。结果表明，r e l s p 算法和kr e l s p 算法的平均性能比传统算法1 6 , 7 要 好，尤其在大规模的s t d 网络中性能表现特别优越。 第四章推导出用于计算s t d 网络中某条路径期望旅行时间的正向和逆向递归公 式，为下一步设计求解s t d 网络中单源点和单目的地间的期望最短路径问 题的正向和逆向递归算法做了前期准备工作。 第五章总结全文并展望今后的研究工作。 随机时间依赖网络中的路径规划算法 1s t d 网络的可靠性理论模型 1 1 预备知识 为方便对后面内容的理解，我们先对可靠性理论的基础知识作一简要的介绍，进一 步的详细内容可在教科书 4 5 】中查找到。 我们用非负随机变量x 表示一个系统的寿命，其中x 具有概率分布函数f ( t ) 。该 系统的可靠度函数定义为 f 一( t ) = e ( x r ) = 1 一e ( x f ) = 1 一f ( t ) ， 即 f 一( t ) = 1 一f ( t ) 。 很显然，f ( f ) 描述了该系统在时间区间【o ，f 】内的生存能力。 该系统的平均寿命为 e x = f t d f ( t ) = f d f ( t ) j d x = f d r , f d f ( t ) = p ( t ) d t ， 即 e x = f f f ( t ) d t 而该系统在f 时刻的平均剩余寿命为 我们记 瓯= e 防一tlx f 】。 d = s u r t if o ，声 o ，d ：【o ，d ) 。 其实，d 就是系统寿命的上确界，j d 就是该系统寿命的分布区间。 假设f ( t ) = f ( f ) ，即厂( ，) 为随机变量z 的概率密度函数，则该系统的失效率定义 为 啪= 器舢 由( 2 ) 式，我们可以得到 ( 2 ) 随机时间依赖网络中的路径规划算法 m ，：器：可d f ( t ) ：一掣d：一桨 d t 郧。， f ( f )f o )f o )f o ) 即 ，( f ) 一讲a - - l n f ( f ) ( 3 ) 进而可以得到 j ( f ) ：p 一如冲 ( 4 ) 有了对可靠性理论的初步理解，接下来，我们就将可靠性理论巧妙地应用到s t d 网络中的路径规划中来。这里的路径规划包含两个方面：一是对期望最短路径问题的求 解：二是对k 期望最短路径问题的求解。首先，我们建立s t d 网络的可靠性理论模型， 并推导出该模型具有的一些基本性质。 1 2 可靠性理论模型 由于可靠性理论是研究系统随机寿命的理论，因此，我们首先将s t d 网络描述成 一个系统，称之为s t d n - r 网络系统。然后将s t d 网络的期望最短路径问题转化为系 统的期望最短寿命问题。我们把整个s t d 网络以及个体从源点到目的地的旅行时间r 构造成一个系统，并将丁作为该系统的寿命。为了更容易地表达系统寿命的动态过程， 我们引入路径寿命的概念。一条从源点s 到结点的路径的寿命是指，个体从源点j 出 发，沿该路径运行，到达结点时所花费的时间。 在s t d n - r 网络系统中，由于弧的寿命( 即旅行时间) 是随机的和时变的，所以该 系统的寿命也是随机的和时变的。我们用非负随机变量x 表示该系统的寿命。我们优化 的目标是设法使系统期望寿命最短，即寻找期望寿命最短的那条路径作为最优路径。也 就是说，我们希望找到一个尽可能小的r ，使该系统在时间区间【o ，f 内的生存能力最低， 即失效率最大。 在系统中，“失效这一事件是由个体到达当前路径的最后结点所导致的。本文， 我们引入系统初始时刻、系统失效时刻、系统期望失效时刻、弧勺o v 户的初始时刻、弧 的失效时刻是指个体在尾结点，出发，沿该弧运行，到达头结点的时刻：弧 的期望失效时刻是个体在尾结点出发，沿该弧运行，到达头结点的期望时刻。 下面，我们给出s t d 网络的可靠性理论模型s t d n - r 网络系统的形式化描述。 随机时间依赖网络中的路径规划算法 1 2 1s t d n - r 网络系统 1 2 1 1 模型 我们将s t d 网络的可靠性理论模型称之为s t d n - r 网络系统，其形式化表示为 s t d n r = ( 矿，a ，l ，) 。其中v 是非空结点集；a v x v 是弧集；l 是每条弧的可能 最小寿命的集合；= 切了( ，) l a ，m 1 ，2 ，n 是所有概率分布的密度函数 集。弧 a 的失效时刻是一个随机变量，按照其前驱弧 a 的失效时刻 所在的时间区间( f 了，f i ：l 】的不同，可能服从个不同的概率分布( 可以是任意类型分 布) ，硝( ，) 是第脚个概率分布的密度函数。如果弧瓴矿的前驱弧 1 ) 条同方向的弧，则将结点，扩展成 d e g + ( 1 ，) ( 即的出度) 个结点，并作为相应弧的尾结点。如果原网络中没有源点s 或 目的地d ，则在原网络中引入源点s 和目的地d 。并且，分别添加从源点s 到这些新扩 展尾结点的寿命不超过某一常数的弧，以及从其它结点到目的地d 的寿命小于某一常数 的弧。若j 和d 都是原网络中的结点，则新添加的弧的寿命均为零。 下面，我们就以一个具体的例子看看如何构造扩展网络： 随机时间依赖网络中的路径规划算法 ( a )( b ) 图7 构造扩展网络示意图 f i g 7 d e m o n s t r a t i o nf o re x p a n d i n gn e t w o r k 图7 ( 曲是一个多重图。由于爿到b 有平行的两条出弧，彳到c 有一条出弧，所以， 么的出度为3 ，即d e g + 似) = 3 。首先，我们将结点么扩展成三个结点，分别为彳l 、么2 和彳3 。并把它们分别定义为弧 a l ，胗、 a 2 ，胗和 的尾结点，曰和c 分别为这 些弧的头结点。由于原网络中没有源点j 和目的地d ，所以，我们分别将源点j 和目的 地d 添加到原网络中。接下来，我们从j 分别添加到a l 、a 2 和彳3 的寿命不大于某一常 数的弧，从c 到d 添加一条寿命小于某一常数的弧，并且，这些弧都是走行弧。这样， 我们便得到了图7 的扩展网络，如图7 ( 6 ) 所示。 没有特殊声明，后面的所有讨论均是针对扩展模型而言的。 1 2 2一致可靠性 定义1 在s t d n - r 网络系统中，用，( z ) 表示初始时刻为z 的弧钒v p 的实际寿命。 设0 j f ，对于s t d n - r 网络中的任意弧瓴矿，如果该网络满足 ， ，b + 乇0 ) j r ( t + ，“( r ) j ( 6 ) 则称该网络具有一致可靠性。 定义1 表明，失效率不会因为初始时刻晚而增大。 在公交网络中，这种一致可靠性是合理的。如果有某辆车a 在任何时刻的失效率都 大于前一辆车b 在相应时刻的失效率，显然最优决策是选择搭乘车a ，而简单地把车b 删除，使其满足( 6 ) 式的一致可靠性约束。也就是说，如果后一辆是特快车并且在运行 中将超过当前车，那么只要允许旅行者在车站等待，就可以简单地从网络中删除当前车， 来恢复该网络的一致可靠性。在大多数现实的交通网络中，对于旅行者来说，在车站等 待是非常合理的。 其实，就本质而言，一致可靠性就是利用可靠性理论来描述s t d 网络中任意弧的 先进先出特性。 1 2 3可靠性优先权 定义2 设p t ( t 。) = p = ，h ，v ：，v ，q ，q 和o 。) = = v 0 , v i ，v ：，1 ，；- 1 ，v i 是初始 1 2 随机时间依赖网络中的路径规划算法 时刻均为t o 且具有相同起点和终点的两条不同路径。( z ) 表示沿路径只( 靠) 系统在z 时 刻的失效率；吃q ) 表示沿路径最( 气) 系统在z 时刻的失效率。对于沈，如果总有 1 ( z ) 吃( z ) 成立，则称路径p l ( t 。) 相对于路径b ( 岛) 具有可靠性优先权，或称路径p l ( t 。) 优于路径e 2 ( t o ) ，记为p l ( t o ) 耐最( b ) 。 从表面上看，可靠性优先权和致可靠性的定义极为相似，但实际上二者有着本质 的区别：可靠性优先权描述的是s t d 网络中某条路径的性质；一致可靠性描述的是整 个s t d 网络中各条弧的特性。显然，前者强调的是局部性质，而后者强调的则是整体 特性。 由( 3 ) 式和( 4 ) 式可知 ( z ) 吒0 ) f i ( z ) f 2 ( z ) 。 因此，我们可以得到可靠性优先权的如下性质： 定理1 设f ( z ) 表示沿路径置( f 。) 系统在z 时刻的可靠度，户z ( z ) 表示沿路径p 2 ( t 。) 系统在z 时刻的可靠度。于是，对于v z ，户( z ) 户z ( z ) 丑( f o ) 耐- p 2 ( t 。) 。 实际上，可靠性优先权的直观意义就是说，如果路径e ) 的期望寿命不大于路径 最纯) 的期望寿命，则路径互( t o ) 优于是( ) ，即 皿亿o 。) ) e l ( e ：( t 。) ) jp l ( t 。) 耐( 岛) 。 定理2 只瓴) 耐( t o ) e l 瓴) ) 皿( 只瓴) ) 营e t 亿瓴) ) 五z 陂o 。) ) 。 证明：我们先证明鼻( 气) 耐最( f 0 ) e l 化( 气) ) e l 化( f 。) ) ， 充分性：因为置o 。) 耐最( 岛) ，由定理1 可知，对于v z ，总有户- ( z ) 户z ( z ) 成立， 再由( 1 ) 式，并结合积分具有单调性可知 皿( e l ) ) = i le ( z ) 出【e ( z ) a z = 皿( 只( 气) ) 。 必要性：显然成立。 所以，p i ( t o ) 耐最o o ) e l 织( “) ) 皿化瓴) ) 。 由( 5 ) 式可知，皿亿( t o ) ) 皿也) ) e t 亿纯) ) 占丁化纯) ) 。 综上所述，定理2 成立。证毕。 1 2 4路径单调性原理 定理3 给定s t d n - r 网络系统，设路径互瓴) = s - - - v o ，h ，v 2 ，h - l ，巧 ，对应扩展 路径鼻( 岛) = p = 1 ，。，v 。，2 ，“，v ，y j ；最( 气) = 和= v o ，：，v 0 ，1 ，“，1 ，) ，对应扩展路径 之( f 。) - s = v 。，1 ，i ，v ：，1 ，“，v ，_ ) 。如果s t d n - - r 具有一致可靠性，则 鼻( f o ) 甜最( 气) jp 。lp o ) 耐p 2 ( t o ) 。 随机时间依赖网络中的路径规划算法 图8 路径单调示例 f i g 8 d e m o n s t r a t i o nf o rt h em o n o t o n yo fp a t h s 证明：设路径最也) 的失效时刻为t l ，p 2 ( t 。) 的失效时刻为t 2 。由于b ( f 。) 甜b 瓴) ， 根据定理2 可知必有f 1 f ：。令_ ( z ) 表示沿路径墨瓴) 系统在z 时刻的失效率，吃( z ) 表 示沿路径最( ) 系统在z 时刻的失效率，l u ) 表示初始时刻为x 的弧勺a 垆的实际寿命。 因为s t d n - r 具有一致可靠性，由定义1 可知1 + 乃( ，1 ) ) r 2 ( t 2 + 乃0 2 ) ) 。由于在任意 时刻从源点出发，上述结论都成立。所以一定有p ，q o ) 甜p 2 瓴) 成立。证毕。 随机时间依赖网络中的路径规划算法 2s t d 网络中的路径规划算法 由于s t d 网络中的单源点和单目的地间的路径预先规划问题包含两个子问题：一 个是单源点和单目的地间的期望最短路径问题，另一个是单源点和单目的地间的k 期 望最短路径问题。所以，s t d 网络中的路径预先规划算法也应该包含两个方面：一个是 用来求解期望最短路径问题的r e l s p 算法，另一个是用来求解k 期望最短路径问题的 k r e l s p 算法。下面，我们就分别介绍这两个算法。 2 1 期望寿命最短路径算法一r e l s p 算法 2 1 1r e l s p 算法所要解决的问题 我们在前面已经说过，期望寿命最短路径是指，s t d 网络中源点s 和目的地d 之间 的期望寿命最短的那条路径。这正是本节的r e l s p 算法所要寻找的那条路径。具体而 言，本节求解的问题是：在s t d 网络中，对于任意给定的在源点s 的出发时刻t o ，预先 规划出从单源点j 到单目的地d 的期望寿命最短的那条路径。也就是说，根据分布于该 s t d 网络中的历史数据，在出发前就先寻找出条统计意义上的最优路径。这显然是一 个预规划问题( 口p r i o r i p r o b l e m ) 。 此外，我们假设s t d 网络中每条弧的寿命都是相互独立的随机变量，并且根据个 体到达中间结点h ( 结点，是弧钒p 的尾结点) 的时刻f l 来决定是否允许个体在该结 点处等待。如果，。r t l 1 ， ，对v v ，s e t ( v , ) 分别扩展鼻以。) 和忍缸o ) ，得到 丑。缸。) 和巧0 。) 。因为舅。) 耐最缸。) ，由定理3 可知置0 。) 耐砭缸。) 。因此，最0 。) 永远不可能成为从源点j 到达目的地d 的最优路径的子路径，于是，我们可以毫无顾忌 的把它删除。 另外，当r e l s p 算法结束时那些还未被搜索到的路径也不可能成为最优路径。这 是因为，若想搜索到这些路径，只有通过扩展o p e n 中的那些剩余元素对应的子路径才 能达到此目的。例如，如图9 所示，设路径只乳o ) = p ，唯3 ， ，坳，d 是r e l s p 算法结束时还未被搜索到的某条路径，要想搜索到只( ) ，则必须扩展o p e n 中的某个 元素n u m 对应的路径b 如。) = 扫，跏1 ，。 到结点1 ，。，继续扩展，直到扩展到目的地d 。 而n u m 在o p e n 表中排在当前已找到的到达目的地d 的路径对应元素的后面，即只( n ) 的 效用函数值不大于当前已找到的到达目的地d 的路径的效用函数值。由于曩) 是通过 扩展只。) 得到的，所以爿缸。) 的效用函数值小于只缸。) 的效用函数值。从而乓0 。) 的 效用函数值一定不大于当前已找到的到达目的地d 的路径的效用函数值，即曩( 风) 不可 能成为最优路径。又由于r e l s p 算法在迭代过程中每次都是从o p e n 中取出最优的元素， 因此，当前已找到的到达目的地d 的路径一定是最优的。证毕。 2 2k 期望寿命最短路径算法一k _ r e l s p 算法 2 2 一 k r e l s p 算法所要解决的问题 我们在前面已经说过，k 期望寿命最短路径是指，s t d 网络中源点s 和目的地d 之 间的期望寿命最一短，第二短，一直到第k 短的那k 条路径。这正是本节的k r e l s p 算法所要寻找的那k 条路径。具体而言，本节求解的问题是：在s t d 网络中，对于任 意给定的在源点s 的出发时刻t o ，预先规划出从单源点s 到单目的地d 之间的k 期望寿 命最短路径。也就是说，对于任意给定的出发时刻t o 预先寻找出从单源点j 到达单目的 随机时间依赖网络中的路径规划算法 地d 的期望寿命第一短的路径、第二短的路径，一直到第k 短的路径。换言之，根据 分布于该s t d 网络中的历史数据，在出发前就先寻找出k 条统计意义上的最优路径。 这显然是一个预规划问题( 口p r i o r ip r o b l e m ) 。 此外，我们假设s t d 网络中每条弧的寿命都是相互独立的随机变量，并且根据个 体到达中间结点1 ，( 结点，是弧邻。驴的尾结点) 的时刻“来决定是否允许个体在该结 点处等待。如果f ? 以 t 。 ，都有只( ，o ) a d q 曼( f o ) 。 证明：我们用反证法求证。假设存在一条初始时刻为t o 的源点s 和目的地d 之间的 路径岛o o ) = 妇= 1 ，d ，v 1 ，v j 1 ，v ，v j + 1 ，v = d ) q 刍( f o ) ，但是，它的某条子路径 只。( f o ) = 如= v o ，v l ，1 ，2 ，1 ，v ，) 萑a d q ：( ，o ) ，k k 。那么，我们可以从a d q ：纯) 中 取出k 条具有可靠性优先权的路径露纯) = p = i ；0 ，v ：，v 乞，1 ，) ，1 k k 。则根据定 理3 可知相应扩展路径扣= i ；0 ，y ，吐l ，v f ，u + 1 ，v h - 1 = d ) s 耐厶( t o ) ，再由定理2 可 知，在t o 时刻从源点j 出发分别沿这k 条扩展路径到达目的地d 时系统的期望失效时刻 都一定不大于沿只d ( “) 到达目的地d 时系统的期望失效时刻，因此，只d ( “) 不可能成为 k 期望寿命最短路径，这与假设矛盾。证毕。 该定理说明：到达目的地的k 期望寿命最短路径集中的任何一条路径一定是由具 有可靠性优先权的子路径组成的。通俗的讲就是，最优路径的子路径也是最优的。因此， 我们在设计kr e l s p 算法时，可以将不具有可靠性性优先权的子路径删除，这是本节 kr e l s p