（運籌學與控制論專業(yè)論文）賦權(quán)哈明距離下若干網(wǎng)絡逆問題的研究.pdf

摘要 摘要 網(wǎng)絡優(yōu)化問題是一類重要的組合優(yōu)化問題，它要求找到給定問題的最優(yōu)解 隨著社會生產(chǎn)的發(fā)展，又產(chǎn)生一些所謂的網(wǎng)絡優(yōu)化逆問題，在這些問題中，先 給定一個可行解，但就目前的參數(shù)而言，它并不是最優(yōu)解，我們需要通過盡可 能少的修改相應的參數(shù)從而使得所給的可行解成為最優(yōu)解隨著計算機科學、管 理科學和現(xiàn)代化生產(chǎn)技術等的日益發(fā)展，這類問題與日俱增，越來越受到運籌 學、應用數(shù)學、計算機科學及管理科學等諸多學科的高度重視本文就是針對這 些新問題，主要對哈明距離下的若干網(wǎng)絡逆問題進行了研究全文共分為四章， 第一章主要介紹與組合優(yōu)化問題及逆問題相關的一些概念和預備知識接著我們 分別研究了不同問題的若干模型 第二章研究的是賦權(quán)哈明距離下最大流逆問題：對給定的連通有向網(wǎng) 絡( k a ，c ) ，每條弧都有一個容量改造費用，令廣。是網(wǎng)絡的一個可行流，如 何改變網(wǎng)絡弧上的容量使得廠。成為新容量下的最大流，且在哈明距離下產(chǎn)生 的改造費用最小我們總共研究了四種模型；對于總和型，我們把問題轉(zhuǎn)化為 求解剩余網(wǎng)絡的一個受限制割，從而給出了時間復雜性為0 ( 億3 ) 的多項式時間 算法對于瓶頸型，我們通過把問題轉(zhuǎn)化為求解剩余網(wǎng)絡的一個受限制瓶頸 割問題，從而給出了時間復雜性為o ( m + 禮1 0 9 禮) 的多項式時間算法對于兩 種混合型，我們利用二分法思想，結(jié)合前面的算法，分別給出了時間復雜性 為d ( 凡3 1 0 9 m ) 和d ( 死3 ) 的多項式時間算法 第三章研究的是賦權(quán)哈明距離下最小一最大支撐樹逆問題：對給定的連通 圖g ：( v e ，c ) ，每條邊都有一個長度改造費用，令p 是圖g 的一個支撐樹， 如何改變圖上邊的長度使得p 成為新長度下的最小一最大支撐樹，且在哈明距 離下產(chǎn)生的改造費用最小我們總共研究了四種模型：對于總和型，我們先給 出了最優(yōu)解的可能取值，然后通過求解圖的受限最小割問題給出了時間復雜性 為o ( n 4 1 的多項式時間算法對于瓶頸型，我們通過求解圖的受限最小瓶頸割問 題給出了時間復雜性為d f n 5 1 的多項式時間算法對于兩種混合型，我們利用二 分法的思想，結(jié)合前面的算法，分別給出了時間復雜性為d ( n 5 ) 和d ( 禮t ) 的多項 式時間算法 第四章研究的是賦權(quán)哈明距離下最小割逆問題：對給定的連通有向 網(wǎng)絡( va ，c ) ，每條弧都有一個容量改造費用，令f x o ，丈u - 是網(wǎng)絡的一 個s 一碚0 ，如何改變網(wǎng)絡弧上的容量使得_ f x o ，x ”) 成為新容量下的最小割，且 摘要 在哈明距離下產(chǎn)生的改造費用最小我們研究了兩種模型：對于總和型，我們利 用背包問題的實例的多項式歸約，證明了該問題是n p 一難的對于瓶頸型，通過 利用最大流一最小割和哈明距離的性質(zhì)，我們給出了時間復雜性為d ( m 釓3 ) 的 多項式時間算法 關鍵詞：網(wǎng)絡優(yōu)化，逆問題，最大流，最小一最大支撐樹，最小割，多項式時 間算法 一一 a b s t r a c t a b s t r a c t n e t w o r ko p t i m i z a t i o ni so n ei m p o r t a n tb r a n c ho ft h ec o m b i n a t o r i a lo p t i m i z a t i o n ， t h eg o a li st of i n da l lo p t i m a ls o l u t i o no f t h eg i v e np r o b l e m a st h es o c i e t ya d v a n c e s ，t h e i n v e r s ep r o b l e m so fn e t w o r ko p t i m i z a t i o na r i s e i nt h e s ep r o b l e m s ，af e a s i b l es o l u t i o n i sg i v e nw h i c hi sn o to p t i m a lu n d e rt h ec u r r e n tp a r a m e t e rv a l u e s a n di ti sr e q u i r e dt o m o d i f ys o m ep a r a m e t e r sw i t hm i n i m u mm o d i f i c a t i o nc o s ts u c ht h a tt h eg i v e nf e a s i b l e s o l u t i o nf o r m sa no p t i m a ls o l u t i o n t h i si n v e r s ep r o b l e mb e c o m e si n c r e a s i n g l yc o n s p i c u o u s ，a t t r a c t i n gm o r ea n d m o r ea t t e n t i o nf r o mm a n y d i s c i p l i n e s ，s u c ha so p e r a t i o n s r e s e a r c h ，a p p l i e dm a t h e m a t i c s ，c o m p u t e rs c i e n c e ，m a n a g e m e n ts c i e n c ea n ds oo n ，a s t h ec o m p u t e rs c i e n c e ，t h em a n a g e m e ms c i e n c ea n dt h em o d e m p r o d u c t i o nt e c h n o l o g y d e v e l o p t h i st h e s i si so r g a n i z e di n t of o u rc h a p t e r s ，a n dm a i n l yd e a l sw i t ht h ei n v e r s e n e t w o r kp r o b l e m su n d e rt h ew e i g h t e dh a m m i n gd i s t a n c e i nc h a p t e r1 ，w ei n t r o d u c e s o m er e l a t e db a s i cc o n c e p t sa n dk n o w l e d g e a n dt h e nw ed i s c u s sd i f f e r e n tm o d e l sf o r t h ed i f f e r e n t p r o b l e m s i nc h a p t e r2 ，t h ei n v e r s em a x i m u mf l o wp r o b l e m su n d e rt h ew e i g h t e dh a m m i n g d i s t a n c ea r ed i s c u s s e d i nag i v e nc o n n e c t e da n dd i r e c t e dn e t w o r k ( ka ，c ) ，e a c ha r c h a sas p e c i f i cm o d i f i c a t i o nc o s t l e tf ob eaf e a s i b l ef l o wo fn w ea r ea s k e dt om o d i f y t h ea r cc a p a c i t i e ss u c ht h a tf of o r m sam a x i m u mf l o wo fna n dt h em o d i f i c a t i o nc o s t o fm o d i f i e da r c si sm i n i m i z e du n d e rt h ew e i g h t e dh a m m i n gd i s t a n c e f o u rm o d e l s a r es t u d i e d i nt h es u m t y p em o d e l ，w er e s o r tt ot h em e t h o do ft h em i n i m u mc u to f t h er e s i d u a ln e t w o r k , t op r o d u c ea p o l y n o m i a la l g o r i t h mw h i c hr u n si nd ( 佗3 ) t i m e i n t h eb o t t l e n e c k t y p em o d e lt h em e t h o do ft h eb o t t l e n e c km i n i m u mc u to ft h er e s i d u a l n e t w o r ki su s e dt op r e s e n ta p o l y n o m i a la l g o r i t h mw h i c h r u n si no ( m + n l o gn ) t i m e a n da sf o rt h em o d e lo ft w om i x e dt y p e s ，u s i n gt h eb i s e c t i o nm e t h o da n dt h ea l g o r i t h m s g i v e nb e f o r e ，w ep r e s e n tt h e i rp o l y n o m i a la l g o r i t h m st h a tr u ni no ( n 3 l o gm ) t i m ea n d o ( n 3 ) t i m e ，r e s p e c t i v e l y i nc h a p t e r3 ，w ec o n s i d e rt h ef o l l o w i n gi n v e r s em i l l m a xs p a n n i n gt r e ep r o b l e m s u n d e rt h ew e i g h t e dh a m m i n gd i s t a n c e i nag i v e nc o n n e c t e dg r a p hg ( ke ，c ) ，e a c h a r ch a sas p e c i f i cm o d i f i c a t i o nc o s t 1e tt ob ea s p a n n i n gt r e eo fg w e a r ea s k e d t om o d i f yt h ee d g el e n g t h ss u c ht h a tt of o r m sar a i n m a xs p a n n i n gt r e eo fga n d t h em o d i f i c a t i o nc o s to fm o d i f i e de d g e si sm i n i m i z e du n d e rt h ew e i g h t e dh a m m i n g m 一 a b s t r a c t d i s t a n c e ，f o u rm o d e l sa r es t u d i e d i nt h es u m t y p em o d e l ，w ea r ef i r s tg i v e nt h er a n g e o ft h ev a l u e ，a n du s et h em e t h o do ft h er e s t r i c t e dm i n i m u mw e i g h te d g ec u tp r o b l e m t op r o d u c ea p o l y n o m i a la l g o r i t h mw h i c hr u n si nd ( 禮4 ) t i m e i nt h eb o t t l e n e c k - t y p e m o d e l ，t h em e t h o df o rt h er e s t r i c t e dm i n i m u mb o t t l e n e c k - t y p ew e i g h te d g ec u tp r o b l e m i sa d o p t e dt op r e s e n tap o l y n o m i a la l g o r i t h mw h i c hr u n si no ( n 5 ) t i m e a n da sf o r t h em o d e lo ft w om i x e dt y p e s ，u s i n gt h eb i s e c t i o nm e t h o da n dt h ea l g o r i t h m sg i v e n b e f o r e ，w ep r e s e n tt h e i rp o l y n o m i a la l g o r i t h m st h a tr u ni no ( n 5 ) t i m ea n do ( n 4 ) t i m e ， r e s p e c t i v e l y i nc h a p t e r4 ，w ec o n s i d e rt h ef o l l o w i n gi n v e r s em i n i m u mc u tp r o b l e m su n d e rt h e w e i g h t e dh a m m i n gd i s t a n c e i nag i v e nc o n n e c t e da n dd i r e c t e dn e t w o r k ( ka ，c ) ， e a c ha r ch a sas p e c i f i cm o d i f i c a t i o nc o s t l e t 一，碧 b ea ns tc u to fn w e a r ea s k e dt om o d i f yt h ea l ec a p a c i t i e ss u c ht h a t x o ，碧】f o r m sam i n i m u mc u to fn a n dt h em o d i f i c a t i o nc o s to fm o d i f i e da r c si sm i n i m i z e du n d e rt h ew e i g h t e dh a m m i n g d i s t a n c e t w om o d e l sa r es t u d i e d t h ef i r s ti sa s u m t y p em o d e l ，i nw h i c hw es h o wt h e p r o b l e mi sn p h a r db yu s i n gt h er e d u c t i o nf r o ma ni n s t a n c eo fk n a p s a c kp r o b l e mt o a ni n s t a n c eo ft h ep r o b l e mi np o l y n o m i a lt i m e ，i nt h el a t t e rb o t t l e n e c k - t y p em o d e l ，i n t e r m so ft h ep r o p e r t i e so ft h em a x i m u mf l o wa n dm i n i m u mc u tt h e o r ya n dt h eh a m m i n g d i s t a n c e ，w ep r e s e n tap o l y n o m i a la l g o r i t h mw h i c hr u n si n0 ( m 護) t i m e k e yw o r d s ： n e t w o r ko p t i m i z a t i o n ，i n v e r s ep r o b l e m s ，m a x i m u mf l o w ，m i n m a x s p a n n i n gt r e e ，m i n i m u mc u t ，p o l y n o m i a la l g o r i t h m s i v 第一章緒論 第一章緒論 1 1 組合優(yōu)化與算法復雜性簡介 在人類幾乎所有的社會活動中都有“尋優(yōu)”的需求，將尋優(yōu)的過程用數(shù)學 模型描述并求解，是應用數(shù)學的重大進展之一組合優(yōu)化問題又稱離散優(yōu)化問 題，是一類重要的優(yōu)化問題雖然某些組合優(yōu)化問題有悠久的歷史淵源，被費馬 ( f e r m a t ) 、歐拉( e u l e r ) 等眾多著名數(shù)學家研究過，但作為運籌學的一個獨 立分支而發(fā)展壯大起來還是近幾十年的事它是一門新興的學科分支，現(xiàn)在已在 網(wǎng)絡通信、物流管理、交通規(guī)劃等領域發(fā)揮了重要作用 定義1 1 1 ：組合優(yōu)化問題7 r 是一個極小化問題，或是一個極大化問題，它由下述 三部分組成： ( 1 ) 實例集合； ( 2 ) 對每一個實例，有一個有窮的可行解集合s ( j ) ； ( 3 ) 目標函數(shù)，它對每一個實例，和每一個可行解盯s ( n ，賦以一個有理 數(shù)f ( z ，盯) 如果該問題是極小化問題( 極大化問題) ，則實例，的最優(yōu)解為這樣一個可 行解礦s ( o ，它使得對所有的仃s ( j ) ，都有( z ，礦) f ( 1 ，仃) ( ，( j ，礦) f ( 1 ，盯) ) 典型的組合優(yōu)化問題有旅行商問題( t r a v e l i n gs a l e s m a np r o b l e m - - t s p ) 、 加工調(diào)度問題( s c h e d u l i n gp r o b l e m ，如f l o w s h o p ，j o b s h o p ) 、0 1 背包問題 ( k n a p s a c kp r o b l e m ) 、裝箱問題( b i np a c k i n gp r o b l e m ) 、圖著色問題( g r a p h c o l o r i n gp r o b l e m ) 、聚類問題( c l u s t e r i n gp r o b l e m ) 等網(wǎng)絡中的組合優(yōu)化 問題還包括最短路問題( s h o r t e s tp a t hp r o b l e m ) 、最小生成樹問題( m i n i m a l s p a n n i n gt r e ep r o b l e m ) 、最大流問題( m a x f l o wp r o b l e m ) 、最小費用流問題 ( m i n c o s tf l o wp r o b l e m ) 等組合優(yōu)化全貌可參見【4 3 ；7 6 有些優(yōu)化問題描述 非常簡單，并且有很強的工程代表性，但最優(yōu)化求解很困難，其主要原因是求 解這些問題的算法需要極長的運行時間與極大的存儲空間，以致根本不可能在 現(xiàn)有計算機上實現(xiàn)，即所謂的“組合爆炸”正是這些問題的代表性和復雜性激 起了人們對組合優(yōu)化理論與算法的研究興趣 第一章緒論 定義1 1 2 ：算法是指一步步求解問題的通用程序，它是解決問題的程序步驟的 一個清晰描述確定性算法是指從前一步到后一步的運行由當前狀態(tài)唯一確 定如果存在一個算法，它對組合優(yōu)化問題7 r 的每個實例，在有限步后一定可 以得到該實例的關于7 r 的提問的答案，那么稱該算法解此組合優(yōu)化問題7 r 定義1 1 3 ：對于一個組合優(yōu)化問題7 r ，如果給定任意一個實例，算法a 總能 找到一個可行解盯s ( z 1 ，那么就稱a 為丌的近似算法( a p p r o x i m a t i o na l g o - r i t h m ) ；如果進一步這個可行解的目標值總等于最優(yōu)解值，則稱a 為最優(yōu)算法 ( o p t i m a la l g o r i t h m ) 例如，單純行法就是解線性規(guī)劃問題的最優(yōu)算法，表上作業(yè)法就是求解運 輸問題的最優(yōu)算法，匈牙利算法就是求解指派問題的最優(yōu)算法，而解非線性規(guī) 劃問題的絕大多數(shù)算法由于不能總得到最優(yōu)解，它們只是近似算法 對于一個具體問題可能會有不同的算法求解，我們希望尋找解決問題的最 有效算法在廣泛的意義下，效率用執(zhí)行算法所用的全部計算資源的多少來衡 量，但通常用時間作為衡量標準，也就是說把能最快得到最終結(jié)果的算法稱為 最有效算法通常，算法所用的時間是指算法中所含的加、減、乘、除、比較 等基本運算次數(shù)而算法所用的時間與實例的規(guī)模有關，為此我們用輸入長度 來刻劃實例的規(guī)模所謂實例的輸入長度通常是指實例所用的計算機內(nèi)存單元 數(shù) 定義1 1 4 ：算法的時間復雜性是指關于實例輸入長度n 的函數(shù)廠( 幾) ，用來表示 算法的時間需求，對每一個可能的輸入長度，它是指在最壞情況下該算法解此 輸入長度的實例時所需時間( 基本運算步數(shù)) 即對于輸入長度相同的所有實 例，把算法對這些實例的最壞情況作為時間復雜性的度量 定義1 1 5 ：若存在一個常數(shù)c ，使得對所有禮0 ，都有i 廠( 禮) i c l a ( n ) l ，則 稱函數(shù)t 廠( 幾) 是0 圓( 佗) ) 時間復雜性是0 ) ) 的算法稱為多項式時間算法，這 里p 是一個多項式，佗為輸入長度不能這樣限制時間復雜性函數(shù)的算法稱為指數(shù) 時間算法還有一類算法叫偽多項式時間算法，它的時間復雜性是關于實例輸入 長度釓和實例中最大數(shù)的二元多項式函數(shù)在二進制編碼下，偽多項式時間算法 并不是多項式時間算法，而是指數(shù)時間算法 一個組合優(yōu)化問題如果已經(jīng)找到了多項式時間算法，那么就稱它為多項式 時間可解問題把所有這樣的問題集合記為p ，因此多項式時間可解問題就稱 一2 一 第一章緒論 為p 類問題在關于問題能否有有效算法的討論中，人們發(fā)現(xiàn)，如果把所有問題 都轉(zhuǎn)化成只要求簡單回到“是”或“否的形式，將會帶來許多方便，使差別 很大的不同問題進行比較成為可能我們稱答案為“是或“否”的問題為判定 問題 定義1 1 6 ：給定一個判定問題，如果存在一個算法，對任何一個答案為“是 的實例，該算法首先給出一個猜想，該猜想規(guī)模不超過，的輸入長度的某個多 項式函數(shù)，且驗證猜想的正確性僅需多項式時間，則稱該問題屬于n p 類 定義1 1 7 ：如果n p 類中所有問題都可以多項式時間歸約到n p 類中某個問題7 r ， 則稱7 r 是n p 一完全問題 定理1 1 8 ：p = n p 當且僅當存在一個n p 一完全問題有多項式時間算法 定義1 1 9 ：設7 r 是一判定問題，p ( ) 是任一多項式，用7 r p 表示7 r 的這樣一個子 問題：它的任一輸入長度為n 的實例的最大數(shù)小于p ) 如果存在某個多項 式p 使砷是n p 一完全的，則稱7 r 是強n p 一完全的 定理1 1 1 0 ：在p # n p t ，強n p 一完全問題不存在偽多項式時間算法 定義1 1 1 l ：如果某優(yōu)化問題7 r 的判定問題是n p 一完全的，則稱問題丌是n p 一難 的；如果判定問題是強n p 一完全的，則稱丌是強n p 一難的 定理1 1 1 2 ：除非p - - n p ，n p 一難問題沒有多項式時間算法，強n p 一難問題沒 有偽多項式時間算法 計算復雜性理論興起于二十世紀六十年代，和算法的設計與分析密切相 關，詳細內(nèi)容可參閱文獻 3 5 1 2 組合優(yōu)化逆問題 經(jīng)典的組合優(yōu)化問題都是給定一些參數(shù)，例如權(quán)重、容量、長度，然 后我們要找到所給問題的一個最優(yōu)解然而，在實際生活中經(jīng)常會出現(xiàn)這樣 一種情形，現(xiàn)成就有一個可行解，但是在目前的參數(shù)下，這個可行解并不是 最優(yōu)解，而我們希望盡可能少的修正現(xiàn)有參數(shù)，從而使得給定的可行解成為 最優(yōu)解我們把這類問題稱作逆問題，而把經(jīng)典的組合優(yōu)化問題稱為原問題 一3 一 第一章緒論 在1 9 9 2 年，b u r t o na n dt o i n t 1 2 首先研究丫由預測地震運動而引出的最短路逆問 題從那以后組合優(yōu)化逆問題就受到眾多學者的廣泛關注對于給定的兩個向 量c = ( c 1 ，c 2 ，) 和d = ( d l ，d 2 ，厶) ，它們之間不同的距離定義為： t l 定義1 2 1 ：f 1 距離： i i c 一圳= i q 一也i i = 1 幾f 一 z 2 距離： i i c 一訓= 、( q 一比) 2 f 。距離： l i c d i i = m & xf q 一也i 哈明足巨離： 日c q ，噸，= ：果q c i = 也d i ， 在過去十幾年里，對z 】，1 2 和2 0 0 距離下組合優(yōu)化逆問題的研究已經(jīng)相對比較 成熟，下面首先簡單把已有的結(jié)果做個介紹，更詳細的內(nèi)容可以參考綜述文 獻【4 2 】及相關的文章 最大流逆問題：y a n g z h a n ga n dm a 7 2 研究了最大流逆問題，他們通過利 用最大流與最小割的對偶性把該問題轉(zhuǎn)化為一個最小費用流問題 最小一最大支撐樹逆問題：y a n ga n dz h a n g 7 5 研究了2 1 和f o o 距離下的最小 一最大支撐樹逆問題和最小一最大容量路逆問題，對于所提到的模型，他們都 給出了多項式時間算法 最小割逆問題：1 9 9 7 年y a n g ，z h a n ga n dm a 7 2 首先研究了無權(quán)的f 1 距離 下受約束的最小割逆問題，他們把該問題轉(zhuǎn)化為最大流問題a h u i aa n do r - 1 i i l 在2 0 0 1 年 3 】和2 0 0 2 年【4 】分別用線性規(guī)劃的方法和組合的方法討論上述問題 對于賦權(quán)“距離下受約束的情形，z h a n ga n dc a i 8 0 和h h u j aa n do r l i n 3 都把它 轉(zhuǎn)化為最小費用流問題燦l u j aa n do r l i n 在2 0 0 2 年 4 研究了賦權(quán)f o o 距離下受約束 的問題，他們用組合的方法得到一個基于二分法的算法，后來他們發(fā)現(xiàn)通過利 用r a d z i k 5 8 的方法可以把他們的算法變?yōu)閺姸囗検綍r間算法y a n g 7 3 j 正明了 給出部分解的受約束最小割逆問題是n t 難的 線性規(guī)劃逆問題：z h a n ga n dl i u 【8 1 】在1 9 9 6 年首先研究了線性規(guī)劃逆 問題，他們把它轉(zhuǎn)化為一個新的線性規(guī)劃問題后來在1 9 9 9 年，z h a n ga n d l i u 8 2 乘i h u a n ga n dl i u 4 6 對該問題進行了更深入的研究2 0 0 1 年a h u j aa n d 一4 一 第一章緒論 o r l i n 3 對對偶的線性規(guī)劃逆問題進行了研究，他們給出了一種很多逆問題都可 以通用的方法 最小費用流逆問題：z h a n ga n dl i u 【8 1 在1 9 9 6 年首先研究了l l 距離下 無約束的最小費用流逆問題2 0 0 1 年a h u j aa n do r l i n 3 用線性規(guī)劃的方 法把該問題轉(zhuǎn)化為最小費用環(huán)流問題c a i 。y a n ga n dl i 1 8 ，a h u j aa n d o r l i n 4 和s o k k a l i n g a m 6 2 都對該問題進行了研究對于z 距離下的最小費用流 逆問題，z h a n ga n dl i u 【8 3 】研究了無權(quán)情形，a h u j aa n do r l i n 3 ；4 】研究了無權(quán)情 形和賦權(quán)情形d i a j 2 2 ；2 3 1 用線性規(guī)劃的方法研究了該問題s o k k a l i n g a m 6 2 貝, 0 對f o 。距離下的無權(quán)情形和賦權(quán)情形以及z 2 距離下的無權(quán)情形進行了研究 最短路逆問題：b u r t o na n dt o i n t 1 2 把f 2 距離下的最短路逆問題轉(zhuǎn)化為二次 規(guī)劃問題并且應用g o l d f a r ba n di d n a n i 3 6 的算法求解z h a n g ，m aa n dy a n g 9 0 冪0 用列生成方法研究了z ，距離下無權(quán)的情形c a ia n dy a n g 1 6 用線性規(guī)劃的方法 研究了2 】距離下的逆問題z h a n ga n dl i u 8 2 和a h u j aa n do r l i n 3 證明了2 】距離下 無權(quán)的情形的最短路逆問題就是同一個圖中的另外一個最短路問題h ua n d l i u 4 5 給出了f ，距離下無權(quán)的情形的最短路逆問題的時間復雜性i f ；3 0 ( n 3 ) 鬟j 算法 ( 其中n 為給定圖或網(wǎng)絡的頂點數(shù)，下同) 指派逆問題：z h a n ga n dl i u 8 1 ；8 2 ，z h a n ga n dm a 8 8 和a h u j aa n d o r l i n 3 把f ，距離下的指派逆問題轉(zhuǎn)化為最小費用環(huán)流問題其q b z h a n ga n d l i u 8 1 ；8 2 】和a h u j aa n do r l i n 3 還證明了f 】距離下無權(quán)情形也是個指派問題 y a n g 7 3 i 正明了給出部分解的指派逆問題是n p - 難的 賦權(quán)的擬陣交逆問題：1 9 9 7 年c a ia n d1 i 1 5 通過利用f r a n k 2 9 構(gòu)造賦權(quán)擬 陣交的算法把擬陣交逆問題轉(zhuǎn)化為最小費用環(huán)流問題1 9 9 9 年c a i 1 4 用另外的 方法把f 1 距離下的問題轉(zhuǎn)化為輔助網(wǎng)絡的最小費用環(huán)流問題2 0 0 2 年z h a n ga n d l i u 8 3 考慮了k 距離下無約束的情形，他們利用f r a n k 的結(jié)果把問題轉(zhuǎn)化為最大 平均圈問題 最小支撐樹逆問題：1 9 9 7 年z h a n g ，x ua n dm a 9 1 直接利用組合的方法得 到了賦權(quán)f 】距離下無約束情形的時間復雜性為0 ( m 4 ) ( 其中m 為給定圖( 網(wǎng)絡) 的邊( 弧) 的數(shù)目，下同) 的多項式時間算法1 9 9 9 年s o k k a l i n g a m ，a h u j aa n d o r l i n 6 3 通過把同樣的問題轉(zhuǎn)化為一個二分圖上的匹配問題得到了時間復雜 性為d f 扎3 ) 的多項式時間算法a h u j aa n do r l i n 2 改進了上文的算法，把時間復 雜性降為0 f n 2 l o g 佗1 2 0 0 3 年d e l l a m i c o ，m a f f i o l ia n dm a l u c e l l i 2 1 用別的方法也 得到了時間復雜性為0 ( 佗3 ) 的算法1 9 9 6 年z h a n ga n dm a 8 8 研究了f 】距離下受 一5 一 第一章緒論 約束的最小支撐樹逆問題，他們把該問題轉(zhuǎn)變?yōu)橛蒻 + 2 個頂點和d f n m ) 條弧 構(gòu)成的網(wǎng)絡的最小費用流問題1 9 9 9 年s o k k a l i n g a m a h u j aa n do r l i n 6 3 和z h a n g a n dl i u 8 2 都研究了2 距離下無約束的最小支撐樹逆問題1 9 9 6 生 z z h a n g ，l i ua n d m a 8 5 用線性規(guī)劃方法對f 】距離下受劃分約束的最小支撐樹逆問題進行了研 究，他們把受約束和不受約束的情形都轉(zhuǎn)化為最小費用流問題 其他逆問題：c a i ，y a n ga n dl i 1 8 研究了賦權(quán)“距離下受約束的最大化子模 函數(shù)逆問題z h a n ga n dm a 8 8 1 研究了f 】距離下受約束的最短路徑樹逆問題，他 們利用線性規(guī)劃的方法把該問題轉(zhuǎn)化為最小費用環(huán)流問題d e l l a m i o o ，m a f f i o l i a n dm a l u c e l l i 2 1 研究了z ，距離下不受約束的最大擬陣基逆問題，他們把該問 題轉(zhuǎn)化為另外一個最大擬陣基問題l i ua n dz h a n g 5 3 對? 】和f 。距離下的最大完 美匹配逆問題進行了研究c a i 。y a n ga n dz h a n g 1 9 研究了l l 距離下受約束的中 心選址逆問題，他們證明了該問題是n p 難的y a n ga n dz h 卸g 7 0 】研究了1 1 距 離下不受約束的最大容量逆問題y a n g 6 8 研究了最大容量路逆問題，他通過 把3 s a t 問題歸約證明了該問題是n p 難的，并且給出了一個求局部最優(yōu)解的算 法w e i ，z h a n ga n dz h a n g 6 5 研究了資料包絡分析逆問題，他們把一般的問題轉(zhuǎn) 化為一個多目標規(guī)劃問題，而把特殊的情形轉(zhuǎn)化為一個單目標規(guī)劃問題 1 3 哈明距離下組合優(yōu)化逆問題 哈明距離下的組合優(yōu)化逆問題是逆優(yōu)化問題中相對較新的一個分支，該問 題的研究具有一定的實際應用價值例如，在交通管理中，要縮短車輛通過某道 路所需要的時間經(jīng)常是通過加寬道路來實現(xiàn)的但往往只是在道路的某幾處比 較狹窄( 而不是道路處處都需要加寬1 ，而且這些地方道路兩旁都有一些建筑或 住戶，要加寬道路必須對這些建筑和住戶進行拆遷安置，此時改造此道路的費 用主要是拆遷安置費，而不是加寬道路的工程費用，該費用可以看成是個固定 值，而不是與道路的長度成正比要求在滿足一定條件下，總的費用的改變盡可 能少我們注意到，2 】，f 2 ，2 0 0 距離相對于改變量而言都是連續(xù)的凸函數(shù)，而哈明 距離則是離散的非凸函數(shù)，這就使得我們不能夠把求解z 1 ，2 2 ，k 距離下逆問題的 方法直接應用到哈明距離逆問題上來 2 0 0 5 年，h e ，z h a n ga n dy a o 4 1 1 第一次提出哈明距離下的逆問題，他們首先 研究了哈明距離下總和型最小支撐樹逆問題，對于有約束和無約束模型，他們 都給出了時間復雜性為0 ( 禮3 m 1 的多項式時間算法z h a n g ，z h a n ga n dh e 7 8 進 步研究了哈明距離下瓶頸型最小支撐樹逆問題，對于無約束情形，他們給出了 一6 一 第一章緒論 時間復雜性為o ( n m l 的多項式時間算法，對于受約束情形，他們給出了時間復 雜性為d ( 伊仇l o g m ) 的多項式時間算法d u i na n dv o l g e n a n t 2 5 也研究哈明距離 下瓶頸型的無約束的優(yōu)化逆問題，他們首先給出了求解最小支撐樹逆問題的時 間復雜性為d ( 億2 ) 的改進算法，接著他們進一步把這個算法推廣到哈明距離下瓶 頸型最小路徑樹逆問題和線性指派逆問題z h a n g 。z h a n ga n dh e 7 7 研究哈明距 離下的中心選址逆問題，對于總和型模型，利用把集覆蓋問題的實例三歸約， 他們證明要得到哈明距離下的中心選址逆問題的一個近似性能比為o ( 1 0 9 佗1 ) 的 近似算法是強n p 一難的對于瓶頸模型，他們通過利用二分法得到了一個時間 復雜性為o ( n 2l o g n ) 的多項式時間算法z h a n g ，z h a n ga n dq i 7 9 研究了哈明距離 下最短路逆問題，他們首先利用把3 s a t 問題的實例多項式歸約證明了一般情 形哈明距離下的最短路逆問題是強n p 一難的接著他們利用把背包問題的實例 多項式歸約證明了一類單發(fā)點、單收點哈明距離下的最短路逆問題也是n p 一難 的，然后他們給出了該類問題的一個偽多項式時間算法，從而證明了該問題不 是強n p 一難的 1 4 論文概述 本文主要對哈明距離下的若干網(wǎng)絡逆問題進行了研究第二章研究的是賦 權(quán)哈明距離下最大流逆問題：對給定的連通有向網(wǎng)絡( v a ，c ) ，每條弧都有 一個容量改造費用，令廠。是網(wǎng)絡的一個可行流，如何改變網(wǎng)絡弧上的容量使 得廠。成為新容量下的最大流，且在哈明距離下產(chǎn)生的改造費用最小我們總共 研究了四種模型：對于總和型，我們把問題轉(zhuǎn)化為求解剩余網(wǎng)絡的一個受限制 割，從而給出了時間復雜性為d f 禮3 ) 的多項式時問算法，對于瓶頸型，我們通 過把問題轉(zhuǎn)化為求解剩余網(wǎng)絡的一個受限制瓶頸割問題，從而給出了時間復雜 性為0 ( m + n 1 0 9 n ) 的多項式時間算法，對于兩種混合型，我們利用二分法思 想，結(jié)合前面的算法，分別給出了時間復雜性為o ( n 3 1 0 9 m ) 和0 ( 幾3 ) 的多項式 時間算法 第三章研究的是賦權(quán)哈明距離下最小一最大支撐樹逆問題：對給定的連通 圖g = f k e ，c ) ，每條邊都有一個長度改造費用，令p 是圖g 的一個支撐樹， 如何改變圖上邊的長度使得p 成為新長度下的最小一最大支撐樹，且在哈明距 離下產(chǎn)生的改造費用最小我們總共研究了四種模型：對于總和型，我們先給 出了最優(yōu)解的可能取值，然后通過求解受限的最小邊割問題給出了時問復雜性 為o ( n 4 ) 篚j 多項式時間算法，對于瓶頸型，我們通過求解受限的最小瓶頸邊割問 一7 一 第一章緒論 題給出了時間復雜性為0 ( n 5 ) 的多項式時間算法，對于兩種混合型，我們利用二 分法的思想，結(jié)合前面的算法，分別給出了時間復雜性為0 ( n 5 ) 和0 ( ) 的多項 式時間算法 第四章研究的是賦權(quán)哈明距離下最小割逆問題：對給定的連通有向 網(wǎng)絡( va ，c ) ，每條弧都有一個容量改造費用，令1 f x o ，f 是網(wǎng)絡的一 個s 一培0 ，如何改變網(wǎng)絡弧上的容量使得 x o ，f 成為新容量下的最小割，且 在哈明距離下產(chǎn)生的改造費用最小我們研究了兩種模型：對于總和型，我們利 用背包問題的實例的多項式歸約，證明了該問題是n p 難的，對于瓶頸型，通過 利用最大流一最, b 害- u 和哈明距離的性質(zhì)，我們給出了時間復雜性為o ( m n 3 ) 的 多項式時間算法。 為后文的敘述方便，對于一個弧集( 邊集) r 以及定義在其上的一個向 量叫，我們記如8 ( r ) = 伽巧，驢( r ) = 一m 懋，( 這里字母s 和扮別代表總 和和瓶頸) ，這個記號在整篇論文中通用 一8 一 第二章賦叔哈明距離f 最大流逆問題 2 1 引言 第二章賦權(quán)哈明距離下最大流逆問題 設( v a ，c ) 是給定的一個連通的有向網(wǎng)絡，其中v = _ f 1 ，2 ，n 和a = ( 毛歹) ，i ，j v ( i a i = m ) 分別是頂點集和弧集，而c 是定義在弧集上的容量向 量，它的每個分量龜 稱為是對應弧的容量在頂點集y 中有兩個特殊點8 ，t ：其 中s 僅有出弧而沒有入弧，稱為發(fā)點，而t 僅有入弧而無出弧，稱為收點一 個( s 啦流或者就簡單的稱為流是一個定義在弧集a 上的函數(shù)，：a _ r i a i ，它 首先要滿足如下的流量限制： 對每條弧( i ，j ) a ，都有o 向 此外還要滿足如下的守恒規(guī)則： p 圳 j jln 其中u ( ，) 是流廠從s 到t 的流值最大流問題是尋找一個流值最大的流，這是一個 經(jīng)典的可以在多項式時間內(nèi)解決的網(wǎng)絡優(yōu)化問題，在實際生活中有著廣泛的應 用 反過來，最大流逆問題是通過盡可能少的改變給定的容量向量，從而使得 給定的流成為最大流y a n g ，z h a n ga n dm a 7 2 j , t 正l a j 了最大流逆問題在f l 距離下是 多項式可解的在本章中，我們考慮的是賦權(quán)哈明距離下的最大流逆問題，我們 將討論四種模型 給每條弧( i ，j ) 一個相應的容量調(diào)整費用毗f 0 ，我們把費用向量記為w 設，o 是網(wǎng)絡( v a ，c ) 的一個可行流那么賦權(quán)哈明距離下總和型最大流逆問題 就是要尋找一個能夠滿足下面三條的容量向量d ： ( a ) ，o 是網(wǎng)絡( va ，d ) 的最大流； ( b ) 對每條弧( t ，j ) a ，都有一l o d , j 一su o ，其中揚，u i j o 分別是容 量q f 改變的下界和上界； 一9 一 s 厶蟣江江勤 第二章畈權(quán)哈明距離下最大流逆問題 ( c ) 最小化日( ，奶) ( i , j ) e a 而對于賦權(quán)哈明距離下瓶頸型最大流逆問題，就是要找一個新的容量向 量d ，它在滿足上面( a ) 和( b ) 的基礎上還要滿足： ( c 7 ) 最小化( 寫囂日( ，奶) 我們