计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2014年
7期
59-61,68
,共4页
路网%最短路径%最近邻
路網%最短路徑%最近鄰
로망%최단로경%최근린
Road network%Shortest path%Nearest neighbour
已有的城市道路网中的最近邻查询算法只考虑离查询者当前位置最近的对象,不能保证相对于即将行驶的路径也是最近的.提出基于最短路径的最近邻查询,给定当前位置和目的地,返回的是到它们之间的最短路径有最小绕道距离的对象.提出基于三阶段的查询算法SFV(Search-filter-verify),利用双向Dijkstra算法得到最短路径的同时,保留有用的距离信息,再利用最小绕道距离的上下界关系过滤掉不可能成为结果的对象,最后精确计算剩余对象的最小绕道距离,得到结果.基于真实城市路网的实验结果表明,SFV与传统算法相比,有较高的性能和良好的扩展性.
已有的城市道路網中的最近鄰查詢算法隻攷慮離查詢者噹前位置最近的對象,不能保證相對于即將行駛的路徑也是最近的.提齣基于最短路徑的最近鄰查詢,給定噹前位置和目的地,返迴的是到它們之間的最短路徑有最小繞道距離的對象.提齣基于三階段的查詢算法SFV(Search-filter-verify),利用雙嚮Dijkstra算法得到最短路徑的同時,保留有用的距離信息,再利用最小繞道距離的上下界關繫過濾掉不可能成為結果的對象,最後精確計算剩餘對象的最小繞道距離,得到結果.基于真實城市路網的實驗結果錶明,SFV與傳統算法相比,有較高的性能和良好的擴展性.
이유적성시도로망중적최근린사순산법지고필리사순자당전위치최근적대상,불능보증상대우즉장행사적로경야시최근적.제출기우최단로경적최근린사순,급정당전위치화목적지,반회적시도타문지간적최단로경유최소요도거리적대상.제출기우삼계단적사순산법SFV(Search-filter-verify),이용쌍향Dijkstra산법득도최단로경적동시,보류유용적거리신식,재이용최소요도거리적상하계관계과려도불가능성위결과적대상,최후정학계산잉여대상적최소요도거리,득도결과.기우진실성시로망적실험결과표명,SFV여전통산법상비,유교고적성능화량호적확전성.
