超快網絡流算法問世

瑞士蘇黎世聯邦理工學院的研究人員開發了一種超快算法，即網絡流算法。該算法成功解決了在網絡中實現最大流量的同時最大限度降低傳輸成本的問題。這種超快計算能力是研究高度複雜、數據豐富、動態且快速變化的網絡（例如生物學中的分子網絡或大腦網絡）的重要環節。

　　新算法能為任何類型的網絡（包括鐵路、公路、水上交通和互聯網）計算出最佳且最低成本的交通流量方案。其執行計算的速度極快，幾乎在計算機讀取描述網絡數據的瞬間就能提供解決方案。

　　原則上，所有計算方法在尋找最佳流量和最小成本路線時，均需面對多次迭代分析網絡的挑戰。在此過程中，它們會逐一分析網絡連接狀態，包括哪些是開放的，哪些是關閉的，或是由於達到容量極限而擁塞的。

　　此前，計算機科學家在解決這一問題時，往往要在兩種關鍵策略之間做出選擇。一種是以鐵路網絡為模型，每次迭代都要計算整個網絡部分並調整交通流量；另一種則受電網中電力流啟發，在每次迭代中計算整個網絡，但對網絡每個部分的修改流量使用統計平均值，以加快計算速度。

　　現在，研究團隊將這兩種策略的優勢結合，創建了一種全新的組合方法。新算法基於許多小型、高效且低成本的計算步驟，這些步驟加在一起比一些單一的大型步驟快得多。

　　計算最優流量的時間複雜度通常以m的某個冪次方來表達，其中m代表計算機必須計算的網絡中的連接數。直到2000年，都沒有任何算法的計算速度能夠超過m1.5。2004年，解決該問題所需的計算速度成功降低至m1.33。

　　新算法進一步解決了這一問題。使用該算法時，計算時間和網絡規模以相同的速度增加，這或將改變整個網絡流算法研究領域。