不確定圖上流分布可靠性問(wèn)題研究.pdf

1、在實(shí)際應(yīng)用中，不確定性是許多系統(tǒng)的固有特性，如電力傳輸網(wǎng)中的元器件、數(shù)據(jù)通信網(wǎng)中的節(jié)點(diǎn)都存在著發(fā)生故障的概率，交通運(yùn)輸網(wǎng)中也有著發(fā)生擁塞的概率等?？蓪⑦@類應(yīng)用中的系統(tǒng)建模成不確定圖，從而將問(wèn)題轉(zhuǎn)化成不確定圖中的問(wèn)題來(lái)解決。不確定圖最可靠最大流問(wèn)題是指在不確定圖中可以傳遞最大流的多個(gè)流分布中選擇可靠性最高的一個(gè)。該問(wèn)題能夠很好的解決諸如構(gòu)建可靠性網(wǎng)絡(luò)、可靠傳輸路徑的選擇以及系統(tǒng)薄弱環(huán)節(jié)的分析等一系列問(wèn)題。
　　針對(duì)現(xiàn)有的最可靠最大流

2、算法時(shí)間復(fù)雜度較高，難以應(yīng)用于大規(guī)模網(wǎng)絡(luò)的不足，本文給出負(fù)權(quán)群落的概念，并借鑒最小費(fèi)用流中平移思想提出了基于負(fù)權(quán)群落消去的算法(NCEA)。NCEA算法首先求得一個(gè)最大流分布，然后在該最大流分布對(duì)應(yīng)的剩余圖中查找負(fù)權(quán)群落，通過(guò)負(fù)權(quán)群落的消去得到可靠性更高的最大流分布，接著繼續(xù)在更新后的剩余圖中查找負(fù)權(quán)群落并消去，直到剩余圖中不存在負(fù)權(quán)群落，此時(shí)求得的最大流分布經(jīng)論證即為最可靠最大流。然而在NCEA算法中涉及到組合運(yùn)算，容易產(chǎn)生組合爆炸，

3、為此提出了基于剪枝策略的改進(jìn)算法(PBA)，PBA算法利用若一個(gè)組合滿足條件，則包含該組合的其余組合均不滿足條件的性質(zhì)很好的解決了組合爆炸的問(wèn)題，并顯著的提高了算法的性能。
　　為了進(jìn)一步提高算法性能，滿足對(duì)算法速度要求很高而精度要求不高的應(yīng)用需求，本文根據(jù)負(fù)權(quán)群落的特點(diǎn)給出了基于單環(huán)消去的近似算法(OCEA)，該算法具有很好的性能，能夠很快的求出一個(gè)近似解，但算法精度波動(dòng)性較大，為此，本文又提出的另一個(gè)基于雙環(huán)消去的近似算法(T