法律状态公告日
法律状态信息
法律状态
2015-01-21
授权
授权
2014-01-08
实质审查的生效 IPC(主分类):G01S19/39 申请日:20130906
实质审查的生效
2013-12-11
公开
公开
技术领域
本发明属于计算机网络领域,具体涉及一种K最短路径搜索方法,并将其应用于GPS导航设备中。
背景技术
路径搜索问题一般可以通过图论中的最短路径方法解决。常用的最短路方法有Dijkstra、广度优先方法等经典方法。然而这些方法只能寻找图中给定点到任意点间的最短路径。这在实践中往往是不够的,比如,在GPS导航中,除了最短路径外,可能需要寻找第二短路径备用,甚至在某些条件下,可能需要寻找第三、第四短路径。这类问题称为K短路径问题。
与单源最短路径问题相比,K短路径问题在方法设计上更为复杂,目前尚没有一种K短路径方法如单源最短路径方法中的Dijkstra方法一样得到业界共识并且达到大规模实用化程度。
常用的K短路径搜索方法有删除边方法、偏离边方法等。但是这些方法仅仅是一种理论上的模型,在实践应用中还存在问题。
GPS定位系统是指利用卫星,在全球范围内实时进行定位、导航的系统,简称GPS(Global Positioning System)。GPS可以提供车辆定位、防盗、反劫、行驶路线监控及呼叫指挥等功能。由于GPS技术所具有的全天候、高精度和自动测量的特点,作为先进的测量手段和新的生产力,已经融入了国民经济建设、国防建设和社会发展的各个应用领域。
目前已经有很多具有GPS导航功能的终端设备,但是却只能提供最短路径或者满足某种条件的路径,而不能考虑用户在行驶中的其它需求合理给出可供选择的路径。
发明内容
本发明的目的在于提供一种能应用于GPS的快速路径规划方法,该方法应能解决以下几个方面的问题:
(1)可提供限定无环路径的K短路径问题的计算机算法,具有实用性,而非一种纯理论上的算法概念;
(2)给出从源点到目标结点间任意给定数目(即K数)并且以路径长度排序的所有路径;
(3)可将该算法应用于GPS导航中,使得K短路径方法得到实际应用。
为实现以上目标,本发明提出一种应用于GPS的快速K最短路径规划方法,其主要特点,包括以下步骤:
一种应用于GPS的快速K最短路径规划方法,其特征在于,包括以下步骤:
(1)导入地图,并由用户根据GPS确定起始点s和终点t以及相应的K值,其中K是用户期望查找的最短路径数目;
(2)对结点t调用A*算法得到最短路径,定义变量k,令k=1;
(3)递归计算k条最短s-t路径:依次遍历第k条最短路径上各结点的所有为sidetrack edge的入边得到候选路径,并加入集合C,sidetrack edge表示不在最短路径树上的边;
(4)从集合C中取出一条最短路径作为第k+1条最短路径;
(5)判断k,如果路径条数未达到K值,则进入步骤6,否则跳转到步骤7;
(6)判断集合C,如果该集合非空,则返回步骤3,否则进入步骤8;
(7)算法成功结束,返回搜索结果;
(8)算法结束,未找到足够的K条路径,返回搜索结果。
上述技术方案中,所述步骤2中利用A*得到第一条最短路径后A*暂停,且后续步骤中再次调用A*进行结点扩展,在A*的运行过程中,对当前节点的所有出边进行迭代,将位于最短路径树上的边标记为tree edge,不在最短路径树上的边标记为sidetrack edge,对于所有被扩展过的顶点标记其状态为close。
上述技术方案中,所述步骤3中遍历各结点是按照从第k条路径中的最后一个sidetrack edge边的尾结点前向搜索到起始结点,候选路径用sidetrack edge的集合来表示,最后用sidetrack edge表示的路径一一对应地表示为一条常规路径。
上述技术方案中,所述步骤3中依次遍历第k条最短路径上各结点,其方法包括以下步骤:
(4-1)依次遍历当前第k条路径上从最后一条sidetrack edge到起始结点中的所有结点,记为v;
(4-2)依次遍历结点v的所有的sidetrack edge出边,记为e;
(4-3)判断边e的头结点,如果其状态不是close,则重启A*直到e的头结点的状态被标记为close;
(4-4)将e加入到当前路径第k条的末尾,形成一条新的候选路径并计算其长度,加入到集合C中。
上述技术方案中,所述步骤4取出当前集合C中路径长度最短的候选路径作为下一条待处理的路径,候选路径长度为d(t)-d(head(e))+w(e)+d(tail(e))。
上述技术方案中,所述步骤5对K的判断,如果已经达到K值,返回K条最短路径。
上述技术方案中,所述步骤6对C进行判断,集合C如果为空,表示没有候选路径可供选择,算法结束返回不能成功找到K条路径。
上述技术方案中,k为循环变量,每次循环后k++,表示当前已经得到的路径条数。
上述技术方案中,其特征在于步骤1中A*算法包括如下步骤:
(9-1)初始化操作,令集合open为空,将起始结点s设置为close,计算结点s的所有出sidetrack边的f值并入到open集合,其中f值得计算方法为:f(e)=d(tail(e))+w(e)+h(head(e)),函数d(v)表示结点d到初始结点s的最短距离,w(e)表示边e的权值,h(v)表示结点v到目标结点t距离的估计值,tail(e)表示边e的尾结点,head(e)表示边e的头结点;
(9-2)若open集合不为空,进入(9-3),否则跳转到(9-4);
(9-3)从open集合中取出f值最小的一条边,记为e,若head(e)的状态是close,将e标记为sidetrack edge并跳转到步骤2,否则将head(e)设置为close,并计算head(e)的所有出边并将其加入到open集合,若head(e)=目标结点t,跳转到(9-5);
(9-4)返回,找不到结点t;
(9-5)返回,成功找到结点t。
上述技术方案中,递归计算k条最短s-t路径,其步骤如下:
(10-1)设置当前路径π为第一条最短路径,π为由sidetrack edge表示的路径,P(π)为与π相对于的s-t路径,令路径集合C为空;
(10-2)对于路径P(π)中的所有结点,除去t,对于该结点的所有的出sidetrack edge e,若head(e)的状态不是close,重启A*直到e的头结点的状态被标记为close,将e加入到π中形成新路径π*,计算路径π*长度l(π*)=d(t)-d(head(e))+w(e)+d(tail(e)),将路径π*加入集合C;
(10-3)若已经得到K条最短路径,进入(10-7);
(10-4)若C为空,进入(10-6);
(10-5)从集合C中取出一条最短路径作为当前最短路径π,进入(10-2);
(10-6)返回,没找到k条最短路径;
(10-7)返回,成功找到k条最短路径。
本发明具有如下特点:
(1)路径搜索过程中运用了地图数据动态装载特性,提升了搜索速度,降低了算法占用空间;
(2)运用了启发式搜索方法,提高了搜索效率;
(3)采用递归思想提供了一种快速K最短路径规划算法;
(4)将这种快速路径规划算法应用于GPS导航中,提高了该算法的实用性。
附图说明
图1是K短路径快速搜索方法流程图;
图2是A*算法流程图;
图3是应用于GPS的使用流程图。
具体实施方式
下面结合附图以及实施例对本发明作进一步详细描述。
参考图1,为本发明所述K短路径计算机算法流程,结合上面的具体问题分析得如下所述具体步骤:
步骤1:对结点t调用A*算法得到最短路径,定义变量k,令k=1;
步骤2:对于路径P(π)中的所有结点(除去t),对于该结点的所有的出sidetrack edge e,若head(e)的状态不是close,运行A*直到head(e)的状态为close,将e加入到π中形成新路径π*,计算路径π*长度l(π*)=d(t)-d(head(e))+w(e)+d(tail(e)),将路径π*加入集合C;
步骤3:若已经得到K条最短路径,进入步骤7;
步骤4:若C为空则进入步骤6;
步骤5:从集合C中取出一条最短路径作为当前最短路径π,进入步骤2;
步骤6:返回,没找到k条最短路径;
步骤7:返回,成功找到k条最短路径。
根据上面的流程,算法结束后,得到按照路径长度排序的K短路径集。
如上所述步骤1中,对结点调用A*算法也是一个重要的过程,下面对A*作详细描述。
参考图2,为本发明所述A*算法流程,其详细步骤如下:
步骤1:初始化操作。令集合open为空,将起始结点s设置为close,计算结点s的所有出sidetrack边的f值并入到open集合,其中f值得计算方法为:f(e)=d(tail(e))+w(e)+h(head(e)),函数d(v)表示结点d到初始结点s的最短距离,w(e)表示边e的权值,h(v)表示结点v到目标结点t距离的估计值;
步骤2:若open集合不为空,进入步骤3,否则跳到步骤4;
步骤3:从open集合中取出f值最小的一条边,记为e,若head(e)的状态是close,将e标记为sidetrack edge并跳转到步骤2,否则将head(e)设置为close,并计算head(e)的所有出边并将其加入到open集合,若head(e)=目标结点t,跳转到步骤5;
步骤4:返回,找不到结点t;
步骤5:返回,成功找到结点t。
如上所述,运行A*算法将得到从源点到目标点的最短路径,且在K短路径后续步骤中会调用A*对结点进行扩展。每次调用后,得到新的扩展结点集合以及sidetrack edge集合。
参考图3,为本发明所述将K短路径算法应用于GPS的流程,其详细步如下:
步骤1:导航设备导入电子地图,GPS定位当前位置,作为源点;
步骤2:用户输入目的地以及希望找到路径的条数K;
步骤3:运行K短路径算法,得到搜索结果并将结果返回给用户;
步骤4:用户根据搜索得到的结果选取一条便利的路径,GPS开始导航。
如上所述,将K短路径搜索方法应用于GPS中,既扩大了K短路径搜索算法的应用范围,也提高了GPS导航设备的实用性。
机译: 一种自动移动机器人的路径规划方法,该方法利用地图信息,避免特征点之间的障碍以及快速安全地到达下一个特征点的细胞分解方法,通过细胞分解方法形成路径
机译: 清洁机器人及基于清洁机器人的最短路径规划方法
机译: GPS GPS一种为全球定位系统压缩数据的方法,一种为GPS和GPS设备恢复数据的方法