本文關(guān)鍵詞： l_∞模 極大加和支撐樹 組合優(yōu)化逆問題 時間復雜性　出處：《東南大學》2017年碩士論文　論文類型：學位論文

【摘要】：本文研究的是l_∞模下調(diào)整最大權(quán)重w的極大加和支撐樹逆問題.極大加和支撐樹問題是在一個邊賦權(quán)無向連通圖G(V,E,c,w)中,找一棵最優(yōu)的支撐樹T*,使得目標函數(shù)max_(e∈T)w(e)+∑_(e∈T) c(e)最小,該問題的時間復雜度為O(m log n),其中m:= |E|,n:= |V|.它的逆問題描述為:給定網(wǎng)絡G的一棵非最優(yōu)的支撐樹T_0,調(diào)整網(wǎng)絡各邊的權(quán)重w到(?),使得T_0成為新網(wǎng)絡G(V,E,c,(?))下的最優(yōu)極大加和支撐樹,其中w-l≤(?)≤w+u,l≥0,u≥0.目標函數(shù)是使得maxe∈Eq(e)|w(e)-(?)(e)|最小,其中q(e)是調(diào)整1單位w(e)所需的費用.本文首先分析了該逆問題的可行解和最優(yōu)解所具有的性質(zhì),其次得到了如何通過給定的可行目標函數(shù)值構(gòu)造可行解這個重要結(jié)論.最后我們分別討論了三種情況.首先在無界的單位無窮模情況下,我們根據(jù)最優(yōu)值的性質(zhì)設計了二分法確定最優(yōu)值的下界,進一步根據(jù)最優(yōu)解的性質(zhì)確定了最優(yōu)值,并證明了該算法的迭代次數(shù)不超過O(m),算法的時間復雜度為O(m~2 log n).在賦權(quán)無窮模的情況下,我們先討論了無界的情況,再推廣到一般有界的情況.我們先將已知樹上的邊分成兩類,根據(jù)每類邊的不同性質(zhì)設計了尋求最優(yōu)解的算法.證明了算法最多調(diào)用O(m~2)次求解極大加和支撐樹問題的算法,因此時間復雜度為O(m~3 log n).
[Abstract]:In this paper , we study the maximal load and the support tree inverse problem of adjusting the maximum weight w under the mode of l _ 鈭，

本文編號：1542093