【摘要】：本論文主要研究限制性路構(gòu)建問題,包括兩個(gè)基本內(nèi)容,即限制性路增廣問題和限制性路構(gòu)建問題。限制性路增廣問題可以描述為:給定一個(gè)有向圖D =(V,A;c)以及圖D中的一條s-t有向路Ps,t,其中s,t∈V,費(fèi)用函數(shù)c:A →R+,要尋找弧子集A1(?)A-A(Ps,t),滿足對(duì)任一條弧a ∈ A(Ps,t)(或者對(duì)任一個(gè)頂點(diǎn)u ∈ V(Ps,t)-{s,t}),在誘導(dǎo)子圖Ps,t ∪A1-{a}(或者誘導(dǎo)子圖Ps,t ∪A1-{u})中仍存在一條s-t有向路,目標(biāo)是使得所選弧集合A1的總費(fèi)用c(A1)達(dá)到最小,即c(A1)=∑e∈A1c(e)達(dá)到最小。對(duì)于這兩個(gè)問題,本文設(shè)計(jì)了兩個(gè)時(shí)間復(fù)雜度為O(mn)多項(xiàng)式時(shí)間最優(yōu)算法,其中m表示有向圖D中弧的數(shù)目,n表示有向圖D中頂點(diǎn)的數(shù)目。在上述問題的基礎(chǔ)上,本文研究了限制性路構(gòu)建問題,具體描述為:給定一個(gè)賦權(quán)有向圖D=(V,A;w,c),長(zhǎng)度為L(zhǎng)的材料若干,以及圖DD中一條s-t有向路Ps,t,其中s,t∈V,長(zhǎng)度函數(shù)w:A→RR+,施工費(fèi)用函數(shù)c:→→R+,要構(gòu)建一個(gè)弧集合A1(?)A-A(Ps,t),滿足對(duì)任一條弧a∈A(Ps,t(或者對(duì)任一個(gè)頂點(diǎn)u∈V(s,t)-{s,t}),在誘導(dǎo)子圖Ps,u A1—{a}(或者誘導(dǎo)子圖Ps,∪ A1—{u})中仍存在一條s-t有向路,目標(biāo)是使得構(gòu)建弧集合A1的總費(fèi)用cost(A1)達(dá)到最小,即cost(A1)= ∑e∈A1(e)+k(A1)·c0達(dá)到最小,這里總費(fèi)用包括施工費(fèi)用和購(gòu)買材料的費(fèi)用,k(A1)表示構(gòu)建弧集合A1所需材料的根數(shù),c0為每根材料的購(gòu)買費(fèi)用。對(duì)于此類問題,本文設(shè)計(jì)了兩個(gè)時(shí)間復(fù)雜度為O(mn)的2-近似算法,其中m表示有向圖D中弧的數(shù)目,n表示有向圖D中頂點(diǎn)的數(shù)目。
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

相關(guān)博士學(xué)位論文 前1條

1 丁紅林;限制性路由與網(wǎng)絡(luò)構(gòu)建問題[D];云南大學(xué);2014年

本文編號(hào)：2750089