计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
7期
242-245,289
,共5页
最短路径%多权值图%双向搜索%长路径
最短路徑%多權值圖%雙嚮搜索%長路徑
최단로경%다권치도%쌍향수색%장로경
Shortest path%Multi-cost graph%Bidirectional search%Long path
求解最短路径是图研究中的一个经典问题.目前大多数相关研究都假设图中每条边只有一种权值.然而在实际应用中,有时候图中的边设有多种权值,求解最短路时需要综合计算多种权值,并采用用户自定义的聚合函数f将路径的多种权值映射到一个实数上,用以比较路径的长短.当f不是线性函数时,最短路的子路不一定也是最短路,于是大部分求解最短路的算法对此问题并不适用.文中提出了一种双向搜索方法,用以在多权值路网中求解最短路近似解.实验表明,本方法适用于长路径查询.与单向搜索相比,该方法有较高的运行效率.与基于Dijkstra算法的贪心算法相比,该方法有较高的准确率.
求解最短路徑是圖研究中的一箇經典問題.目前大多數相關研究都假設圖中每條邊隻有一種權值.然而在實際應用中,有時候圖中的邊設有多種權值,求解最短路時需要綜閤計算多種權值,併採用用戶自定義的聚閤函數f將路徑的多種權值映射到一箇實數上,用以比較路徑的長短.噹f不是線性函數時,最短路的子路不一定也是最短路,于是大部分求解最短路的算法對此問題併不適用.文中提齣瞭一種雙嚮搜索方法,用以在多權值路網中求解最短路近似解.實驗錶明,本方法適用于長路徑查詢.與單嚮搜索相比,該方法有較高的運行效率.與基于Dijkstra算法的貪心算法相比,該方法有較高的準確率.
구해최단로경시도연구중적일개경전문제.목전대다수상관연구도가설도중매조변지유일충권치.연이재실제응용중,유시후도중적변설유다충권치,구해최단로시수요종합계산다충권치,병채용용호자정의적취합함수f장로경적다충권치영사도일개실수상,용이비교로경적장단.당f불시선성함수시,최단로적자로불일정야시최단로,우시대부분구해최단로적산법대차문제병불괄용.문중제출료일충쌍향수색방법,용이재다권치로망중구해최단로근사해.실험표명,본방법괄용우장로경사순.여단향수색상비,해방법유교고적운행효솔.여기우Dijkstra산법적탐심산법상비,해방법유교고적준학솔.
