（基础数学专业论文）随机网络中的动态最短路研究.pdf

摘要 在传统的最短路径问题中，假设网络中的权值是静态的、确定的，这些 假设在i t s 、计算机网络与通信等许多应用领域是不现实的。时变、随机网络 最短路问题突破了传统的最短路径问题的局限性，成为i t s 的基础理论。新的 现实问题使得最短路的计算变得非常困难。 本文针对出现的新问题及前人研究中存在的问题，重点研究了时变随机 网络中的最短路问题。本文的工作分为三部分： ( 1 ) 总结了前人的研究成果，并指出存在的问题。 ( 2 ) 从有限覆盖定理入手，针对权值为关于时间t 的连续函数的动态最 短路问题，分析某个时刻的最短路与该时刻的邻域内的最短路关系，求解某 个时刻从起点到终点的最短路。在求解权值为连续函数的随机网络在某个时 刻的动态最短路时，将关于时间的闭区问划分为有限个恰当间隔的小区间， 运用权值期望的方法将各小区间上的权值函数转化为离散函数来解决。 ( 3 ) 基于蚁群算法设计了时变随机网络中最短路的算法，实验证明该算 法可以有效的求解随机网络中实时最短路问题。 本文的研究有一定的理论意义和实用价值，研究成果可应用于智能交通系 统( i t s ) ，计算机网络与通信等许多应用领域。 关键词：随机网络，动态最短路问题，有限覆盖定理，改进的d i j k s t r a 算法， 蚁群算法 a bs t r a c t i ta s s u m e st h a tt h ew e i g h to ft h ea r c si nt r a d i t i o n a ln e t w o r ki ss t a t i ca n da d e t e r m i n a t en u m b e r , w h i c hi sn o tt r u ei nm a n yf i e l d ss u c ha si n t e l l i g e n t t r a n s p o r t a t i o ns y s t e ma n dc o m p u t e rn e t w o r ka n dc o m m u n i c a t i o nf i e l d s t h e s h o r t e s tp a t hp r o b l e m si nv a r i a b l e t i m ea n ds t o c h a s t i cn e t w o r kb r e a kt h r o u g ht h e l i m i to f t r a d i t i o n a ls h o r t e s tp a t hp r o b l e m sa n db e c o m ef o u n d a t i o nt h e o r yi ni t s t h en e wr e a lp r o b l e m sm a k et h es h o r t e s tp a t hc o m p u t i n gt ob em o r ed i f f i c u l t i nt h i sp a p e r , c o m p a r e dw i t ht h en e wp r o b l e ma n dt h eo l dp r o b l e m se x i s t i n g i nt h ef o r m e rr e s e a r c h ，w em a i n l yf o c u so nt h er e s e a r c ho fd y n a m i cs h o r t e s tp a t hi n av a r i a b l e t i m ea n ds t o c h a s t i cn e t w o r k o u rw o r ki sd i v i d e di nt ot h r e ep a r t s ： ( 1 ) s u m m a r i z et h ef o r m e rr e s e a r c hr e s u l t ，a n di n d i c a t et h ee x i s t i n gp r o b l e m s ( 2 ) f o rt h er a n d o mn e t w o r kw h i c h sw e i g h t sa r ec o n t i n u o u s f u n c t i o n so f t i m e ，w ed i s c u s so nt h er e l a t i o na b o u tt h es h o r t e s tp a t ha tam o m e n ta n dt h e s h o r t e s tp a t ho ft h em o m e n t sn e i g h b o r h o o da n dg e tt h es o l u t i o nf o rt h es h o r t e s t p a t hf r o mt h es t a r tn o d et ot h ee n dn o d ea tam o m e n tu s i n gt h el i m i t e dc o v e r a g e t h e o r e m w h e ns o l v i n gt h ed y n a m i cs h o r t e s tp a t ha tas p e c i f i ct i m ei nas t o c h a s t i c n e t w o r kw h i c h sw e i g h t sa r ec o n t i n u o u sf u n c t i o n so ft i m et ，w ed i v i d et h ec l o s e d i n t e r v a li n t oaf i n i t en u m b e ro ft i n yp r o p e ri n t e r v a l ，t r a n s f o r mt h ec o n t i n u o u s f u n c t i o ni n t od i s c r e t ef u n c t i o n su s i n ge x p e c t a t i o n ( 3 ) b a s e do nt h ea n tc o l o n ya l g o r i t h m ，w ed e s i g nan e wa l g o r i t h mf o rt h e s h o r t e s tp a t hp r o b l e m si nv a r i a b l e t i m ea n ds t o c h a s t i cn e t w o r k t h i sa l g o r i t h mi s p r o v e dt o b ea ne f f e c t i v es o l u t i o nt ot h er e a l t i m es h o r t e s tp a t hi ns t o c h a s t i c n e t w o r k t h es t u d yo ft h i sp a p e rh a si m p o r t a n tt h e o r e t i c a la n dp r a c t i c a lv a l u e s t h e r e s u l to ft h er e s e a r c hc a nb e a p p l i e d i nm a n yf i e l d s ，s u c ha s i n t e l l i g e n t t r a n s p o r t a t i o ns y s t e m ( i t s ) ，c o m p u t e rn e t w o r ka n dc o m m u n i c a t i o n ，e t c k e yw o r d s ：r a n d o mn e t w o r k ，d y n a m i cs h o r t e s tp a t h ，l i m it e dc o v e r a g e t h e o r e m ，a d v a n c e dd i j k s t r aa l g o r i t h m ，a n tc o l o n ya l g o r i t h m 中央民族大学研究生学位论文作者声明 本人声明：本人呈交的学位论文是本人在导师指导下取得的研究成果。 对前人及其他人员对本文的启发和贡献已在论文中作出了明确的声明，并表 示了谢意。论文中除了特易j , d n 以标注和致谢的地方外，不包含其他人和其它 机构已经发表或者撰写过的研究成果。 本人同意学校根据中华人民共和国学位条例暂行实施办法等有关规 定将本人学位论文向国家有关部门或资料库送交论文或电子版，允许论文被 查阅和借阅；本人授权中央民族大学可以将本人学位论文的全部或者部分内 容编入有关数据库进行检索，可以采用影印、缩印或者其它复印手段和汇编 学位论文( 保密论文在解密后遵守此规定) 。 作者签名：重盎日期：二虹年月生日 第一章绪论弟一早 三；酉下匕 这篇论文是关于随机网络两点问最短路问题的研究。随机网络是指网络中弧的权值具 有不确定性。这项研究起因于智能交通系统、计算机网络系统、通信系统、紧急服务运输 系统等众多应用领域对具有时变，不确定性和多样性的最短路径算法的需求。这些应用需 求计算满足一定约束的路径，这些路径计算问题有些已经得到解决或者通过现有的算法来 解决。然而，还有许多路径计算问题还没有遇到，存在许多具有挑战性的路径计算问题有 待解决。本文是针对这些尚未解决的路径计算问题以及对现有研究成果从理论上进行研究 或进行改进开展研究工作的。具体包括随机网络最短路的理论研究，计算方法的研究。 第一节随机网络中动态最短路研究的科学依据及理论意义 随机网络问题是网络最优化关键技术的核心问题，并成为许多网络优化问题的子问题 。在传统的最短路径问题中，假设网络中弧的权值建模成随时问变化的、随机的，因此 突破了传统的最短路径问题的局限性，能够描述现实网络系统的时变性和随机性。此外， 由于各种网络系统的规模越来越大、越来越复杂，大规模网络最短路的求解效率成为人们 追求的目标，传统的最短路径算法理论在时变、随机网络不能够证确的求解新的最短路问 题。新的现实问题使得传统的最短路径算法面临新的挑战，其理论有待于进一步发展，特 别是从1 9 9 0 年，网路流和匹配算法成为离散数学和理论计算机科学的第一个挑战问题心1 ， 激发了人们对各种最短路径算法的广泛研究，引起了计算机科学、交通工程、通信工程、 系统工程、运筹学等学科学者的普遍重视和研究。 时变随机网络最短路问题研究是交叉学科研究领域，是图论与组合数学，计算机科学 理论、计算机仿真技术、概率论与数理统计、通信理论、控制理论、交通科学、以及管理 科学的综合反映，是一门多学科交叉的新兴边缘学科，是- j 7 处于发展中的学科口1 。不同 学科的相互交叉、相互渗透、相互促进，极有可能创造出新理论、新方法，因此，随机网 络最短路问题具有科学依据和重要的理论意义。 第二节随机网络最短路的研究意义 随机网络动态最短路问题是一类普遍受到重视和研究的图论网络优化问题，具有非常 广泛的应用领域，这主要是因为：( 1 ) 实践中我们经常遇到类似的应用要求；( 2 ) 它为研究 更复杂的网络流问题提供了基础；( 3 ) 是解决许多复杂的网络优化问题的子问题之一。 本文主要针对智能交通系统的应用背景和计算机网络与通信系统的新需求进行介绍。 这两个新兴的应用领域产生了许多有待解决的新问题。美国国会1 9 9 1 年制定的智能交通系 统( i t s ) 发展战略规划指出：i t s 的主要目标是通过应用先进的技术和现代化算法方法学来 提高运输效率。这些需求在大多数情况下排除了现有算法的可用性3 。在i t s 中，0 _ d 对( 源 一目的地) 之间的最短路径应是时变的，具体包括出行者出发时间的时变性，到达目的地 的时变性，交通流分布不均匀性和时空性，这是i t s 的基础理论嵋1 。在交通网络以及其他网 络系统中，不仅仅存在确定性时变最短路径问题，而且普遍存在不确定性的最短路径问题， i t s 导致了各种弧的代价具有随机性的最短路径问题阳叫。 在实际运输过程中，影响运输时间的主要因素是交通路口红绿灯引起的等待，上下班 高峰期路况拥堵分布情况等。运输车辆遇到交通路口红绿灯而停留的时f n j 又是预先不可知 的，只有运输车辆行驶的交通路口时才能确定等待时间。在这种动态交通网络中，决策者 要考虑选择一条最快到达目的地的路径，那么这条路径该如何选择? 这些参数对于决策者 和运输部门起着至关重要的作用。因此，如果能找到一条在不确定交通网络中的实时最短 路径，无疑会为公司运输部门制定合理的路径选择方案提供有效的决策依据。 在计算机网络与通信系统中，下一代互联网络的体系结构、网络路由算法是核心技术 之一。目前的计算机网络路由算法，把网络链路权值看作是静态的、确定的、不随时间变 化的，这是不符合实际的。对于网络信息不精确的情况，国际上的研究处于起步阶段，只 有一些初步的描述和结果2 1 ；基于随机网络的路由理论也远未成型3 叫引。新一代高速互联 网络的大规模网络模型也成为人们关注和有待研究的问题，该模型应能描述传输的突发 性、网络环境信息交换和应用的动态性、随机性，这些新的特性使得网络链路的状态具有 不确定性。 在这样的背景下，本文主要研究了随机网络的动态最短路问题的基础理论，基本算法， 解决随机网络路径计算问题以及提高计算效率问题。这些算法对智能运输系统中路径选择 问题以及i n t e r n e t 网络路由问题都有借鉴意义。 第三节论文的组织结构 本文组织结构为： 第一章绪论，简要介绍随机网络实时最短路径问题，研究该问题的科学依据，理论意义及 现实意义。 第二章先介绍最短路问题的基本概念，再简要介绍静态最短路经典算法，最后给出随机 网络最短路问题的定义及研究现状，指出动态最短路问题研究存在的问题以及本文的主要 贡献。 第三章指出随机网络中动念最短路的两个重要特征。 第四章建立随机网络动念最短路模型，结合有限覆盖定理设计改进的d i j k s t r a 算法，并 用此算法求解时间依赖随机网络中动态最短路问题。 第五章介绍了蚁群算法的基本理论及其应用现状，基于蚁群算法提出求解随机网络实时 最短路问题的求解方案，并且对其进行了实验模拟，分析结果。 第六章给出结论，展望将来的工作。 第二章最短路问题 最短路问题是运筹学中的一个经典问题，它已被广泛的应用于计算机科学、交通工程、 通信工程、系统工程、运筹学等众多领域。不同领域的不同需求，使得最短路径呈现为多 样性，人们对最短路径算法的研究侧重于不同的方面。从大类上可迸行如下分类：按照时间 来分类，分为静态最短路径问题和动态( 时变) 最短路径问题；按照确定性与非确定性来分， 分为确定型最短路径问题和随机最短路径问题；按照网络规模大小来分，可分为小规模网 络最短路径问题和大规模网络最短路径问题。各大类之问的相互组合产生了各种各样的最 短路径问题。在本章中将分别简要介绍各类最短路问题。 第一节最短路问题的基本概念 定义2 1 1 有向图给定一个有向图d 的三元组为( v ，e ，f ) ，其中v 是一个非空集合，其 元素称为有向图的结点；e 是一个集合，其元素为有向图的弧段( 边) ；f 是从e 到v v 上的映射( 函数) 。 定义2 1 2 最短路设给定一个赋权有向图d = ( v ，e ，f ) ，记d 中每一条弧( v ，v ，) 上的权 为w ，。给定d 中一个起点v 。和终点v t ，设p 是d 中从k 到v ，的一条路。则定义路p 的权 是p 中所有弧的权之和。记为，( p ) ，即 ，( 尸) = w 盯 ( y ，- y 卢尸 又若p + 是d 图中v 。到v ，的一条路，且满足 ，( p ) = m i n ，( 尸) i p 为v 到v 舻路) 式中对d 的所有从匕到y ，的路p 取最小，则称p 4 为从匕到v ，的最短路，( p ) 为匕从1 ，到 的最短距离。 在一个图d = ( v ，e ，f ) 中，求从屹到v ，的最短路和最短距离的问题就称为最短路问题。 第二节静态最短路研究 当网络中的权值是一个常量时( 固定值、不随时间变化的) ，这样的网络称之为静态网 络，相应的求解网络中两点之问的最短( 最优) 路径，或者从源结点到所有其他结点的最短 路，或者所有结点之间的最短路的算法称之为静态最短路径算法。这类算法属于传统的最 短路径算法。人们对这类问题的研究已有相当的历史，美国著名的数学家，动态规划的鼻 4 祖r b e l i m a n 在1 9 5 8 年研究了这问题心0 1 ；著名的计算机科学家荷兰的e w d i j k s t r a 在1 9 5 9 年提出了著名的、具有深远影响的最短路径算法( d i j k s t r a 算法) 瞳，人们继 d i j k s t r a 丌创性的工作提出了大量求解最短路径问题的方法，其理论不断发展，产生了大 量算法，c h e r k a s s k y ，g a l d b e r g 和r a d z i k ( 1 9 9 6 ) 比3 对1 7 个最短路径算法进行了理论分析 和试验评价。按照不同类型分为标号设置方法、标号修改方法、动念规划方法、基于线性 代数方法、启发式和双向启发式算法、基于流体神经网络的算法。这些算法属于静念算法， 即处理固定网络拓扑和固定的权值。下面我们将介绍两种经典的静态最短路问题， d ij k s t r a 算法和胁算法。 一、d i j k s t r a 算法 o i j k s t r a 算法是一种标记法，它的基本思路是从起点v 。出发，逐步向外探寻最短路， 执行过程中，给每一个顶点y ，标号( 兄，z ，) 。其中彳，是正数，它表示获得此标号的前一点的 下标；，或表示从起点1 ，到该点，的最短路的权( 称为固定标号，记为p 标号) 或表示 从起点1 ，。到该点1 ，的最短路的权的上界( 称为临时标号，记为t 标号) 。方法的每一步是 去修改t 标号，并且把某一个具有t 标号的点改变为具有p 标号的点，从而使d 中具有p 标号的顶点数多了一个。这样至多经过p 一1 步，就可以求出从y ，到y ，及各点的最短路。再 根据每一点的第一个数五，反向追踪找出最短路径。 用p ，t 分别表示某个顶点的p 标号、t 标号，s ：表示在第i 步已具有p 标号点的集合。 d i j k s t r a 算法的具体步骤： ( 1 ) 开始时，令f = o ，s 。= v ，) ，旯，= o ，p ( v ，) = 0 ，对每个v ，1 ，s ，令兄， - s ，k = s 。 如果s ，= v ，算法终止。这时，对每个y ，j ，l ，= p ( v ”否则转下一步。 ( 2 ) 设v t 是刚获得p 标号的点。考察每个使( 1 ，足，v ，) 彳且将v ，仨s ，将r ( 1 ，) 修改为 丁( 1 ，) = m i n t t ( v j ) ，尸( k ) + j 公式( 2 1 ) 如果t ( v ) p ( 1 ，。) + w 灯则把丁( 1 ，) 修改为p ( v 。) + w 茸，把兄修改为k ；否则不修改。 ( 3 ) 令 t ( v i , ) = m 2 r ( y 川 公式( 2 - 2 ) 如果丁 g ，+ 烈v ，叻，若是，贝, l jg 。= g + 烈v ，纠，a = v ； 若w s ，判断是否有g 。 g 。+ d ( y ，w ) ，若是，则g 。= g 。+ j d ( y ，w ) ，r = y ； 若w 萑p 且w 芒s ，令g wg 。+ d ( v ，w ) ，尸w = v ，p = p u w 计算结点w 的估计函数 宰一g 。+ j i i 幸，转( 2 ) ： ( 4 ) 从目标点1 ，开始，利用回溯的方法找到根据其父节点p n ，依次类推，最终找到 起始点1 ，从而得到从起始点到目标点的最短路径，以及最短距离g 。，算法终止。 这些算法已成为确定情况下的经典算法，并且得到广泛应用。但是这些静态假设在许 多应用中不一定是真的，计算机网络与通信、分布式处理和智能交通系统( i t s ) 的兴起给 这个传统的研究课题带来了新的方向一时间依赖随机网络的动态最短路问题。 第三节动态最短路研究 随着最短路问题的深入研究，人们发现传统的最短路径理论和算法在权变的网络中， 有时并不适用。在实践中，网络特征可能会实时变化，要求最短路径算法必须实时更新。这 类问题集中在交通网络的实时导航，调度和计算机互联网络的数据传递路由等方面。例如 在互联网访问量增大时，网络的运行时间会有所延迟：在生产系统中，受资源供应的影响， 作业时间也会延长或缩短：尤其在城市交通系统中，随着车流的变化及j j 堵现象的发生，各 路段的通行能力及车速限制将随时间变化 传统的最短路算法并不能求出精确这类问题的解。下面，我们将给出动念最短路问题 的定义，并举例说明传统静态最短路理论并不适用于这类问题。 一、动态最短路问题的定义 定义2 3 1 在网络中如果用随机变量而不是用简单的标量表达边权，该随机变量服从离 散的或连续的概率分布函数，称这样的网络叫随机网络。 定义2 3 2 动态最短路给定一个赋权有向图( v ，e ，g ) ，其中v = _ ，哆，) ，是有限点 集；e 是有限边集，e v v ；记d 中每一条弧( v ，) 上的权为岛( f ) 。岛( f ) 不是常数，它 随着时间演进而发生变化。g 是对于每一条边权函数岛( f ) 的矩阵。给定d 中一个起点v s 和 7 终点v ，设开始时刻为t o ，p 是d 中从k 到v t 的一条路。则定义路p 的权是p 中所有弧的 权之和，记为，( pt o ) ，即 z c plt 。) = g 打 ( v j ，1 ，j ) e p 。 又若p 术是d 图中到y ，的一条路，且满足 z ( pit o ) = m i n ( pif o ) f p 为v 吣舻路，t 为出发时刻 式中对d 的所有从v 。到v ，的路p 取最小，则称p + 为在i o 时刻出发从y 。到v 的动态最短路， ，( p 宰lt ) 为从v 。到v ，的动态最短距离。 确定性网络中的固定网络拓扑和固定的权值的假设在很多实际应用中都是不合理的。 时间依赖的网络中的最短路问题比传统静态最短路更具有实际意义。因而研究随机网络的 动态最短路问题称为当前的一个热点。区别于一般最短路问题，动念最短路问题是针对网 络中弧的权值是变动的这一实际需求提出来的，它的问题求解更加复杂，然而适用范围却 很广。因而，动态最短路问题引起国内外专家学者广泛的研究。 二、动态最短路问题研究现状 在实践中，网络特征可能会实时变化，要求最短路径算法必须实时更新。这类问题集中 在交通网络的实时导航，调度和计算机互联网络的数据传递路由等方面。我们称这种问题 为动态最短路问题。此类问题中，边的权值随机变化，大多数情况下边权为时间的变化依 赖于时间。时变随机网络的研究可以分为两个方向，一类是对动态权值的观察和预测，例如 智能交通系统中，站点之间的行程时i 日j 随交通流量和红绿灯控制等因素的影响随时间动态 变化，孙喜梅等人利用随机服务系统理论结合多元统计回归方法提出了实时动态路段行程 时间预测的实用模型心3 3 。吴成东等人研究了基于神经网络的交通神经网络的交通信息实时 预测方法，探讨了基于遗传算法的最短路求解动态路径诱导问题心。另一类的研究集中在 对于动态最短路问题的算法的研究上。文献 2 5 j 运用对a 木算法解决满足先进先出原则的动 态网络的性能进行了试验和性能分析。文献 2 6 从理论上证明了传统的最短路径算法，如 n i j k s t r a 算法和标号设置算法等不能正确的求解出动态网络中的最短路问题，并提出了求 解最小时间路径的优化条件和改进的o i j k s t r a 算法。文献 2 7 中e 1 i s edm i l l e r h o o k s 和h a n ism a h m a s s a n i 研究了边权是时间依赖的离散时间变量的网络，给出了最小可能时 间的最短路算法以及相关概率的下界，但是当路径由9 条以上弧组成的时候，理论计算上 的最短路实现的概率一般不大于1 0 - 2 ，基本不可能实现。文献 2 8 研究了随机时间依赖网 络，给出了一个启发式算法，但该算法并不能保证总是找到最短期望路。该算法不仅能解决 弧权是离散的随机变量的最短期望路问题，而且在弧权是连续分布的随机变量的情况下， 依然有效。 第四节动态最短路问题研究存在的问题 目前，对于时间依赖随机网络动态最短路问题，国内外研究现状存在的问题、不足和 有待进一步研究的问题主要是： 1 ) 到目前为止，人们只从实例上给出了传统的最短路径理论和算法在时间依赖网络中 是不正确的，给予理论证明得很少； 2 ) 认识传统的理论和算法是不j 下确的，仅仅是解决问题的开始，关键在于给出解决问 题的理论基础，按照新的理论基础可以设计不同的算法； 3 ) 在时间依赖随机网络动念最短路的研究中，人们研究的前提假设是网络中随时间变 化的权值函数是己知的，但是在现实中这个函数是未知，因此如何得到这个函数是有待解 决的另一个关键问题。 第五节本论文的主要贡献 本论文所做的主要贡献是从理论上研究了随机网络动态最短路问题，并提出了新的解 决方案。具体包括一下几个方面： 1 ) 对当前国际上随机网络动念最短路的研究状况，进行了系统、全面的归纳，总结和分 析。 2 ) 简要概括传统最短路径算法，并指出d i j k s t r a 算法和标号设置算法，在时间依赖的 随机网络上不能有效地求解最短路问题； 3 ) 在没有限制性条件下，给出了时问依赖的随机网络动态最短路模型以及求解最短路 的两种重要算法。第一种是结合有限覆盖定理改进d i j k s t r a 算法，第二种是基于蚁群算 法设计的动态最短路算法。 4 ) 模拟仿真，分析结果。实验结果表明是这两种算法是j 下确的有效的。 第六节小结 本章简要介绍了最短路问题的基本概念。最短路问题有多种划分方法，根据权是否 9 为固定不变的，可将其分为静态最短路问题和动念最短路问题；针对静态最短路问题，简 要介绍静态最短路经典算法一d ij k s t r a 算法和a 冰算法；针对动态最短路问题问题，本章给 出了明确定义，概括其研究现状，指出动态最短路问题研究现存的问题以及本文的主要贡 献。 1 0 第三章随机网络中的动态最短路的特征 第一节理论基础 p 问题是指能够在多项式时间求解的判定问题( 判定问题指只需要回答是和不是的问 题) ，而n p 问题则是指那些其肯定解能够在给定正确信息下在多项式时间内验证的判定问 题。比如，要判定一个数是合数，如果给定一个约数，我们就很快判定它就是合数。所以 判定一个数是合数的问题属于n p 。 n p 完全( n pc o m p l e t e ，简记为n p c ) 问题，指的是那些n p 中最难的那些问题：所有其 它的n p 问题都可以归约到这些n p 完全问题。它的定义是，如果你可以找到一个解决某个 n p - c o m p l e t e 问题的多项式算法，那么所有的n p 问题都将可以很容易地解决。 通常证明一个问题a 是n p c o m p l e t e 需要两步，第一先证明a 是n p 的，即满足容易 被检查这个性质；第二步是构造一个从某个己知的n p - c o m p l e t e 问题b 到a 的多项式 变换，使得如果b 能够被容易地求解，a 也能被容易地解决。这样一来，我们至少需要 知道一个n p - c o m p l e t e 问题。 想要证明一个问题是n p c ，最简单的方法是先证明它属于n p ，然后将它变换成某个已 知是n p c 的问题。因此在学习变换技巧前，先熟悉各种不同类型的n p c 问题是很有用的。 下面列出了一些以决定性命题表示的著名n p c 问题： 御尔可满足性问题：( b o o l e a ns a t i s f i a b i l i t yp r o b l e m ) ( s a t ) n - p u z z l e 问题( 华容道问题) ：( n p u z z l e ) 背包问题：( k n a p s a c kp r o b l e m ) 哈密尔顿回圈问题：( h a m i lt o n i a nc y c l ep r o b l e m ) 旅行推销员问题：( t r a v e l i n gs a l e s m a np r o b l e m ) 子图同构问题：( s u b g r a p hi s o m o r p h i s mp r o b l e m ) 子集合加总问题：( s u b s e ts u mp r o b l e m ) 分团问题：( c 1 i q u ep r o b l e m ) 顶点涵盖问题：( v e r t e xc o v e rp r o b l e m ) 独立项点集问题：( i n d e p e n d e n ts e tp r o b l e m ) 图着色问题( 四色定理) ：( g r a p hc o l o r i n gp r o b l e m ) 图3 - 1 变换流程图 图3 1 是一些n p c 问题及证明其为n p c 问题的变换流程图。在流程图中，箭头代表的 是从何问题变换成另一问题的过程，要注意的是这张图并不代表这些问题的数学关系，事 实上任两个本质为n p c 的问题都可以以多项式时间变换，这图仅指示可以让研究者较为简 单地变换问题的顺序。 背包问题是一个关于最优解的经典问题。通常被讨论的最多的，最经典的背包问题是0 - 1 背包问题( 0 - 1k n a p s a c kp r o b l e m ) 。o 一1 背包问题的描述大概是这个样子的，“强盗在抢 劫一家商店，发现n 件物品；对于其中的第i 件物品，其价格为y ，重a i ( 所有物品的价格 和重量都是整数) 。这个贼希望尽可能的拿走所有最有价值物品，但是他的背包最大能承 受的重量为b ( b 也为一个整数) ，他该怎样爿能保证拿走物品的总价值最高? ”类似这样 的l 司题被称为0 一l 背包问题是因为对于其中的每一件物品，强盗只能选择拿或者不拿，但 是，他不能够拿走其中每件物品的一部分。 背包问题可以用数学语言描述如下： 给定m 个j 下整数口，a ：口。及f 整数b ，问是否存在子集s l 一2 删 使得口，= 6 7 这罩 假定1 6 a = 口，a i e s 第二节动态最短路问题的特征 特征1 静态最短路理论和算法并不完全适用于动态最短路问题。 早期，人们对随机网络的特性的认识存在局限性，认为传统的最短路径理论和算法 可以应用于时变动态网络。事实并不是这样的。图3 2 1 的实例来源于文献心2 ，下面的实 例说明了传统的静态最短路算法对于非静态网络是不适用的。 例3 2 1 ：如图3 - 2 所示的一个离散时间依赖的网络，求从结点1 在0 时刻出发到结点4 的最 短路。 g m ( t o ) 22 0 9 3 4 ( a o ) = 5 图3 2 离散时间依赖的网络 这个网络由四个结点四条边组成，假设起始时间为0 ，由结点1 到结点3 有两条路径，1 经过2 到达3 所需时间为2 0 。1 直接达到3 所需时| 、日j 为l o ，而9 3 。( 1 0 ) 2 2 0 ，9 3 4 ( 2 0 ) 2 5 ，如果采用 传统的d i j k s t r a 方法或者标号设置算法最短路是( 1 ，3 ，4 ) ，走行时i 日j 是3 0 ，但是路径 ( 1 ，2 ，3 ，4 ) 具有最小时问花费2 5 。 例3 2 2 ：如图3 - 3 所示的一个连续时问依赖的网络，求在0 时刻从结点1 出发到结点4 的最 短路。 9 1 3 ( o 】- 1 9 2 3 ( 1 ) = 4 o ( j 3 4 ( t ) = 1 + ( t 一5 ) 图3 - 3 连续时问依赖的网络 在0 时刻从结点1 出发到结点4 的最短路按照传统d i j k s t r a 方法或者标号设置算法是( 1 ， 3 ，4 ) ，走行时i 日j 是1 7 ；但是路径( 1 ，2 ，3 ，4 ) 具有最小走行时间为 由上面的两个例子，我们知道o i j k s t r a 算法和标号设置算法不能正确地求解随机网络 的最短路问题。特征1 成立。 特征2 动念路问题是n p 完全问题。 证明：首先，证明此判定问题属于n p 类。事实上，从节点1 到n 的一条长度不超过l 的路p 可以作为一个判掘( c e r t if i c a t e ) 。这是因为计算路p 的长度，即逐次将各段弧长( 依 赖于先前诸弧的运行时问) 相加，可以在多项式时间内完成，因而此判掘的有效性可以在 多项式内得以验证。这罩有一个自然的假定：对给定的时刻t ，计算函数w ，) 的值可在多 项式时问内完成。因此，动态路问题属于n p 类。 其次，证明背包问题可以按多项式归结为动态路问题。给定背包问题的实例 口。，a ：a 。；6 ) ，可以构造动态路问题的实例( 即网络g ) 如下：它有n l + 2 个节点0 ，1 ，2 ， ，m ，m + 1 ：对0 f m ，从节点f l 到节点i 有两条有向弧e j 及p i ，其中p j 的( 时 问) 长度为口i ，p j 的长度为o ( 均不依赖于时间) ；从节点m 到节点m + 1 有一条动念 弧p 川，其( 时间) 长度为 2 a ，t b + 1 ) 。由此可知，沿路p 进入弧p 刊的时刻 t 满足b s t t 磊。，则此时最短路线为毛。若在0 时刻出发 的各路线s 一，j ：，权值大小关系不变，仍为 ， f 2 。 ，则从时刻出发对应的 最短路仍为。露。 定理4 1 1 ( 有限覆盖定理幽1 ) 若丌区间集s 覆盖闭区问 a ，b ，则s 中存在有限个丌区i 日j 也覆盖闭区间 a ，b 。 一般来说，如果我们己知在闭区间 a ，b 上每一点的某个邻域内都具有性质p ，每一点 的邻域( 开区间) 集覆盖了 a ，b ，为了将性质p 扩充到整个闭区问 a ，b 上，这时，可用有 限覆盖定理，将覆盖 a ，b 的无限个邻域换成有限个邻域。 根据有限覆盖定理，对于闭区间时f b j 段o l 一，可取这个区l 、b j 上所有实数的小邻域集覆 1 6 盖这个闭区问，根据定理4 1 1 ，这无限个小区问集中定可以取到有限个开区l 白j 集覆盖这 个闭区间。再由这有限个小区间上最短路的存在性，得到整个闭区间时问段上的最短路肯 定存在。整个闭区间时问段上的最短路就是有限个小区间上最短路的并。 定理4 1 2 在闭区问时i 日j 段 f 。，t m 】上各边权值为连续函数的随机网络，如果在某个时刻t 时刻的最短路为s ，则在t 时刻的某邻域u ( f ) 内最短路线的选取仍为s 。 证明：设从起点到终点有h 条路。由于各边的权值为连续函数，则各边权值之和也为 时间t 的连续函数。即时刻出发对应的各条路_ ，s z ，屯的权值分别为，- ，z ，- ，i 如果 在时刻出发的最短路为豇，即vn ，n - - 1 h ，且刀k ，都有t 山 g 。( f ) + 厂( f + g 。( f ) ) ， 则转4 步，否则转第5 步。 4 令厂，( f ) = m i n 厂( f ) g ，( f ) + f ( f + g i 夕) ) ，s u c c ( i ) 2 j ； 将结点插入咋插入l i s t 表中， 转第5 步。 5 若l i s t v o = ，则停止。否则转第2 步。 上述算法结束后，如) 即为t 时刻从结点v 出发到达目t 撇a v n 的最短路的最小时问。 s u c c ( i ) = j 的操作建立了最短路径的生成树。这个算法对权值为离散函数的随机网络比较 容易求解，对于权值为二次以上连续函数的情况，求解的过程中会遇到求解大于四次方程 的解的情况，因为五次或五次以上的方程不可能有代数解。所以求解边权为连续函数的随 机网络的在某个时刻t 从始点出发的最短路问题，需要先对权值做些处理，使得各边关于 时间的连续函数用离散函数来逼近。 定理4 2 1 。m 1 若为定义在闭区间 a ，b 上的连续函数，则在闭区间 a ，b 上可积。 根据定理4 2 1 ，可知对权值为连续函数的随机网络，任意一边( _ ，v j ) e 的权值岛( ) 闭区问 气+ k a ，t 。+ ( 后+ o a 上可积。对于边权为连续时间函数的随机网络模型( v x t ，e ，g ) 中的边权函数矩阵g 进行修正，将权值的连续函数转换成分段函数，取适当的时问f u j 隔，将 分段函数的函数值定义为连续函数在该时间段上的积分的平均值，也就是期望。在进行详 细计算分段函数的函数值之前，需要确定合适的时间问隔，的大小与网络中各条路的权 值之i 日j 的大小关系有关，为求精确性，时间f b j 隔越小越好，但是要是取得过小，计算量会 很大。因而为了提高算法效率，我们先根据网络中的节点数和起点到终点的某条路在某个 时刻的权值来确定一个比较小的a ，求得随机网络的一组最短路解，然后再检验以便进行修 正。我们可以先计算o 时刻从始点出发到达终点的任意一条通路的时间花费，记为l ，以此 作为取最大时间上限0 的一个参考。设定是较小的时间间隔，2 l l ( 1 0 n ) ，其中n 为网络 中的结点个数。以辱( ，) 表示按上述方法修正过的从结点m 在t 时刻出发到达结点0 的走行 时间。 训= 去s 掣删巩 其中是向下取整函数。g = ( 宫扩( f ) ) 是修正过的边权函数矩阵，在时间 t o ，t m c 尺区 间上定义的边权函数的矩阵，如表4 - 1 所示： 表4 1 ：各边动态时问表 边时段 ( ，气+ a )( t o + a ，t o + 2 a )( t o + ( 2 j 7 v 一1 ) a ，t o + 2 n a ) ( m ，吃) 喜：( f 。)季。：( f 。+ )季2 ( fo + ( 2 一1 ) ) ( v f ，1 ，) 喜f ，( f 。)季口( f o + )喜o - ( t 。+ ( 2 一1 ) a ) 这样，我们就把权值为连续函数的随机网络转化为权值为离散函数的随机网络，可以 运用下面进一步改进的d i j k s t r a 算法来求解初始时刻o 出发的最短路。对于每条边需要计 算的总时间跨度需要根据网络中边的条数和权值函数等情况来确定。对于所选取的，可以 求取一组解。验证所划分的小区间内，是否选择的是同一条最短路，若不是，需要对进行调 整，取为a 2 再求解。直到同- d , 区问内最短路的选取一样。根据有限覆盖定理，总可以 在有限步后找到最优解。 对于边权为连续函数的随机网络，进一步改进d i j k s t r a 算法，得到适合于边权为连续 1 9 函数的随机网络最短路算法。 1 ，计算在2 0 时刻从始点出发到达终点的任意一条通路时间花费l ，取a = 。0o , 0 ，其中 n 为网络中的结点个数。 2 求出边权矩阵g = ( 季，) ) 。 3 置r ) 20 ，对v v ，彳( f ) = o ，l i s t = k 。 4 从l i s t 中选取第一个结点作为当前结点，并把该结点从l i s t 表中删除( 结点心 一旦被删除，永不进入l i s t 表中) 。 5 对于每一个结点哆彳( j ) v o ，在每一时刻t e t ，若存在( f ) 季。( f ) + 厂( f + 季。( f ) ) ，则 转6 步，否则转第7 步。 6 令厂，( t ) = m i n f ，( f ) ，季f ( f ) + 厂( f + 季，( f ) ) ，s u c c ( i ) 2 j ；将结点吩插入l i s t 表中，转第7 步。 7 若l i