南京理工大学学报（自然科学版）
南京理工大學學報（自然科學版）
남경리공대학학보（자연과학판）
JOURNAL OF NANJING UNIVERSITY OF SCIENCE AND TECHNOLOGY
2011年
6期
749-754
,共6页
多约束%最优路径%多弧权网络%路径算法%启发式搜索
多約束%最優路徑%多弧權網絡%路徑算法%啟髮式搜索
다약속%최우로경%다호권망락%로경산법%계발식수색
针对多弧权网络路径寻优及其效率问题,提出了4种多约束最优路径算法,并对其进行了比较研究.基于经典Dijkstra算法,提出了多约束最优路径问题的D_MCOP算法；引入启发式搜索思想,设计了A*_MCOP算法和迭代加深搜索的IDA*_MCOP算法；为克服IDA* _MCOP算法每次迭代都要回到起始节点重新搜索的缺陷,提出了一种多约束边沿搜索算法——Fringe_MCOP算法.实例研究表明:三种启发式搜索算法扩展的节点数、边数以及算法的执行时间都远小于D_MCOP算法,而且Fringe_MCOP算法在三种启发式算法中性能最优；当给定的约束条件与最优路径的权值向量越接近时,算法的执行效率越高,当网络规模较大时,这一趋势更加明显；当约束条件过于严格而得不到满足约束条件的路径时,A*_MCOP和Fringe_MCOP的算法速度比IDA*_MCOP的算法速度更快,D_MCOP的算法速度最慢.
針對多弧權網絡路徑尋優及其效率問題,提齣瞭4種多約束最優路徑算法,併對其進行瞭比較研究.基于經典Dijkstra算法,提齣瞭多約束最優路徑問題的D_MCOP算法；引入啟髮式搜索思想,設計瞭A*_MCOP算法和迭代加深搜索的IDA*_MCOP算法；為剋服IDA* _MCOP算法每次迭代都要迴到起始節點重新搜索的缺陷,提齣瞭一種多約束邊沿搜索算法——Fringe_MCOP算法.實例研究錶明:三種啟髮式搜索算法擴展的節點數、邊數以及算法的執行時間都遠小于D_MCOP算法,而且Fringe_MCOP算法在三種啟髮式算法中性能最優；噹給定的約束條件與最優路徑的權值嚮量越接近時,算法的執行效率越高,噹網絡規模較大時,這一趨勢更加明顯；噹約束條件過于嚴格而得不到滿足約束條件的路徑時,A*_MCOP和Fringe_MCOP的算法速度比IDA*_MCOP的算法速度更快,D_MCOP的算法速度最慢.
침대다호권망락로경심우급기효솔문제,제출료4충다약속최우로경산법,병대기진행료비교연구.기우경전Dijkstra산법,제출료다약속최우로경문제적D_MCOP산법；인입계발식수색사상,설계료A*_MCOP산법화질대가심수색적IDA*_MCOP산법；위극복IDA* _MCOP산법매차질대도요회도기시절점중신수색적결함,제출료일충다약속변연수색산법——Fringe_MCOP산법.실례연구표명:삼충계발식수색산법확전적절점수、변수이급산법적집행시간도원소우D_MCOP산법,이차Fringe_MCOP산법재삼충계발식산법중성능최우；당급정적약속조건여최우로경적권치향량월접근시,산법적집행효솔월고,당망락규모교대시,저일추세경가명현；당약속조건과우엄격이득불도만족약속조건적로경시,A*_MCOP화Fringe_MCOP적산법속도비IDA*_MCOP적산법속도경쾌,D_MCOP적산법속도최만.
