（计算机软件与理论专业论文）关于两不相交路径问题的研究.pdf

摘要 在本文中，我们研究了计算机网络通讯中一类重要问题，不相交路径问 题问题为：给出图g = ( k e ) 以及图中的两点s ，t ，我们要求从点s 到点t 的两条不相交路径( 点不相交或者边不相交) ，并且满足某个目标函数我们 研究了在不同的目标函数下，这些问题的复杂性，这些目标包括：m l n m a x ， m l n m m ，b a l a n c e d ，m i n s m n - m i n m a x ，m i n s u m - m i n m m ，m u l t l - o b j e c t w e ，c o n - s t r a i n e dm u l t l - o b j e c t i v e 对m i n m a x2 d p 问题，我们给出了，在d a g 上的解决该问题的f p t a s 算 法 对m i n m m2 d p 问题，我们证明了，四种版本的问题都是强n p 完全的 对b a l a n c e d2 d p 问题，我们证明其四种版本都是强n p 完全的，并且都不存 在常数近似度的近似算法而对于d a g 的情况，我们证明其为n p 完全的，并且 给出了伪多项式时间的算法 对m m s u m - m m m a x2 d p 问题，我们证明，对于无向图，该问题是n p 完全 的，并且存在近似度为2 的近似算法对有向图，该问题是强n p 完全的，存在近 似度为2 的近似算法，并且不存在近似度小于2 的近似算法，除非p = p 对于 d a g ，该问题是n p 完全的，并且存在f p t a s 对m m s u m - m l n m i n2 d p 问题，在d a g 的情况下，我们给出了一个快速的 多项式时间算法 对多目标优化2 d p 问题，我们证明对于d a g 的情况，存在f p t a s 算法 而对于带约束多目标优化2 d p 问题，在d a g 的情况下，存在多项式时间的 ( 1 + 0 t ，1 + p ) 近似算法同时我们还从一些角度分析，提出对般情况这两个问 题可能不存在f p t a s 算法 关键词：两不相交路径问题，n p 完全问题，强n p 完全问题，伪多项式时间算法 近似算法，f p t a s 中图分类号：t p 3 0 16 n l a b s t r a c t g i v e nag r a p ha n dt w od i s t m e tn o d e ssa n dt w ec o n s i d e rt h ep r o b l e mo ft i n d l n g t w od i s j o i n tp a t h sf r o m8t ots a t l s 研n gs o m eo b j e c t i v e w ec o n s i d e rs e v e no b j e c - r i v e s ，m i n m a x ，m m m i n ，b a l a n c e d ，m i n s u m - m m m a x ，m i n s u m - m i n m m ，m u l t i - o b j e c t l v ea n dc o n s t r a i n e dm u l t i - o b j e c t i v e f o rm l n m a x2 d pp r o b l e m ，w ew i l lg i v ea nf p t a sf o rt h i sp r o b l e mo nd a g s f o rm l n m m2 d pp r o b l e m ，w ew i l lp r o v et h a tt h ep r o b l e mi ss t r o n gn p c o m p l e t ef o rd i r e c t e da n du n d i r e c t e dg r a p h s ，a n df o re d g ed i s j o i n ta n dn o d ed i s - j o i a tp a t h s f o rb a l a n c e d2 d pp r o b l e m ，w ev a up r o v et h a tt h ep r o b l e ml sa l s os t r o n g n p - c o m p l e t ef o rd i r e c t e da n du n d i r e c t e dg r a p l l 8 ，a n df o re d g ed i s j o i n ta n dn o d e & s j o i n tp a t h s o nd a g s ，t h ep r o b l e mi sn p - e o m p l e t e w ew i l lg i v eap s e u d o - p o l y n o m m l - t i m ea l g o n t h mf o rt h i sp r o b l e mo nd a g s f o rm l n s u m - m m m a x2 d pp r o b l e m ，w ew i l lp r o v et h a tt h ep r o b l e mi sn p c o m p l e t ea n da2 - a p p r o x i m a t i o na l g o r i t h me x i s t sf o ru n d i r e c t e df a p h 8 f o rd i - r e c t e dg r a p h s ，t h ep r o b l e mi ss t r o n gn p - c o m p l e t e ，a2 一a p p r o m m a t i o na l g o r i t h m e x i s t sa n dt h e r ei sn oe - a p p r o x i m a t i o na l g o r i t h mf o ra l lc o n s t a n t 0 ，算 法都可以给出一个解，其目标函数值不会超过最优解的1 + e 倍，并且其运行时间 为问题规模以及l c 的多项式大小 m i n m i n2 d pp r o b l e m ： 输入：图g = ( v 司，源点s 和汇点t ，以及定义在边集上的非负整数 函数，：e h n 输出从点8 到点t 的两条不相交路径，使得这两条路径中权值较小的 一条路径的权值最小化 这个问题最早由y a n g 等人在【3 5 】中提出，他们给出了对m l n m m2 d p 问题 比较详细的分析他们证明了对于图是有向或者无向，路径是边不相交或者点不 相交，这四种版本的m l n m i n2 d p 问题的判定问题都是强n p 完全的，并且证明 了这四个问题都不存在常数近似度的近似算法，除非p = n p 而对于d a g 的 情况，作者给出了多项式时间的算法，这个算法也是基于p e r l & s h i l o a s h 算法 但是，在证明无向图上边不相交路径m m m m2 d p 问题的判定问题是强n p 完全的时候，作者用线图的方法，将无向图边不相交路径m m m i n2 d p 问题规 约到无向图点不相交路径m i n m i n2 d p 问题，从而指出由无向图点不相交路 径m m m m2 d p 问题的判定问题是强n p 完全的可以得到无向图边不相交路径 m m m l n2 d p 问题的判定问题是强n p 完全的显然作者给出了一个错误的规约 我们在本文中指出作者的错误并且给出了一个正确的证明 b a l a n c e d2 d pp r o b l e m ： 输入图g = ( k e ) ，源点s 和汇点t ，以及定义在边集上的非负整数 函数，：e h n 输出从点8 到点t 的两条不相交路径，使得这两条路径中的权值之差 的绝对值最小化 该问题由我们在本文中提出，并且我们对这个问题进行了详细的讨论首先 我们证明，无论图是有向图还是无向图，无论所求的路径是点不相交的路径还是 第一章绪论3 边不相交的路径，b a l a n c e d2 d p 问题的判定问题都是强n p 完全的，并且不存在 常数近似度的近似算法，除非p = p 其次，对于特殊的情况，图为d a g ，我们 证明其上的b a l a n c e d2 d p 问题的判定问题是n p 完全的，同时我们也给出一个 伪多项式时间的算法 m i n s u m - m i n m a x2 d pp r o b l e m 输入：图g = ( k e ) ，源点s 和汇点t ，以及定义在边集上的非负整数 函数，：e hn 输出：从点8 到点t 的两条不相交路径，使得首先这两条路径中的权值 之和是最小的，并且在所有权值之和最小的两不相交路径中，其权值 较大的路径的权值最小 m i n s u m - b a l a n c e d2 d pp r o b l e m ： 输入：图g = ( k e ) ，源点s 和汇点t ，以及定义在边集上的非负整数 函数，：e h n 输出从点8 到点t 的两条不相交路径，使得首先这两条路径中的权值 之和是最小的，并且在所有权值之和最小的两不相交路径中，其两条 路径的权值之差的绝对值最小 这两个问题由我们在本文中提出我们首先证明了这两个问题的等价性然 后对前者，我们详细讨论了其在几种不同的图上的复杂性以及算法在无向图上， 这个问题的判定问题是n p 完全的，我们给出了对于这个问题的近似度为2 的简 单的近似算法在有向图上，我们证明这个问题的判定问题是强n p 完全的，存在 近似度为2 的近似算法，但是不存在近似度小于2 的近似算法，除非p = n p 最 后对于d a g 的情况，我们证明这个问题的判定问题是n p 完全的，并且给出一个 伪多项式时问的算法，同时给出了解决该问题的f p t a s m i n s u m - m i n m i n2 d pp r o b l e m ： 输入：图g = e ) ，源点s 和汇点t ，以及定义在边集上的非负整数 函数，：e h n 输出：从点s 到点的两条不相交路径，使得首先这两条路径中的权值 之和是最小的，并且在所有权值之和最小的两不相交路径中，其权值 较小的路径的权值最小 第一章绪论 4 这个问题最早由y a n g 【3 4 】提出，并且对这个问题进行了讨论他证明了 在有向图上，对于点不相交和边不相交两种情况，这个问题的判定问题均为 强n p 完全的，并且证明了不存在常数近似度的近似算法，除非p = p 对 于d a g 的情况，y a n g 给出了一个多项式时间的算法，这个算法是通过证明 d a g 上m m s u m - m i n m m2 d p 问题的最优解和另一个问题d a g 上n o r m a l i z e d 口+ 一m i n - s u m2 d p 问题在o = 而m ，m = 。f ，( e ) + 1 时的最优解相同，然后 从蝎上n o r m a h z e do t + 一m i n - s u m2 d p 问题的多项式时间算法【3 6 】求出原问 题的最优解 我们注意到，在求d a g 上n o r m a l i z e do + 一m i n s u m2 d p 问题的解时，需 要对各边的权值乘以a 这个系数，而由于口= i 干丽m ，m = e e e ，( e ) + 1 ，这 个算法需要使用大量的乘法和除法运算而且问题规约到d a g 上n o r m a l i z e d a + 一m i n - s u m2 d p 问题后使得对原问题的求解不直观，并且这个算法很难推广 到求k 2 条不相交路径的情况在本文中，我们将给出一个清晰的d a g 上 m i n s u m - m i n m i n2 d p 问题的多项式时间算法，该算法无须乘法除法运算，时间 复杂度小，并且很容易推广到七 2 的情况 多目标优化2 d p 问题 输入：图g = ( k e ) ，源点s 和汇点t ，以及定义在边集上的两个非负 整数函数c 1 ，c 2 ：e n 输出从点s 到点t 的两条不相交路径的集合，集合中的两不相交路径 满足不存在某个两不相交路径使得后者在两个权值函数下的值都比 前者的小 我们首先介绍一类问题多目标优化问题，这类问题是研究优化问题中的一 个重要的分支对这类问题求解近似解：e 近似p a r e t o 曲线，p a p a d m n t n o u 和 y a n n a k a k i s 【2 5 】给出了充要条件 对于在d a g 上的特殊情况，我们给出了求解多目标优化2 d p 问题的e 近似 p a t e t o 曲线的多项式时间算法 对于该问题的另一个变种带约束多目标优化2 d p 问题 带约束多目标优化2 d p 问题： 输入：图g = ( v e ) ，源点s 和汇点t ，以及定义在边集上的两个非负 整数函数c l ，c 2 ：e n ，一个非负整数 输出从点s 到点t 的两条不相交路径，满足这两不相交路径在c 1 下 的权值之和小于等于k ，并且对所有在c 1 下的权值之和小于等于耳 的两不相交路径中，输出的解在岛下的权值之和最小 第一章绪论5 对这类带约束的多目标优化问题，有一类近似算法被称为( 1 + o t ，1 + p ) 近似 算法，该算法返回的解会违反约束条件，但是不会超过约束条件的1 + a 倍，而目 标函数不会超过最优解的1 + 口倍我们首先证明对多目标优化问题在多项式时 间求解7 近似p a r e t o 曲线和对相应的带约束多目标优化问题在多项式时间求 解( 1 + 7 1 近似解是等价的 利用以上的结论和我们给出的多项式时间求解d a g 上多目标优化2 d p 问 题的7 近似p a r e t o 曲线，我们可以得到对d a g 上带约束多目标优化2 d p 问题 的多项式时间求解( r + 7 ) 近似解的近似算法 而对于一般图上的带约束多目标优化2 d p 问题，我们给出一些负面的结论， 即可能不存在求解该问题( 1 + 1 + 卢) 近似解的多项式时间算法 对前五种目标函数下的问题以及相应的结论，我们总结在下表中 第一章绪论6 姆凄g秘姆掣谣聪圈厦卜鞲叮熏旧艘目=量=-mns口_暑xb昌口h窆-ns目=p9。星rb口_【苫口量苫u1窆苌【1【僻 燃 燃 琳 r 一 蜮 燃 ，一 c ，) 色 厘 瓣包 备 燃 窖 燃 匦 臣 弧 帽 高 撅 匾 柑 厘 臀 皇 厘 献 幢 鲁 愉 姑 譬 幅 铎 蚺 柑 匣 雷 韬 丞 皇 性 忙 二土 馨 柑 删 蚺 幛 根 硝剞 谁 假 a _ 山 z z 荟撼蜮 薹薹 蜮 圣 娜 羹董 揖黎出 鉴篱曩 娜一 圣 墨 z 蚶忙燃 岂 z 棣鼍 g 盈 蝈一 蚓 匝 萨星 g 葛g 叵 毯：i 型i 警墨窜乏 忙 蛸毒 艚翼尘 舆“ 删纂钆 氓誊幕 鉴蓬蓬z 忙燃皇撵簧 璃恃琳 骥陡趟黧悟趟穗雉k - 斟穗k - 燃 蜮 矗 燃 = 蚓 琳 包 枷 g 墨 团 剞 张 警叁 蚓 g 厘根 山 求 山z蚓 采 z 憩删餐钆 型 疆 耋蓬蔫 蓍霾瑙* 燃 山 山 口 食 山 山 山 门 苫 口 口 口誉 鹊 鹊 一 皇 蕾 基专 皇 窆 皇 冒 暑 量昌 名 卣 暑 岂 磊 富 宝 第二章背景知识 在这章中，我们对整篇文章中将涉及到的一些基础知识作简要介绍对于更 加深入的知识，我们将列出一些专著以供参考 2 1 图论相关知识 图论是组合数学中最基础的分支之一，也是计算机科学的基础之一计算机 科学的许多问题都可以归结到图论问题，最显著的就是计算机网络问题在这节 中我们简单介绍图上的一些定义以及一些重要的结论这些内容都涵盖在许多图 论的基础教材中，可以参考【3 ，4 ，8 ，3 3 图是一个二元组g = ( k e ) ，其中y 称为顶点集，e 称为边集图可以按照 边的性质分为无向图和有向图在无向图中，边集e 中的元素是形如 珏，口) 的集 合，其中1 1 , ，口v 而在有向图中，边集e 中的元素是形如( 钍，t ，) 的有序对，其中 t t 口v 如果集合e 是多重集，即在e 中可以有重复的元素，那么这些重复的元素被 称为重边如果边 ，口) ( 或者边( u ，口) ) 中让= t ，这种边被称为自环一个没有 自环和重边的图被称为简单图本文中提到的图如果没有特别说明均指简单图 一条边 “， ) ( 或者边( “， ) ) 的两点称为这条边的端点，这两点被这条边连 接，这两点称为相邻顶点和某点相邻的点的数目称为这个点的度数对有向边 e = ( u ，口) 称e 离开缸进入 ，有时也称牡为起点而 为终点两条有公共端点的 无向或者有向边被称为相邻边有向图中，某点的出度是从这点离开的边的数目， 而入度是进入该点的边的数目 图g 的线图g ，是将g 中的边e 作为g 的顶点对无向图，g ，中的两点 ，钳之间有边当且仅当e ，e ，在g 中相邻而对有向图，g ，中的两点，咐之间 有边( ，岵) 当且仅当在g 中e 的终点是e ，的起点 图g 中的路径是一个序列, 0 1 ，e 1 ，v 2 ，e 2 ，e t l ，z l ，其中e l = “，v t + 1 ) ， 1s ；n ，这条路径的路径长度为n ，也就是其中边的数目两点”l ， o n + l 称为路 径的端点如果路径中的边是有向边，满足e i = ( v z ，仉+ - ) ，那么这条路径称为有 向路径， 1 ，+ 1 分别称为路径的起点和终点在有向路径上的相邻两点中，点地 7 第二章背景知识 8 称为点1 的前驱，1 l n 路径序列中的点称为被这条路径经过如果一条 路径满足具经过的点互不相同，那么这样的路径称为简单路径本文中如无特殊 说明，路径皆指简单路径 给出图g = ( k e ) ，图中两点8 ，t ，图的边权函数c ：e n ，要求求出从点8 到点t 的权值最小的路径这个问题称为最短路径问题最短路径问题有快速的 算法求解，可以参考1 7 1 两条路径被称为边不相交路径( 点不相交路径) ，如果这两条路径所经过的 边( 点) 互不相同 如果路径序列的起点和终点重合，那么这样的路径称为圈有向路径的起点 和终点重合形成有向圈如果一个圈经过的点互不相同，那么这样的圈称为简单 圈圈的长度为其序列中边的数目 如果一条路径经过图中所有顶点一次且仅一次，那么这条路径称为哈密尔顿 路如果一个圈经过图中所有顶点一次且仅一次，那么这样的圈称为哈密尔顿圈 存在哈密尔顿圈的图称为哈密尔顿图 对于有向图，如果其中不含有有向圈，那么这样的图称为有向无圈图，简称 d a g 对于d a g 有一个重要的性质，就是可以拓扑捧序 有向图g ；( k e ) 的拓扑排序是对图中顶点的一个赋值，：v 一 1 ，2 ，i v l ，满足对于任意的q ，屿k ，) ，( ) ，并且对于 任意的e = 以，) e 都有芦似) ，( 码) 有向图存在拓扑排序当且仅当该图是d a g k n u t h 最早给出了d a g 拓扑排序的线性时间算法，可以参考【2 0 ，7 】 图g ，= ( ，e 7 ) 称为图g = ( k e ) 的子图，如果矿sk f e 图g ，= ( y 7 ，e 7 ) 称为图g = ( k e ) 的导出子图，如果v f = “札，口) e u ， - ，) ( 对有向图f = ( u ， ) e i u ，口) ) 一个无向图被称为树，如果这个图是连通的并且没有圈一个图t 被称为图 g 的生成树，如果t 是g 的导出子图并且t 是树 给出一个图g = ( k e ) ，以及图的边权函数c ：e n ，要求求出图的边权 之和最小的生成树，该问题称为最小生成树问题最小生成树问题存在快速的算 法，可以参考f 7 1 2 2 复杂性相关知识 问题 本文中，我们讨论两类问题，一类问题称作判定问题，另一类问题称作优化 判定问题是这样的问题，给出问题的任意实例j ，要求给出的回答是“是”或 q 绷 鳓糟 第二章背景知识 9 者“否”判定问题多为判断存在性的问题，比如h a m i l t o n 圈问题，就是给定一个 图，判断图中是否存在哈密尔顿圈 在给出优化问题的定义前，我们先给出搜索问题的定义 定义在关系r = ( j ，y ) l i z ，y s o l ( 1 ) 上的搜索问题是给出一个问题 的实例j ，要求给出这个实例的一个解对一个实例，其解的集合8 0 l ( i ) = y ic x ，y ) r ) 优化问题是在搜索问题的基础上定义了解的权值函数，并且要求求出权值达 到极值的解 优化问题是一个四元组口，s o l ，c ，g o a l ) 其中z 是实例集合，对于任意的 实例i 互s d ( x ) 是其解的集合c ：工s o l n 为权值函数对任意的 解y s o t ( i ) ，权函数c ( x ，y ) 映射到一个非负整数g o a l m i n ，m a x 如果 g o a l = m a x ，优化问题是要对于任意一个实例i z ，要求求出y s o l ( x ) ，满 足对于任意的矿s o l ( i ) 有c ( x ，矿) c ( x ，可) 如果g o a l = n f m ，优化问题是要 对于任意一个实例i z ，要求求出y s o l ( x ) ，满足对于任意的矿s o l ( x ) 有 c ( x ，矿) c ( i ，y ) 比如最小生成树问题，实例集z 就是所有的连通图，s o l ( n 是图的所有生成 树的集合，c 是权值函数，g o a l = r a i n 对一个问题的实例，我们为了能够在计算机上进行处理，必须对问题的实例 进行编码通常，我们使用二进制对实例进行编码 对于某个问题口，如果存在一个算法一4 对于该问题的任意实例i ，4 ( j ) 都给 出对这个实例的正确解，那么称这个算法解决问题d 如果存在一个多项式函数 p ，并且对于任意的实例，这个算法所花费的时间都是o ( p ( i x l ) ) ，其中i 卅为该实 例的二进制编码长度，那么称这个算法一4 为解决问题d 的多项式时间算法而 问题口称为多项式时间可解决的 所有多项式时闻可解决的判定问题所组成的集合称为p 类 对判定问题口，如果存在一个多项式时间的算法一4 和一个多项式函数 p 满足对于口的任意实例j ，如果实例j - 的解为“是”，那么存在证据y 满足 i y l = o ( p ( 1 1 1 ) ) 有a c i ，y ) 返回“是”，如果实例，的解为“否”，那么对任意的证据 y 满足l y l = o ( p ( 1 i i ) ) 都有a ( i ，y ) 返回“否”，那么称问题d 是多项式时间可验 证的算法一4 称为问题口的多项式时间验证算法 所有多项式时间可以验证的判定问题所组成的集合称为n p 类 在复杂性理论中，通常用规约来衡量两个问题之间的相对难易程度对两个 判定问题z ，l ，现，如果说d l 可以多项式时问规约到现，记做口l p 伤，那么 存在从问题d l 的实例集五到问题z 2 的实例集五的多项式时间可计算的函数 ，：五一乃，满足，对任意的d l 的实例 ， 的解为“是”当且仅当1 2 = f ( 1 1 ) 的 缓 赫 第二章背景知识 1 0 解为“是” 对于其他形式的规约以及性质可以参考相关复杂性的著作【9 ，2 4 ，2 9 】 对判定问题d ，如果d p 并且对任意的判定问题n p 都有 p 口，那么判定问题口被称为p 完全的 自从c o o k1 9 7 1 年f 6 】证明存在p 完全问题以来，大量的n p 完全问题被 证明在这里我们给出本文中需要用到的一些n p 完全问题，对于其他的问题以 及这些问题p 完全性的证明可以参考【1 2 1 3 s a t 问题 输入：布尔变量的集合x = 茁1 ， 以及字句的集合c = c 1 ， ，每个字句至多含有三个文字 判断是否存在对布尔变量的赋值：x 一 t r u e ，f a l s e ，使得每个 子句都满足，也就是使得对每个子句岛中的三个文字，至少有一个在 此赋值下取值为t r u e m a x - 3 s a t f 司题 输入：布尔变量的集合x = z 1 ，) 以及字句的集合c = c l ， ，每个字句至多含有三个文字正整数k s m 判断是否存在对布尔变量的赋值：x 一 t r u e ，f a l s e ，使得满足 的子句个数大于等于k m a x - 2 s a t 问题 输入：布尔变量的集合x = z 1 ，) 以及字句的集合c = c l ，) ，每个字句含有两个文字正整数k m 判断是否存在对布尔变量的赋值：x 一 t r u e ，f a l s e ，使得满足 的子旬个数大于等于k h a m i l t o n 路问题 输入：图g = ( k e ) ，以及两点札，仉 判断：是否存在一条g 中的哈密尔顿路，并且这条哈密尔顿路的两个 端点分别为u ， 集合划分问题 输入：集合s = s l ，s n ，以及权函数c s n 戮 - 嬲 第二章背景知识 1 1 判断是否存在一个集合s 满足。s ，e ( s ) = 。c ( 8 ) 子集和问题 输入集合s = s l ，) ，权函数c ：s n ，以及正整数耳 判断是否存在一个集合s 满足，伊c ( s ) = k 背包口j 题 输入集合s = 8 1 ， ，权函数w ：s n ，c ：s 卜n ，正整数 r k 判断：是否存在集合f s 满足。w ( s ) r ，。c ( 8 ) k 对于某个问题口，如果存在一个算法一4 ，以及一个多项式函数p ，满足：对于 该问题的任意实例i ，a ( z ) 都给出对这个实例的正确解，并且算法所花费的时间 是o ( p ( i i ，m a x ( 功) ，其中i j l 为该实例的二进制编码长度，而m a x ( ) 为实例，中 数值的最大值那么称这个算法a 为解决问题d 的伪多项式时问算法 伪多项式时间算法和下面给出的强n p 完全的定义有着很大的联系首先， 给定问题d 以及多项式p ，我们定义问题岛为问题口的子问题，满足问题的 实例集耳= x l i 五m a x ( ) p ( i i i ) 也就是约束问题口的实例，使得其中的 数值都不超过其编码长度的某个多项式 一个问题口被称为是强n p 完全的，如果这个问题是属于n p 的，并且存在 一个多项式p ，使得z ) 口是n p 完全的 如果一个问题是强n p 完全的，那么这个问题不存在伪多项式时间的算法， 除非p = n p 一个优化问题伍，s o l ，c ，g o a l ) 被称为是n p 优化问题，如果( i ) 存在多项式 p 满足对于任意的实例i 工对于任意的y s o l ( i ) 都有m y = 0 ( p ( 1 邛) ( i i ) 存在多项式时间算法，满足对任意的y 且m y = o c o ( i z t ) ) ，该算法可以判定是否 y s o l ( t ) ( n i ) 函数c 是多项式时间可以求解的 问题r 可以图灵规约到问题岛，记做乃 t7 毛，那么存在多项式时间算法 一4 ，假设存在解决问题岛的算法，对于任意的问题r 的实例 ，算法一4 m ) 返 回对该实例的解，并且在算法4 的计算过程中可以调用算法爿作为子过程，而 每次调用只记为一个单位时间 优化问题p 被称为n p 难的，如果对于任意的判定问题尹7e p ，都有 少 0 ，一个多项式时间的 算法一4 被称为( 1 + e ) 近似度的近似算法，如果对于任意的实例i ，y = a ( i ) s o l ( i ) 为算法返回的解，那么如果g o a l = m a x 则c ( x ，g ) c ( x ，o p t ) ( 1 + e ) ，如 果g o a l = m i n 则c ( i ，y ) ( 1 + e ) c ( j ，o p t ) ，其中o p t s o l ( i ) 为该实例的最优 解 一个算法被称为解决某优化问题p 的p t a s ( p o l y n o m i a l - t i m ea p p r o x - i m a t i o ns c h e m e s ) ，如果对任意的问题的实例j 以及参数厶算法返回的解是一 个( 1 + e ) 近似度的解，并且算法运行时间为实例规模的多项式大小 一个算法被称为解决某优化问题p 的f p t a s ( e 、d lp 0 1 5 r n o m i a l - t i m e a p p r o x i m a t i o ns c h e m e s ) ，如果对任意的问题的实例，以及参数e ，算法返回 的解是一个( 1 + e ) 近似度的解，并且算法运行时间为实例规模和l e 的多项式大 小 对于n p 优化问题，以及于其相关的复杂性类的深入的介绍，可以参考【2 】 但是，不同的n p 难优化问题可以设计出的近似算法的近似度不一定相同， 有些问题有很好的近似算法，比如背包问题有f p t a s 算法f 1 7 ，m a x - 3 s a t 存 在8 7 近似度的近似算法【1 9 】而有些问题不存在好的近似算法一般来说，要证 明一个问题的不可近似性，我们需要从某个难的问题规约到要证明的问题早期， 是利用类似证明n p 完全性的规约方法，从而证明在p n p 的假设下，达到某 第二章背景知识 个近似度是难的直至1 9 9 2 年，计算机科学家发现了n p 问题的另一种表述模型 p c p ( p r o b a b f l m t mp r o o fs y s t e m ) 系统，至此，大量的不可近似的结论被证明对 于p c p 的发展以及在不可近似性中的应用，可以参考c a i 等人【5 】的综述，以及 文章中的参考文献对于不同问题的近似算法以及不可近似的结果，可以参考 c r e s c e n z i 和k a n n 给出的网站： h t t p ：州n a d a k t h s e t h e o r y p r o b l e m h s t h t m l 笏 绷 第三章m i n m a x2 d p 问题 3 1问题描述 “等人在【2 1 i 中提出了m i n m a x2 d p 问题问题定义如下： 定义3 1 ( m i n m a x2 d p ) 给定图g = ( k e ) 和图中的两点：源点s 和汇点t ，以 及边权函数，：e n ，其中n 是非负整数的集合，要求求出从8 到t 的两条不 相交的路径，并且使得这两条路径中权最大的路径的权最小化，其中路径的权定 义为其上所有边的权之和 在这个定义中，图可以是无向图或者有向图，不相交路径可以是点不相交的 路径或者边不相交的路径，这样m m m a x2 d p 问题就可以衍生出4 个版本的定义 在【2 1 1 中，l l 等人证明对于一般图，m i n m a x2 d p 问题的4 个版本的判定问题 均为强n p 完全的，对于有向图，m m m a x2 d p 问题存在近似度为2 的近似算法， 但是不存在近似度小于2 的近似算法，除非p = p 而对于d a g 上的m l n m a x 2 d p 问题，在【1 8 】中已经证明其判定问题为n p 完全的，而在【2 1 】中l l 等人给 出了伪多项式时间的算法，这个算法利用了p e r l 和s h i l o a c h 在【2 8 】中给出的在 d a g 中寻找点不相交路径的多项式时间算法 利用l i 等人的伪多项式时间算法，我们可以设计出d a g 上m m m a x2 d p 问题的有效的近似算法 3 2d a g 上m i n m a x2 d p 问题的f p t a s 算法 为了使算法的描述更加完整，我们在这里简单介绍p e r l 和s h i l o a c h 【2 8 】中设 计的在d a g 中寻找点不相交路径的算法，以及l 1 等人【2 1 】给出的伪多项式时间 算法 3 2 1p e r l s h i l o a c h 算法 p e r l 和s h d o a c h 【2 8 】给出的算法起源于对不相交路径问题( d i s j o i n tp a t h s p r o b l e m ) 的研究问题定义如下： 1 4 第三章m m m a x2 d p 问题 定义3 2 ( d i s j o i n tp a t h sp r o b l e m ) 给定图g = ( v 司和图中的k22 对点 ( 8 1 ，t 1 ) ，( 8 k ，如) ，问是否有从8 。到t s ，1 i k ，的七条不相交的路径 如果给定的图g 是有向图，则不论不相交的路径是点不相交还是边不相交， 这个问题被证明为n p 完全的1 1 1 ，即使在k = 2 的情况 p e r l & s l u l o a c h 算法其实是一个多项式时间的规约，将问题从在g 上求k 条 不相交的路径的问题规约到在g ，上求一条路径我们下面给出k = 2 时的构造 因为g 是一个d a g ，g 存在一个拓扑排序，假设”l ，7 3 2 ，为g 的一个拓扑 排序，即满足对于任意的边他，廿，) 都有o 3 ，构造一个新图g ，= ( ，) 如下： v 7 = ( 仇，吻) l 仇，码k l j = ( ( 仇，) ，( 仇，) ) i ( 码，v k ) e ，j 。) u i f ( v , ，码) ，( 仉，) ) i ( 仇，仇) e ， j ) ( 3 1 ) 对任意的七只要将g ，的顶点改为k 元组即可 定理3 1 ( 2 8 1 ) g 中存在从8 1 到t l 以及8 2 到屯的两条点不相交的路径，当且 仅当在g ，中存在从( 8 - ，8 2 ) 到( t - ，t 2 ) 的路径 这样要解决d i n j o i n tp a t h sp r o b l e m 只须在g ，上判断两个顶点之间的 连通性即可，可以在新图g ，规模的线性时间完成而注意到当k = 2 时 l v i = o ( i v l 2 ) ，i f i = o ( i v f l ej ) = o ( i v l 3 ) ，d i s j o i n tp a t h sp r o b l e m 可以在 o ( i v l 3 1 时间内解决 下面我们把( 3 1 ) 中前面一个集合的边称为横向边，后面一个集合的边称为 纵向边从图g ，的构造可以看出，如果图g ，的对应两点间有一条路径，则原图 g 中的两条点不相交的路径分别对应图g ，的路径中横向边和纵向边的集合，反 之亦然 3 2 2 l a b e l i n g 方法 对于d a g 上的m m m a x2 d p 问题，l l 等人给出了伪多项式时问的算法该 算法首先使用p e r l & s h i l o a c h 算法构造图g ，但有所不同的是，在构造图g ，的顶 点时须加入点( 8 ，s ) ，( t ，t ) 以及相应的边，因为在m m m a x2 d p 问题中两条路径的 源点和汇点都重合图g ，上的边( 似，码) ，以，口k ) ) 和边( ( 码，仇) ，( 讥，仉) ) 的权值与 原图对应边( 屿，仇) 的权值相同接下来对图g ，使用标注法( 1 a b e h n g ) 一个标注 是一个三元组( x ，e ( 似，) ，( a ，6 ) ) ) ，其中x 和y 均是非负整数，而似，码) 是g ， 中的点，( 口，b ) 是一个二维数组的下标，在下文中会给出定义算法在执行的过程 霭绷_ 第三章m i n m a x2 d p 问题1 6 中会对g ，中的每个点( 讥，研) 求出一个标注集合，一个标注( x ，k ( 似，码) ，( a ，6 ) ) ) 在这个集合中当且仅当在g ，中存在一条从点( s ，s ) 到点饥，研) 的路径，并且这条 路径上所有横向边的权值之和等于x ，所有纵向边的权值之和等于y ，在这条路 径上点( 讥，q ) 的前驱为点以，t 。) 最后在点( t ，t ) 的所有标注中选出m a x x ，y 最小的，即是原问题的解 因为g 是d a g g ，也是d a g 所以求标注集合的过程可以按照拓扑序对每 个点依次求得但是对每个点，标注集合的大小由到这个点的不同权值路径的数 量决定，其上界是d ( 驴) ，l = ( f y l 一1 ) m a x e f ，( b ) ，所以该算法是伪多项式时 间算法 3 2 3d a g 上m i n m a x2 d p 问题的f p t a s 算法 本节，利用以上的伪多项式时间算法，我们给出求解刚旧上的m i n m a x2 d p 问题的f p t a s 算法在这里，我们假设图g 中所有边的权值都是正整数 我们注意到影响到伪多项式时间算法的关键在于其时间复杂度中含有l 这 个长度值，如果我们可以压缩这个值，但又不会使解偏离最优解太多，就可以得到 很好的近似算法 算法的思路大致是，将工分割成 1 0 9 1 + 6 l j + 1 个区间，每个区间【f i ，f i + l 】的 相对大小为1 + d ，即簪= 1 + 6 如果有很多值落在同一个区间中，我们只需要 保留一个值，产生的相对误差是1 + 6 ，但是时间可以指数地减少 下面给出具体算法，假设输入图g 已经是拓扑排序好的，并且点8 ，t 分别是 第一个和最后一个点，否则可以将拓扑排序中在点8 前和在点t 后面的点以及它 们的相邻的边删除，因为从8 到t 的路径不可能通过这些点对于每个点似，q ) ， 用二维数组l a b e l 。，) 【记录其标注的值，标注( x ，( ( 地，饥) ，( n ，6 ) ) ) 被记录 在l a b e l ( 鸬) 【u 0 9 l “x j + 1 1 0 9 l + 5 y j + 1 】里，并且一小数组单元最多只记录一 个标注，没有记录标注的l o 捌单元存放空值n u l l 对每个点似，) ，用集合 丑 ，) 表示其所有非空l a b e l 单元的下标，标注三元组最后一元( a ，6 ) 即是这个集 合中的元素用这种方法可以在算法结束时通过回溯这些信息将路径构造出来 算法描述如下 f p t a s - d a g m i n m a x - 2 d p ( g = ( ke ) ，s ，f ，只e ) lc o n s t r u c tg ，= ( 矿，) ，s u c h t h a t v ； 池，吩) h ，码k l j u “s ，8 ) ，( t ，砷，a n d e j = ( 饥，码) ，她，v k ) ) l c v ，仇) e ，j l u ( 他，码) ，( 饥，码) ) i h ，仇) e ，t s ， 2 6 = ( 1 + e ) 赤一1 ， 3 i m t u d m a t r l o 瞄l a b e l ( q ，q ) 【叫旧= n u l l ，1 s l ，i y i ，1 s 南，l 【l o g l + d l j + 1 ， f ( q ) ；0 ，1s 。，j i y i ， s 。) _ ( 1 ，1 ) ) ， 第三章m i n m a x2 d p 问题 1 7 l a b e l ) 【1 】【1 l = ( o ，0 ，n u l l ) ； f o r t - 1 t o l v ld o f o rj 1 t o i v id o f o re a c h ( 帆，砷，他，码) ) e f o re a c h ，b ) 慨( x ，e ) b et h el a b e li nl a b e l ( v 。 【n 】【6 】； l e t 一= l l 0 9 1 + 6 ( x + ，( ( u ，吩) ) ) j + l ； i fl a b e l ( m ，q ) f l b l = = n u l l t h e n l a b e l ( q ) 【n ，】 b l = ( x + ，( ( u ，码) ) ，y ，( 他，) ，( o 6 ) ) ) ， 饥，q ) = 印 u ( 一，6 ) ， f o re a c h ( ( u ，码) ，( 仉，码) ) e f o re a c h ( 口，b ) 厶q ，q 慨噬，k ) b et h el a b e li nl a b e l ( 。，q i n 】【6 l ， l e t6 ，= l l o g l + 6 ( y + ，( ( u ，佻) ) ) j + 1 ； ”l a b e l