增廣鏈修復(fù)的最大流求解算法
最大流問題是運籌學(xué)中經(jīng)典問題之一，它可以使用圖的方法進行求解。網(wǎng)絡(luò)最大流在計算機、工程學(xué)等學(xué)科中有著廣泛的用途，例如通信網(wǎng)絡(luò)流量分配、交通運輸線路分配等都能轉(zhuǎn)化為網(wǎng)絡(luò)最大流數(shù)學(xué)模型。最大流的經(jīng)典算法主要分為增廣鏈法和預(yù)流推進法，其中常用的增廣鏈法有Ford-Fulkerson提出的增廣鏈算法、Dinic研究的阻塞流和分層網(wǎng)絡(luò)算法、Edmonds等設(shè)計的最短路增廣算法、Karzanov改進的先進先出預(yù)流推進算法及Cherkassky改進的最高標(biāo)號預(yù)流推進算法。這些經(jīng)典算法逐漸降低了求解網(wǎng)絡(luò)最大流的時間復(fù)雜度，是研究大規(guī)模網(wǎng)絡(luò)的基礎(chǔ)。
經(jīng)典算法的經(jīng)典之處在于它的適用面廣，在各類網(wǎng)絡(luò)中都能穩(wěn)定運行且在較短時間內(nèi)完成求解過程，但在部分特殊網(wǎng)絡(luò)如稀疏網(wǎng)絡(luò)中，它們的效率不高，因此需針對這些網(wǎng)絡(luò)的特點改進或使用新算法提高執(zhí)行效率，實現(xiàn)其研究價值。
本文針對Newman和Watts提出的NW小世界網(wǎng)絡(luò)以及Barabasi和Albert提出的BA無標(biāo)度網(wǎng)絡(luò)兩種現(xiàn)實中常見的網(wǎng)絡(luò)提出了一種新算法，這種算法能夠盡可能地避免反復(fù)地重新尋找新的增廣鏈，通逋捷徑的方法修復(fù)滿足條件的原始增廣鏈，從而縮短了重復(fù)計算的時間，提高算法效率。
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%