计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2015年
5期
1246-1249
,共4页
最大流%增广链%增广链修复%NW小世界网络%BA无标度网络
最大流%增廣鏈%增廣鏈脩複%NW小世界網絡%BA無標度網絡
최대류%증엄련%증엄련수복%NW소세계망락%BA무표도망락
maximum flow%augmenting path%augmenting path restoration%NW small-world network%BA scale-free network
NW小世界网络及BA无标度网络是现实中常见的两种网络,这两种网络中任意两点之间有极大可能存在多条路径,若舍弃饱和增广链并重新寻找增广链,则效率不高,因此针对网络的这一特性提出了一种增广链修复的最大流求解算法.该算法沿最短增广链调整流量后,保留路径上残余的非饱和弧,并用贪心法则选择合适的中继节点修复断开的增广链,提高增广链使用效率.通过对NW小世界网络和BA无标度网络建模仿真,得到并验证了所提算法在这两种网络上的运行速度数倍于Ford-Fulkerson算法且其空间复杂度仅有Dinic算法的一半,因此所提算法能够高效处理更大规模网络流问题,以适应日益膨胀的通信网络和交通运输网络.
NW小世界網絡及BA無標度網絡是現實中常見的兩種網絡,這兩種網絡中任意兩點之間有極大可能存在多條路徑,若捨棄飽和增廣鏈併重新尋找增廣鏈,則效率不高,因此針對網絡的這一特性提齣瞭一種增廣鏈脩複的最大流求解算法.該算法沿最短增廣鏈調整流量後,保留路徑上殘餘的非飽和弧,併用貪心法則選擇閤適的中繼節點脩複斷開的增廣鏈,提高增廣鏈使用效率.通過對NW小世界網絡和BA無標度網絡建模倣真,得到併驗證瞭所提算法在這兩種網絡上的運行速度數倍于Ford-Fulkerson算法且其空間複雜度僅有Dinic算法的一半,因此所提算法能夠高效處理更大規模網絡流問題,以適應日益膨脹的通信網絡和交通運輸網絡.
NW소세계망락급BA무표도망락시현실중상견적량충망락,저량충망락중임의량점지간유겁대가능존재다조로경,약사기포화증엄련병중신심조증엄련,칙효솔불고,인차침대망락적저일특성제출료일충증엄련수복적최대류구해산법.해산법연최단증엄련조정류량후,보류로경상잔여적비포화호,병용탐심법칙선택합괄적중계절점수복단개적증엄련,제고증엄련사용효솔.통과대NW소세계망락화BA무표도망락건모방진,득도병험증료소제산법재저량충망락상적운행속도수배우Ford-Fulkerson산법차기공간복잡도부유Dinic산법적일반,인차소제산법능구고효처리경대규모망락류문제,이괄응일익팽창적통신망락화교통운수망락.
