中文摘要：

研究了道路网络中一项重要的查询:最优路径查询(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比现有的算法响应时间更小,性能更优.