百度地图的路径搜索算法
我给你看一份文件:
地图最短路径搜索算法研究
学生:李导师:董銮
摘要:到目前为止，国内外大量的专家学者对“最短路径问题”进行了深入的研究。通过理论分析和实际应用，从各个方面系统地比较了广度优先搜索算法(BFS)、深度优先搜索算法(DFS)和A*算法的优缺点。
关键词:最短路径算法；广度优先搜索；深度优先算法；A*算法；
地图最短路径搜索算法
摘要:迄今为止，国内外大量专家学者对“最短路径问题”进行了深入的研究。本文通过理论分析和实际应用，从系统的任何方面对广度优先搜索算法(BFS)、深度优先搜索算法(DFS)和A *算法进行了研究。
关键词:最短路径算法；广度优先算法；算法；A *算法；
前言:
最短路径问题是地理信息系统(GIS)网络分析的重要内容之一，在图论中也具有重要意义。现实生活中的许多问题都与“最短路径问题”有关，如网络路由、集成电路设计、布线问题、电子导航、交通和旅游等。本文应用深度优先算法、广度优先搜索算法和A*算法对一个具体问题进行了讨论和分析，并比较了三种算法的优缺点。
在地图最短路径搜索算法的研究中，各种算法优缺点的比较原则主要遵循以下三点:[1]
(1)算法的完备性:提出一个问题，这个问题有一个答案，算法可以保证找到对应的答案。算法的完备性是算法性能的优秀指标之一。
(2)算法的时间复杂度:问一个问题，算法需要多长时间找到对应的答案。算法的速度是算法优劣的重要体现。
(3)算法的空间复杂度:算法在搜索问题答案时需要多大的存储空间？算法占用的资源越少，算法的性能越好。
地图中最短路径的搜索算法:
1，广度优先搜索
广度优先搜索，也称为宽度优先搜索或横向优先搜索，是最简单的图搜索算法之一，该算法也是许多重要图算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了类似宽度优先搜索的思想。广度优先搜索(width-first-search)的别名是BFS，属于一种盲搜索方法，旨在系统地展开并检查图中的所有节点以找到结果。换句话说，它彻底搜索整个图，而不考虑结果的可能地址，直到找到结果。BFS不使用经验法则算法。
广度优先搜索算法的伪代码如下:[2-3]
BFS(v)//广度优先搜索G，从顶点v开始
//所有搜索到的顶点I都标记为已访问(i)=1。
//Visited//的初始组件值都是0。
已访问(v)= 1；
q =[]；//将Q初始化为只有一个元素v的队列。
当Q不为空时
u = del head(Q)；
For与u的所有顶点w do相邻。
如果已访问(w)=0，则
AddQ(w，Q)；//将W放在队列q的末尾。
已访问(w)= 1；
endif
结束
结束时间
结束BFS
这里调用了两个函数:AddQ(w，Q)将w放在队列Q的末尾；DelHead(Q)从队列Q中取出第一个顶点，并将其从Q中删除。重复DelHead(Q)过程，直到队列Q为空。
完备性:广度优先搜索算法完备。这意味着无论哪种图形，只要目标存在，BFS就一定会找到它。然而，如果目标不存在，并且图是无限的，则BFS不会收敛(不会结束)。
时间复杂度:在最坏的情况下，BFS必须找到到可能节点的所有路径，所以它的时间复杂度是，其中|V|是图中节点的数量，|E|是图中边的数量。
空间复杂度:因为必须存储所有节点，所以BFS的空间复杂度为，其中|V|是图中节点的数量，而|E|是图中边的数量。另一种说法是BFS的空间复杂度是O(B)，其中B是树的最大分支系数，m是树的最长路径长度。由于对空间的巨大需求，BFS不适合解决非常大的问题。[4-5]
2.深度优先算法
深度优先搜索，英文缩写为DFS，属于回溯算法。就像算法的名字一样，深度优先搜索所遵循的搜索策略是尽可能深地搜索图。[6]简而言之，过程就是沿着顶点的邻点进行搜索，直到当前搜索到的顶点没有未被访问过的邻点。此时，前任搜索到的顶点的原始路径返回到其之前搜索到的访问过的顶点，并将该顶点作为当前搜索到的顶点。继续这个过程，直到不能执行为止。
深度优先搜索算法的伪代码如下:[7]
DFS(v) //访问v到达的所有顶点。
已访问(v)= 1；
For与v的每个顶点w do相邻。
如果已访问(w)=0，则
DFS(w)；
endif
结束
结束DFS
作为一种搜索算法，DFS在寻找解决NP(包括NPC)问题的方法中起着重要的作用。然而，搜索算法的时间复杂度是O(n！)，其效率相对较低，当数据规模变大时，这种算法就显得力不从心了。[8]深度优先搜索的效率问题有很多解决方案。最通用的是剪枝，也就是去掉无用的搜索分支。可行剪枝和最优剪枝两种。
BFS:对解决最短或最少问题特别有效，搜索深度小，但缺点是内存消耗大(需要打开大量数组单元格来存储状态)。
DFS:对于解决所有的遍历和寻找问题都是有效的，在问题搜索深度较小时速度很快，深度较大时效率很低。
3.A*算法
1968的一篇论文，“P. E .哈特，N. J .尼尔森和b .拉斐尔。启发式确定图中最小费用路径的形式基础。IEEE Trans。系统。Sci。还有控制论，SSC-4(2):100-107，1968 .[9]此后，一种巧妙而高效的算法——a*算法问世，并被广泛应用于相关领域。A*算法实际上是在宽度优先搜索的基础上引入了一个评价函数。它不是一次展开所有可展开的节点，而是利用评价函数对所有未展开的节点进行评价，从而找出最应该展开的节点并展开，直到找到目标节点。
A*算法主搜索过程的伪代码如下:[10]
创建两个表，打开的表保存所有已经生成但没有调查的节点，关闭的表记录已经访问过的节点。
计算起点的估计值；
将起点放入打开的表中；
而(开！=NULL) //从打开的表中取估计值f最小的节点n；
If(n节点= =目标节点)break
endif
For(当前节点n的每个子节点x)
计算x的估计值；
如果(X打开)
if(x的估计值小于开表的估计值)
把n设为x的父亲；
更新开放表中的估计值；//取最小路径的估计值；
endif
endif
如果(X包括在内)
if(x的估计值小于CLOSE表的估计值)
把n设为x的父亲；
更新结算表中的估计值；
将X节点放入OPEN //中，得到最小路径的估计值。
endif
endif
如果(X不在路径中)
把n设为x的父亲；
求x的估计值；
并将x插入到打开的表中；//尚未排序
endif
结束于
在关闭表中插入n个节点；
根据估计值对开放表中的节点进行排序；//其实就是比较开放表中节点F的大小，从路径最短的节点向下进行。
end while(打开！=空)
保存路径，即从终点开始，每个节点沿着父节点移动，直到起点，这就是你的路径；
A *算法分析:
DFS和BFS在扩展子节点时都属于盲搜索，即不会在下一次搜索中选择哪个节点更好，而跳转到那个节点进行下一次搜索。在运气不好的情况下，需要探索整个解集空间，显然，它只能应用于搜索小规模的问题。A*算法与DFS、BFS等盲搜索的最大区别在于，当前搜索节点选择下一个节点时，可以通过一个启发式函数进行选择，选择代价最小的节点作为下一个搜索节点，并在其上跳转。【11】a*算法是利用对问题的理解和对问题求解过程的理解，寻求一些有利于问题求解的启发式信息，从而利用这些启发式信息来搜索最优路径。它不需要遍历整个地图，而是在每一步根据启发式函数在某个方向进行搜索。当地图较大且复杂时，其计算复杂度远优于D ijks tr a算法。这是一种搜索速度非常快、效率高的算法。但是，相应的A*算法也有其不足之处。启发式信息是人为添加的，主观性很大，直接依赖于操作人员的经验。不同的情况使用不同的启发信息和启发函数，它们的选择比较困难，很大程度上找不到最优路径。
总结:
本文描述了最短路径算法的一些步骤，总结了每种算法的一些优缺点，以及算法之间的一些关系。对于BFS或者DFS来说，虽然好用，但是由于时间和空间的限制，只能解决小规模的问题，而BFS应该用于最短或者最少的问题，而DFS应该在遍历和解决所有问题的时候使用。至于A*算法，是一种启发式搜索算法，也是一种最优优先级算法。适用于小规模、大规模和超大规模问题，但启发式搜索算法主观性很大，其质量取决于程序员的经验和选择的启发式函数，所以用A*算法写出一个优秀的程序相对困难。每种算法都有自己的优缺点。针对不同的问题选择合理的算法是最好的方法。
参考资料:
[1]陈，滕，，陈清华。四种最短路径算法的案例分析[J].计算机知识与技术(学术交流)，2007(16):1030-1032
阴，阴。图的最短路径算法及其在网络中的应用[J].软件指南，2011(07):51-53。
刘文海，徐荣聪。几种最短路径的算法及比较[J].福建计算机，2008(02):9-12。
邓春燕。两种最短路径算法的比较[J].计算机知识与技术，2008(12):511-513
王苏南，魏松人，江文胜人。最短路径算法的比较[J].系统工程与电子，1994 (05): 43-49。
许、李天智。求解所有最短路径的算法[J].计算机工程与科学，2006 (12): 83-84
李，刘润涛。一种基于Dijkstra的最短路径算法[J].哈尔滨理工大学学报，2008 (03): 35-37
许道。一种求最短路径的新算法[J].计算机工程与科学，2006(02)。
[9]颜春申。一种改进的基于图的深度优先算法和Dijkstra算法的警察巡逻程序[J].2010电气工程与自动控制国际会议，2010(3) : 73-77
[10]布松雅VC++实现基于Dijkstra算法的最短路径[J].科技信息(科学教学与研究)，2008 (18): 36-37
杨，王，马。一种最短路径分析优化算法的实现[J].吉林大学学报(信息科学版)，2002 (02): 70-74