计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2011年
z2期
728-734
,共7页
空间数据库%道路网络%最优路径查询%多属性最近邻查询
空間數據庫%道路網絡%最優路徑查詢%多屬性最近鄰查詢
공간수거고%도로망락%최우로경사순%다속성최근린사순
研究了道路网络中一项重要的查询:最优路径查询(optimal sequenced route query,OSRQ).给定路网中的n个属性的点集合M1,M2,…,Mn以及一个起点s和一个终点t,最优路径查询返回一条最短的路径P,其中P起始于s,依次经过M1,M2,…,Mn每个集合中的至少一个点,最终到达终点t.路网中的最优路径查询在现实生活中经常用到,例如,某用户从学校出发,想依次经过一个加油站、一个银行、一个餐馆,最后回家,最优路径查询会根据要求返回一条最短的路径.提出了一种基于图嵌入框架的最优路径查询算法EOSRA.EOSRA利用图嵌入框架所提供的2点之间最短路径长度的上下界,对存在的路径进行了剪枝,大大减少了最优路径的搜索空间,最后对剩下的候选路径进行精确计算,将最短的路径返回给用户.实验结果表明EOSRA比现有的算法响应时间更小,性能更优.
研究瞭道路網絡中一項重要的查詢:最優路徑查詢(optimal sequenced route query,OSRQ).給定路網中的n箇屬性的點集閤M1,M2,…,Mn以及一箇起點s和一箇終點t,最優路徑查詢返迴一條最短的路徑P,其中P起始于s,依次經過M1,M2,…,Mn每箇集閤中的至少一箇點,最終到達終點t.路網中的最優路徑查詢在現實生活中經常用到,例如,某用戶從學校齣髮,想依次經過一箇加油站、一箇銀行、一箇餐館,最後迴傢,最優路徑查詢會根據要求返迴一條最短的路徑.提齣瞭一種基于圖嵌入框架的最優路徑查詢算法EOSRA.EOSRA利用圖嵌入框架所提供的2點之間最短路徑長度的上下界,對存在的路徑進行瞭剪枝,大大減少瞭最優路徑的搜索空間,最後對剩下的候選路徑進行精確計算,將最短的路徑返迴給用戶.實驗結果錶明EOSRA比現有的算法響應時間更小,性能更優.
연구료도로망락중일항중요적사순:최우로경사순(optimal sequenced route query,OSRQ).급정로망중적n개속성적점집합M1,M2,…,Mn이급일개기점s화일개종점t,최우로경사순반회일조최단적로경P,기중P기시우s,의차경과M1,M2,…,Mn매개집합중적지소일개점,최종도체종점t.로망중적최우로경사순재현실생활중경상용도,례여,모용호종학교출발,상의차경과일개가유참、일개은행、일개찬관,최후회가,최우로경사순회근거요구반회일조최단적로경.제출료일충기우도감입광가적최우로경사순산법EOSRA.EOSRA이용도감입광가소제공적2점지간최단로경장도적상하계,대존재적로경진행료전지,대대감소료최우로경적수색공간,최후대잉하적후선로경진행정학계산,장최단적로경반회급용호.실험결과표명EOSRA비현유적산법향응시간경소,성능경우.
