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