超快網(wǎng)絡(luò)流算法問世
能實現(xiàn)最大流量的同時最大限度降低傳輸成本
瑞士蘇黎世聯(lián)邦理工學(xué)院的研究人員開發(fā)了一種超快算法,即網(wǎng)絡(luò)流算法。該算法成功解決了在網(wǎng)絡(luò)中實現(xiàn)最大流量的同時最大限度降低傳輸成本的問題。這種超快計算能力是研究高度復(fù)雜、數(shù)據(jù)豐富、動態(tài)且快速變化的網(wǎng)絡(luò)(例如生物學(xué)中的分子網(wǎng)絡(luò)或大腦網(wǎng)絡(luò))的重要環(huán)節(jié)。
新算法能為任何類型的網(wǎng)絡(luò)(包括鐵路、公路、水上交通和互聯(lián)網(wǎng))計算出最佳且最低成本的交通流量方案。其執(zhí)行計算的速度極快,幾乎在計算機(jī)讀取描述網(wǎng)絡(luò)數(shù)據(jù)的瞬間就能提供解決方案。
原則上,所有計算方法在尋找最佳流量和最小成本路線時,均需面對多次迭代分析網(wǎng)絡(luò)的挑戰(zhàn)。在此過程中,它們會逐一分析網(wǎng)絡(luò)連接狀態(tài),包括哪些是開放的,哪些是關(guān)閉的,或是由於達(dá)到容量極限而擁塞的。
此前,計算機(jī)科學(xué)家在解決這一問題時,往往要在兩種關(guān)鍵策略之間做出選擇。一種是以鐵路網(wǎng)絡(luò)為模型,每次迭代都要計算整個網(wǎng)絡(luò)部分並調(diào)整交通流量﹔另一種則受電網(wǎng)中電力流啟發(fā),在每次迭代中計算整個網(wǎng)絡(luò),但對網(wǎng)絡(luò)每個部分的修改流量使用統(tǒng)計平均值,以加快計算速度。
現(xiàn)在,研究團(tuán)隊將這兩種策略的優(yōu)勢結(jié)合,創(chuàng)建了一種全新的組合方法。新算法基於許多小型、高效且低成本的計算步驟,這些步驟加在一起比一些單一的大型步驟快得多。
計算最優(yōu)流量的時間復(fù)雜度通常以m的某個冪次方來表達(dá),其中m代表計算機(jī)必須計算的網(wǎng)絡(luò)中的連接數(shù)。直到2000年,都沒有任何算法的計算速度能夠超過m1.5。2004年,解決該問題所需的計算速度成功降低至m1.33。
新算法進(jìn)一步解決了這一問題。使用該算法時,計算時間和網(wǎng)絡(luò)規(guī)模以相同的速度增加,這或?qū)⒏淖冋麄€網(wǎng)絡(luò)流算法研究領(lǐng)域。(記者張佳欣)
分享讓更多人看到