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