一种基于图嵌入的在道路网络中查找最优路径的方法

摘要

本发明属于空间数据库技术领域，具体涉及一种道路网络中查找最优路径的方法。该方法的步骤为：给定路网中的n个属性的点集合M1、M2、…、Mn，以及一个起点s和一个终点t，以s为起点，根据图嵌入框架提供的上下界，以迭代查找最近邻的方法找出贪心路径Rg；然后按顺序遍历n个属性的点集合M1、M2、…、Mn，以贪心路径的长度为上界，结合上下界对存在的路径进行剪枝；最后对剩下的候选路径进行精确计算，找出最优路径。通过本发明的基于图嵌入的查找方法，大大减小了搜索空间，因而有更高的查找效率。