【毕业学位论文】（Word原稿）若干Routing问题的算法研究-应用数学

硕 士 学 位 论 文 题 目 : 若干 题的算法研究 研 究 生 张 玥 玥 专 业 应 用 数 学 指导教师 陈光亭 教 授 完成日期 2005 年 12 月 杭州电子科技大学硕士学位论文 若干 题的算法研究 研 究 生： 张 玥 玥 指导教师： 陈 光 亭 教授 2005 年 12 月 2005 杭州电子科技大学硕士学位论文 I 摘 要 题是一类具有 广泛实际背景的网络优化问题， 题在许多情形下与 问题紧密相关。 问题主要分为平面 问题和网络 问题两大类。 一般网络或平面上的 问题 (一个 其研究 有着悠久的历史。 在超大规模集成电路设计 ,光网络 ,计算机通讯网络上都有 着 非常重要的应用。 1990 年后 ,的研究有了飞速的发展。在这段时期内解决了 面上的 想 ,提出了多项式时间 近似方案。 在第一章绪论中 ,我们首先简单的介绍了平面和网络 小树问题 ,以及几类特殊的网络结构 ,比如 2结构 ,系列平行图结构 ,结构。之后介绍了带权约束的 小树问题 (带时延约束的 小树问题(完全 小树问题 ( 分层服务 小树问题(最后 ,我们介绍了另一 类 重要的 题，最快路（ 题 ，并给出了快 速 路的定义 ,以及最快路的几个重要的结果。 第二章 重点 研 究 2上带有费用约束的最短直径 问题。首先证明了该问题是 然后使用动态规划方法设计了直径受限最小费用 并在这个基础上设计了多项式时间近似方案。之后文章又提出了总时延受限的最小费用 问题，同样证明了该问题是 出了伪多项式时间算法 。 随着 发展， 视频点播、电视会议等新的业务 ,需要对多媒体信息传输质量有所要求，比如从源点到终端的传输时间。不能使用传统的最短路问题来建立模型。 在第三章， 介绍了快 速 路的概念，并解决了所有 顶点对 间最快路问题。本文采用标签设定算法，通过修改原网络，得到一个新网络，使得新网络中快速路的子路也是快速路。 最后 使用动态规划的方法，给出了所有顶 点 对之间最快路的算法 。 第四章介绍的是多路传输最快路的瓶颈扩容问题。当点对间的数据传输时间超过了人们可以容忍时间的时候，就需要对网络进行扩容。要求数据传输时间在人们容忍时间内，并且扩容 费用 最小。这是一个 用贪婪的思想给出了一个伪多项式时间算法。 关键词： ， 2 ， 速路 杭州电子科技大学硕士学位论文 is a 990s on of of It of on in in is to a in in a ,of is In we on in we we to of of we is In we of a we is we we a we is of in as by we to in we a to in on an a of a is a In we to in 州电子科技大学硕士学位论文 we to In we a on of to of 杭州电子科技大学硕士学位论文 录 摘 要 I 第 1 章 绪 论 小树问题简介 类特殊的网络结构 典的网络 小树问题的模型 快路 (介 文的主要工作 第 2 章 2上带有费用约束的最短直径 问题 有费用约束的最短直径 问题简介 2上的 题的复杂性 多项式时间算法 2上的 项式时间近似方案 7 2上的总时延约束问题 9 题的展望 5 第 3 章 所有顶点对之间最快路算法 6 速路背景简介 6 有顶点对之间最快路定义 6 络的转换及其性质 7 有顶点对之间最快路算法 8 第 4 章 多路传输最快路的瓶颈扩容问题 1 颈相关问题简介 1 路传输最快路的瓶颈扩容问题 2 路、多路路由问题简介 3 路传输最快路的瓶颈扩容问题是 3 大动态流 4 法的提出 5 例 8 致 谢 0 参考文献 1 附 录： 5 杭州电子科技大学硕士学位论文 1 第 1 章 绪 论 小树问题简介 小树问题 (组合优化问题中最为活跃的问题之一 1234，在现代的生产生活中有着广泛的应用，特别是计算机通讯网络 5、超大规模集成电路设计 (6有 着非常 重要 的 应用。 小树问题通常分为 几何 和网络两种情形 78。定义 别给出了平面和网络 小 树问题的定义。 定义 平面 小树问题 平面 小树问题的目标是在 欧氏平面 里找到支撑给定点集 S 的最短网络（树） 。 在该问题中允许在给定点集 S 之外引入新点，通过适当选取新点集 N，使由 问题是 题的推广。 300 年前 ,出了一个问题 :在 欧氏平面上有 3 个给定的点 ,找到一个点使得这个点到 3 个给定点的距离和最小。我 们知道这就是一棵 小树。 要提出了 小树问题 9。之后 ,0于 1941年在著名的 “中把这类问题归结为 题。二十世纪六十年代 ， 两篇重要的文章为后来的 的研究奠定了基础。 先给出了 面 的算法 11。 出了很多新的研究课题 12,比如引入了 的概念 ,并且把这个问题扩展到其它的度量空间。 定义目标点集 S 的 小树与最小支撑树总长度的比值为 。1976 年 ,3 证明了 面上的 为 2/3 。 1968年 ,出了 欧氏 平面上 为 3/2 的猜想。 1990 年 ,堵丁柱和黄光明证明了这个猜想 1415,在此之后 出了 1617上的 为 /(2 1)d 的猜想 18。 平面 小树 问题 ，主要有 面 小树问题，面 小树问题， 面 小树问题，以及 平面 小树问题。 欧氏距离以及上述几个距离下的 小树问题均是强 19。 杭州电子科技大学硕士学位论文 2 图 种常见平面 定义 正权无向网络上的 小树问题（ 给定无向图 ( , )G V E ,V 为顶点集， E 为边集，图 G 中各边 e 有相应费用 ()给定目标点集合 ，在图 G 中寻找各边费用之和最小的子树 T ，使得 S 中各点在该树中连通。 一般网络上的 20。 1使用最小生成树构造 出时间复杂度为 23( 2 ( ) )SO n n s的算法（这里 ,/n S s V S），3( ( ) 3 ( ) 2 ( ) )n s n s n s 的时间内找到最优解的算法 22。由于问题的困难度，许多学者使用不同的方法设计近似算法 2324252627。 将近似比改进到了 8。 在通信网络中，数据传输总是受到带宽等因素的 约束 ，有的时候，我们要求数据从源到用户端的传输时间有一定的限制。这就是带有服务质量的 问题 5。 数据或信息通常由网络中某信息源发送给多个用户，希望在网络中找到一棵根在源点且总费用最小的 ，这样的问题称为 题。 类特殊的网络结构 通常网络上的组合优化问题 都是 是可以在一些特殊的稀疏网络上设计多项式时间的最优解算法。通常研究的稀疏网络有 :2 2930，系列平行图 31， 3233，一般圈树图等 34。 定义 2 定义一个三角形为一个 2给定一个 2其中一条边 ( , )加入一个点 z 并分别连接两个端点得到边 ( , ), ( , ),z x z y 得到的图仍然 为 2。由此不断增加三角形，得到一般的 2。 杭州电子科技大学硕士学位论文 3 图 演示 系列平行图是 2的子图（通常称系列平行图为 ）。法可以在 () 35。因此经常可以把系列平行图上的问题放在 2 上面进行研究。 图 状系列平行图 2和系列平行图表现出了与树相似的递归性质 ,于是可以根据这个递归性质对一些组合优化 问题设计动态规划算法。 系列平行图上对 分层服务 小树问题 (计动态规划算法 ,在多项式时间内获得最优解 36。 系列平行图上对 带权约束的 小树问题 (计 2。 G.系列 平行 图上研究顶点带权重的染色问题37。论文的第 2 章节将介绍两个 2上的带有不同 约束 的 问题模型 ,分别 证明了这两个问题是 并给出了 法。 定义 哈 林图（ 给定一个嵌入的树 T ，其不含有度数为 2 的点，然后用边将 T 中连续的叶子连接起来形成圈 C（连接叶子的顺序事先由内嵌的树 T 确定），图 H T C 为哈林图。 图 林图及扇形收缩的演示 杭州电子科技大学硕士学位论文 4 从定义 演示图 难发现 ,哈 林图收缩扇形后仍然是哈林图，哈林图有着很好的递归性质 ,可以根据它们的递归性对一些问题设计动态规划算法。 上研究 题 32,证明该问题是 并给出了多项式时间近似方案 ( 研究哈林图上的最优线性指派问题（ 38。 典的网络 小树问题的模型 定义 带权约束的 小树问题 (给定无向图 ( , )G V E ， V 为顶点集， E 为边集， ()图 G 中各边 e 的相应费用。 ()e 为各边的相应的权重。给定目标点集合 以及 总权和的上限 W ，寻找 G 的各边费用之和最小的子树 T ，使得 S 中各点在该树中连通并且满足() 。 在一般的网络上 ,该问题是强 的结果不多。在特殊的稀疏网络上建立 型 则能得到较好的结果 。 别在系列平行图上 30和哈林图 32上研究了 明了问题是 ，并根据这两类网络的很好的递归性，设计了多项式时间近似方案。 定义 带时延约束的 小树问题 (给定无向图 ( , )G V E ， V 为顶点集， E 为边集， ()图 G 中各边 e 的相应的费用。 ()定包含源点和目标点的集合 ，寻找 G 的各边费用之和最小的子树 T ，使得 S 中各点在该树中连通并且满足源点沿该树中的路到达各目标点的时延 不 超过时延上界。 出了带时延约束的 小树问题 39，该问题比传统的 难，很难找到好的近似算法。 多项式时间内解决了固定拓扑结构的题 40，下面给出了实际中经常用到的时延限制： 有界最长延迟 ( 令 s 是源， v 是用户， ( , )d s v 是数据从 s 传输到 v 的时间延 迟 。时间延迟 约束 定义为 ( ) m a x ( , )e l a y T d s v 。 是用户指定的最大延迟。 有界延迟变化 （ 要求从源传到任意两个用户的时间相差不能超过一个指定时间 。即&m a x ( , ) ( , ) u D v D d s v d s u ，其中 是用户指定的最大延迟。 平均延迟（ 有 D 个用户， 是用户指定的最大延迟 ,平均 时延约束 定义为： ( ) ( 1 / ) ( , ) D d s u 定义 完全 小树问题（ 给定无向图 ( , )G V E ， V 为顶点集， E 为边集， ()图 G 中各边 e 的相应的费用。给定包含源点和目标点的集合 ，寻找 G 的各边费用之和最小的子树杭州电子科技大学硕士学位论文 5 T ，使得 S 中各点在该树中连通，并且要求集合 S 中的目 标点都是 T 的叶子。 完全 小树问题在通讯网络和计算生物学等方面都有广泛的应用 41。该问题仍然是 研究了边长限制为 1 或 2 的完全 小树问题 42，证明该问题是 问题，并给出近似比为 8/5 的算法。 定义 分层服务 小树问题 (输入： 1. 无向图 ( , )G V E ，正整数 R 。 2. 函数 g ： 0 , 1 , 2 , . . . , 1。任意 ，整数 ()示顶点 x 的服务层次。 3. 函数 c ： 0 , 1 , 2 , . . . , 1 。 ( , )c e g 表示边 e 上提供服务层次为 g 的费用。对于任意 11 ，对于任意的 函数 c 满足 ( , ) ( , 1)c e i c e i并且( , 1 ) ( , 0 ) 0c e c e。 问题：分配给图 G 中每条边一个服务层次，使得任意两个顶点 ,接两者路上每条边的最小服务层次不小于 m ( ), ( )g x g y 。若存在这样的分配，确定最小的分配费用。若不存在，记录结果为 。 题在通信、交通等网络有着很广泛的应用，这方面的文章也比较多43444546。 出了系列平行图上 题的多项式时间算法 47。 义 个优化问题的多项式时间近似方案（ 一 系列 近似算法， 对于 一个任意小的值 0 ，这个方案 中有 一个 关于这个优化问题的 近似 比 为 1 的近似算法，并且对于每一个固定的 ，其运行时间对于实例的规模 n 是多项式的。 对于一个 题， 能得到一个 一件非常有意义的工作。 849证明了如果最小生成树上的最长边和最短边之比在一个常数范围内，那么一定就有一个多项式近似方案来解决 及 问题。 1995 年， 0和 152发现了一个非常有用的技术 ， 通过产生一个多项式时间的近似方案 来 解决 问题。这个发现是非常重要的。 它不仅可以在 问题上有很多的应用，同时也可以应用到 很多 其它 的组合优化问题中去。 快路 (介 随着 发展，出现了如视频点播、电视会议、远程学习、计算机协同工作等新的业务。这需要对多媒体信息传输质量有所要求，比如从源点到终端的传输时间。但是在现有的网络中，节点的信息拷贝 ,网络的信息传输等都需要时间。杭州电子科技大学硕士学位论文 6 并且信息传输时间还受到传输的信息量和带宽的 约束 。因此不能使用传统的最短路问题来建立模型。 1990 年 出了最快路 53(概念 ,并且在多项式时间内找到了一条从 s 到 t 的最快路。 对于不含负回路的有向网络 ( , , , , )G N E d b ,N 代表网络顶点的集合 ,n 为顶点的个数。 E 代表网络边的集合 ,m 为边的条数。 (, )t i j 是边 ( , )v v E上的数据传输延迟。 (, )bi j 为边 ( , )v v E上的带宽，这些边带有 r 个不同的带宽。12( , , ., )rb b b b是边的不同带宽的集合。 是任意两点对之间需要传输的数据量的集合。 下面给出快速路和最快路的定义。 定义 快速路 设 路12, , ., lP v v v 为一条1则 路 P 的延迟时间为 ：11( ) ( , ) t v v ， 路 P 的最大可用带宽为 ：11( ) m i n ( , )j l j b v v ， 沿着路 P 用带宽 b 传输 个单位的数据需要的总的传输时间为( , , ) ( ) / 1D P b T P b 。 定义 最快 路 点对 ( , ), )Pi j ,就是找一条快速路使得从据到 最快路在计算机通信有着很广泛的应用 ,很多学者都对其进行了研究 56575861。 3在 ( lo g )O r m r n r n 时间内找到一条最快路 ,算法的空间存储量为 ()之后 4等人在 ( lo g )O r m r n m 时间内找到一条最快路 ,算法的空间存储量有所改进为 ()后 ,0采用 法 在 ( lo g )O r m r n r n 时间内找到了一条从s 到 t 的最快路。这个算法在时间上和 算法的时间复杂性相同 ,但是在实际操作中 ,时间比 法的平均时间低。 对 最快路问题进行延伸 ,提出了一些新的问题。 5给出了 2()O 间复杂度的所有点对之间最快路的算法。 6给出了一 个 3( l o g )O k m n k m n k 算法 ,找到了点对 s,t 之间 k 条最快路的算法。 9研究了点对之间多条最快路同时进行信息传输的问题 ,并且给出了一个多项式时间算法。论文的第三章将讨论所有点对之间最快路算法。第四章提出了基于最快路的瓶颈扩容问题 ,首先证明了该问题是 之后给出了多项式时间近似方案。 文的主要工作 一般网络上的带时延约束的 小树问题 ( 文的第二章研究 2上带有费用约束的最短直 径 问题。首先证明了该杭州电子科技大学硕士学位论文 7 问题是 然后使用动态规划方法设计了直径受限最小费用 问题的伪多项式时间算法 ,并在这个 算法的 基础上设计了 费用受限的最短直径 问题的 多项式时间近似方案。之后文章又提出了总时延受限的最小费用 问题，同样证明了该问题是 出了伪多项式时间算法。 论文的第三章研究的是所有 顶点对 间最快路算法。首先 通过修改原网络 ,得到一个新网络 ,使得新网络中 最 快路的子路也是 最快 路。之后使用动态规划方法 ,给出了所有 顶点对 之间最快路算法。 在实际应用中 该算法在 时间上有一定的优势。 如果网络传输 单位的信息量需要时间1T,现在 ,我们需要在221内传完 单位的数据 ,这就需要在某些边上进行扩容。由于 各 边扩容费用不同 ,因此我们就需要寻找一个方案使得扩容费用最小。这就是 第四章研究的 多路传输最快 路的瓶颈扩容问题。本论文 先 提出这个问题 ,并 证明了这个问题是 最后给出了一个 伪多项式时间算法 。 杭州电子科技大学硕士学位论文 8 第 2 章 2上带有费用约束的最短直径 问题 有费用约束的最短直径 问题简介 随着组播 （ 术的发展，越来越多组播的应用和服务已经在 很快成为网络研究的一个热点。组播的特点是信息能够在网络的节点上进行拷贝 ,从而提供单点到多点通信以及多点到多点的通信。相对于点播来讲，组播可以有效的利用网络带宽，减少网络拥挤，提 高数据传播的效率。目前，组播技术成为许多网络应用的关键技术，例如：网络多媒体会议、远程教育、视频点播、网上实时转播、网络数据发布、分布式协同工作等等。在实际的互联网络中，信息的传输同时需要满足一定的服务质量 （ ，比如要求在规定的时间传输信息等。 计算机通讯网络通常可以看成一个无向图 ( , )G V E ,这里 V 为顶点集 ,E 为边集。在传统网络上的 题中，无向图中各 边 e 有一个相应的费用 ()对给定的顶点子集 ，寻找 G 的一个各边费用之和最小的子图，使得 S 中各点在该子图中连通。在这个问题中，每条边对应的参数只有一个费用，但是在实际问题中，尤其是通信网络中，每条边上除去一个费用，还会有一个时延，即信息通过该边所需的时间， 一般来讲，边的时延和边的费用是两个独立的参数。上面的组播和点播可以理解为，若将信息从某给定点在预定时间内传输到另一点且要求所走路径的总费用最小，这是一个约束最小费用路问题，也称为点播问题 (若是要把信息从某给定点在预定时间内传输到一个给定点集中的每一点而要求传输所用各边的费用之和最小，这可以理解为网络上带有时延约束的 是组播问题 (点播问题的研究比较多，有一些比较好的结果，而组播问题因为问题的难度，好的结果不多。在第一章，我们介绍了实际中 经常用到的一些时延限制。在本章我们 讨论 的是 费用 受限的 最短直径 问题 ，也称为带有费用约束的最短直径 问题 （ 简记为 意两点间时延不超过一定约束的最小费用 ，也称为带有直径约束的最小费用 （ 简记为 网络上 强 题，因此带有时延约束的 小树问题也是强络上 时延约束的 问题的延伸，因此也是强 2是稀疏网络中极为重要的一类网络 293032，有很好的递归的性质。在这类网络上有很多问题是 可以得到 多项式时间 近似方案的 ， 比如权重限制最小 问题 （ 等。本章主要研究 2 上的 杭州电子科技大学硕士学位论文 9 题。首先，证明 2上的 题是 次，研究直径受限的最小费用 问题，给 出了一个伪多项式时间算法。最后给出了 2上的 题的复杂性 首先我们给出 描述，描述如下： 设无向 2 ( , , , )G V E c ， V 代表网络顶点的集合， E 代表网络边的集合。 ()e 是边 上的 权重（或距离） , ()边 的费用。对于任意的两个点 u 和 v ,u 和点 v 的一条路，,()路,()的直径 ()树 T 上任意两点之间最长的 距 离 ， 也 就 是 树 上 的 任 意 两 个 叶 子 之 间 的 最 长 距 离 ，可知,( ) m a x ( ( ) )u v T u p。 树 的 费 用 ()树的 所 有 边 的 费 用 和 ， 可 知( ) ( ) c e 。对于一个给定的目标点集 D ， D V ,r 是目标点集 D 中点的个数，用的限制，我们需要得到一棵 2上的连接 D 中所有点的最短直径 。并且这棵树的费用 ()首先我们证明这个问题是 定理 2上的 题是 证明 ： 当 r =2 时 , 目标点集 D 中只有两 个点。此时， 2上的 上的权重限制最短路问题（ 称 因为 2上的 题是 32,因此 2上的 题也是 我们首先给出了 2上的直径受限的最小费用 问题 （ 伪多项式时间算法，然后在此基础上给出了 2上的 多项式时间近似方案。 多项式时间算法 在本节中，我们给出 了 2上的 题的伪多项式时间算法 。 论文第一章，介绍了 2的定义， 2是由递归生成。本章利用 2次收缩 2上度为 2 的点，直到只有一条边为止。在收缩度为2 的点的同时，我们要记录如下的一些变量。 2 ( , , , )G V E c ， V 为顶点集， E 为边集， 为时延 集 ， c 为费用 集 。对于任意边 ( , )e x y 。有下面的定义： () 的子图，通过收缩度为 2 的点到边 ( , )e x y 得到 。 ( , , , , )S T e k 是 ()上 同时包括点 x 和 y 并且满足下列条件的最小费用 。这棵 的直径 不超过 。 上连接点 x 但是不连接点 度不超过 。 上连接点 y 但是不连接点 x 的最大时延路杭州电子科技大学硕士学位论文 10 长度不超过 。 上连接点 x 和点 y 的最大时延路 长度不超过 k 。( ( , , , , ) )C S T e k 是 这棵 的最小费用。 ( , , , )D T e 是 ()上两棵分别与点 x 和点 y 相连 并且满足下列条件的总费用和最小的 。 设这两棵 的直径分别为 12,，那么( , , , )D T e 中 12, 不超过 。连接点 x 但是不连接点 y 的最大时延路 的长度不超过