百度地图的路径搜索算法 求大神指点 百度地图API实现批量搜索地点 返回位置
\u6c42\u4e00\u4e2a\u5730\u56fe\u8def\u5f84\u7b97\u6cd5\u7b97\u6cd5\u540d\uff1aA*\u641c\u5bfb\u7b97\u6cd5
\u6211\u7406\u89e3\u7684\uff0c\u4f60\u662f\u8981\u6839\u636e\u5730\u5740\u83b7\u53d6\u5730\u5740\u7684\u7ecf\u7eac\u5ea6\u3002
\u9996\u5148\uff0c\u5206\u6790\u4e00\u4e0b\uff0c\u5730\u5740\u7684\u4e0d\u552f\u4e00\u6027\uff0c\u540c\u4e00\u4e2a\u5730\u5740\u6709\u53ef\u80fd\u4f1a\u83b7\u53d6\u591a\u4e2a\u4f4d\u7f6e\uff0c\u4e5f\u5c31\u662f\u591a\u4e2a\u7ecf\u7eac\u5ea6\u3002\u4f1a\u4ea7\u751f\u591a\u4e2a\u7ed3\u679c\uff0c\u800c\u4ee3\u7801\u672c\u8eab\u53c8\u4e0d\u80fd\u5224\u65ad\u9700\u8981\u7684\u662f\u54ea\u4e2a\uff0c\u6240\u4ee5\u5c31\u8981\u589e\u52a0\u7b97\u6cd5\uff0c\u6765\u533a\u5206\u8981\u7684\u7ed3\u679c\u662f\u4f60\u60f3\u8981\u7684\u7ed3\u679c\u3002
\u601d\u8def\u5c31\u662f\u4e0a\u8fb9\u7684\u601d\u8def\uff0c\u4e0b\u8fb9\u5230\u7f16\u7a0b\u65b9\u9762\uff0c\u7ed9\u4f60\u4e00\u6bb5\u4ee3\u7801\u53bb\u53c2\u8003\uff0c\u70b9\u51fb\u4e0b\u8fb9\u7684\u94fe\u63a5\u3002
http://blog.csdn.net/zhihua_w/article/details/52424395
给你看一篇文献：
地图中最短路径的搜索算法研究
学生:李小坤 导师：董峦
摘要：目前为止, 国内外大量专家学者对“最短路径问题”进行了深入的研究。本文通过理论分析, 结合实际应用，从各个方面较系统的比较广度优先搜索算法(BFS)、深度优先搜索算法(DFS)、A* 算法的优缺点。
关键词:最短路径算法；广度优先算法；深度优先算法；A*算法；
The shortest path of map's search algorithm
Abstract:So far, a large number of domestic and foreign experts and scholars on the" shortest path problem" in-depth study. In this paper, through theoretical analysis and practical application, comprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic.
Key words: shortest path algorithm; breadth-first algorithm; algorithm; A * algorithm;
前言：
最短路径问题是地理信息系统（GIS）网络分析的重要内容之一，而且在图论中也有着重要的意义。实际生活中许多问题都与“最短路径问题”有关, 比如: 网络路由选择, 集成电路设计、布线问题、电子导航、交通旅游等。本文应用深度优先算法，广度优先算法和A*算法，对一具体问题进行讨论和分析，比较三种算的的优缺点。
在地图中最短路径的搜索算法研究中，每种算法的优劣的比较原则主要遵循以下三点:[1]
(1)算法的完全性：提出一个问题，该问题存在答案，该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。
(2)算法的时间复杂性: 提出一个问题，该算法需要多长时间可以找到相应的答案。算法速度的快慢是算法优劣的重要体现。
(3)算法的空间复杂性:算法在执行搜索问题答案的同时，需要多少存储空间。算法占用资源越少，算法的性能越好。
地图中最短路径的搜索算法:
1、广度优先算法
广度优先算法(Breadth-First-Search)，又称作宽度优先搜索，或横向优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型,Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。广度优先算法其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。
广度优先搜索算法伪代码如下：[2-3]
BFS(v)//广度优先搜索G，从顶点v开始执行
//所有已搜索的顶点i都标记为Visited(i)=1.
//Visited的初始分量值全为0
Visited(v)=1;
Q=[];//将Q初始化为只含有一个元素v的队列
while Q not null do
u=DelHead(Q);
for 邻接于u的所有顶点w do
if Visited(w)=0 then
AddQ(w,Q); //将w放于队列Q之尾
Visited(w)=1;
endif
endfor
endwhile
end 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、深度优先算法
深度优先搜索算法（Depth First Search）英文缩写为DFS，属于一种回溯算法，正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。[6]其过程简要来说是沿着顶点的邻点一直搜索下去，直到当前被搜索的顶点不再有未被访问的邻点为止，此时，从当前辈搜索的顶点原路返回到在它之前被搜索的访问的顶点，并以此顶点作为当前被搜索顶点。继续这样的过程，直至不能执行为止。
深度优先搜索算法的伪代码如下：[7]
DFS(v) //访问由v到达的所有顶点
Visited(v)=1;
for邻接于v的每个顶点w do
if Visited(w)=0 then
DFS(w);
endif
endfor
end DFS
作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率比较低，在数据规模变大时，这种算法就显得力不从心了。[8]关于深度优先搜索的效率问题，有多种解决方法。最具有通用性的是剪枝，也就是去除没有用的搜索分支。有可行性剪枝和最优性剪枝两种。
BFS:对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。
DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高。
3、A*算法
1968年的一篇论文，“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”。[9]从此，一种精巧、高效的算法——A*算法问世了，并在相关领域得到了广泛的应用。A* 算法其实是在宽度优先搜索的基础上引入了一个估价函数,每次并不是把所有可扩展的结点展开,而是利用估价函数对所有未展开的结点进行估价, 从而找出最应该被展开的结点,将其展开,直到找到目标节点为止。
A*算法主要搜索过程伪代码如下：[10]
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算起点的估价值;
将起点放入OPEN表;
while(OPEN!=NULL) //从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
endif
for(当前节点n 的每个子节点X)
算X的估价值;
if(X in OPEN)
if(X的估价值小于OPEN表的估价值)
把n设置为X的父亲;
更新OPEN表中的估价值; //取最小路径的估价值;
endif
endif
if(X inCLOSE)
if( X的估价值小于CLOSE表的估价值)
把n设置为X的父亲;
更新CLOSE表中的估价值;
把X节点放入OPEN //取最小路径的估价值
endif
endif
if(X not inboth)
把n设置为X的父亲;
求X的估价值;
并将X插入OPEN表中; //还没有排序
endif
end for
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
end while(OPEN!=NULL)
保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；
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
[2]刘树林,尹玉妹.图的最短路径算法及其在网络中的应用[J].软件导刊,2011(07):51-53
[3]刘文海,徐荣聪.几种最短路径的算法及比较[J].福建电脑，2008(02）:9-12
[4]邓春燕.两种最短路径算法的比较[J].电脑知识与技术，2008（12）：511-513
[5]王苏男,宋伟,姜文生.最短路径算法的比较[J].系统工程与电子技术,1994(05)：43-49
[6]徐凤生,李天志.所有最短路径的求解算法[J].计算机工程与科学,2006(12)：83-84
[7]李臣波,刘润涛.一种基于Dijkstra的最短路径算法[J].哈尔滨理工大学学报,2008(03)：35-37
[8]徐凤生.求最短路径的新算法[J].计算机工程与科学,2006(02).
[9] YanchunShen . An improved Graph-based Depth-First algorithm and Dijkstra algorithm program of police patrol [J] . 2010 International Conference on Electrical Engineering and Automatic Control , 2010(3) : 73-77
[10]部亚松.VC++实现基于Dijkstra算法的最短路径[J].科技信息(科学教研),2008(18)：36-37
[11] 杨长保,王开义,马生忠.一种最短路径分析优化算法的实现[J]. 吉林大学学报(信息科学版),2002(02)：70-74
这个问题，你最好咨询开发这个软件的人~~
绛旓細3. 鐧惧害鍦板浘鐑姏鍥剧殑鍒朵綔姝ラ 鍒朵綔鐑姏鍥剧殑涓昏姝ラ濡備笅锛1锛夊噯澶囨暟鎹細鏍规嵁闇瑕侊紝浠庢湁鍏抽儴闂ㄦ垨鑰呰嚜宸卞凡缁忔嫢鏈夌殑鏁版嵁涓紝鎻愬彇鍑洪渶瑕佺殑鍧愭爣鐐规暟鎹2锛夋暟鎹竻娲楋細瀵瑰凡缁忔彁鍙栧嚭鐨勫潗鏍囨暟鎹愪竴鏍稿锛屽垹鍘婚敊璇暟鎹垨涓嶅畬鏁寸殑鏁版嵁銆3锛夋暟鎹仛鍚堬細浣跨敤鑱氬悎绠楁硶锛屽皢鍧愭爣鐐硅仛鍚堟垚鐢熸垚缃戞牸锛屽苟璁＄畻鍑烘瘡涓綉鏍肩殑鍊笺4...
绛旓細鎯у鑸郴缁熸槸涓绉嶄互闄铻轰华鍜屽姞閫熷害璁′负鎰熺煡鍏冧欢鐨勫鑸弬鏁拌В绠楃郴缁,搴旂敤鑸抗閫掓帹绠楁硶鎻愪緵浣嶇疆銆侀熷害鍜屽Э鎬佺瓑淇℃伅,鍙互璇存槸涓涓敱鎯ф祴閲忓崟鍏冨拰绉垎鍣ㄧ粍鎴愮殑绉垎绯荤粺銆 3銆侀珮绮鍦板浘瀹氫綅 瀵逛簬绂荤嚎鍦板浘,灏嗗叾杞彉涓虹摝鐗囧湴鍥,鎻愬彇杞﹁締鎵鍦ㄤ綅缃懆鍥寸殑鍦板浘淇℃伅骞惰繘琛屼綋绱犲寲,杞彉涓虹鏁ｅ寲鐨勪綋绱犲湴鍥;瀵逛簬杞﹁締琛岄┒杩囩▼涓敹闆...
绛旓細鏈鐭璺緞绠楁硶:FLOYD,DIJKSTRA(蹇呭) 鏈灏忕敓鎴愭爲绠楁硶:PRIM,KRUSKAL(蹇呭) 瀹為檯绠楁硶:鍏抽敭璺緞銆佹嫇鎶栨帓搴(鍘熺悊涓庡簲鐢) 浜屽垎鍥惧尮閰:閰嶅銆佸寛鐗欏埄绠楁硶(鍘熺悊涓庡簲鐢) 鎷撳睍:涓績鎬х畻娉曘佺ぞ鍖哄彂鐜扮畻娉(鍘熺悊涓庡簲鐢) 鎼滅储涓庡洖婧畻娉 璐績绠楁硶(蹇呭) 淇″彂寮鎼滅储绠楁硶:A*瀵昏矾绠楁硶(浜嗚В) 鍦板浘鐫鑹茬畻娉曘丯鐨囧悗闂銆佹渶浼樺姞宸...
绛旓細2銆併鐧惧害鍦板浘銆嬶細鐧惧害鍏徃鎺ㄥ嚭鐨勮繖娆惧鑸蒋浠朵娇鐢ㄤ究鎹凤紝鐢ㄦ埛鍙渶杈撳叆鐩殑鍦板嵆鍙幏寰楀鑸湇鍔°傚畠鑳芥牴鎹敤鎴烽渶姹傛彁渚涙渶蹇嵎鐨勫嚭琛屾柟寮忓拰鏈鐭矾绾匡紝闈炲父浜烘у寲锛屽苟鍏峰瀹炴椂瀵艰埅鍔熻兘銆3銆併婅吘璁湴鍥俱嬶細杩欐杞欢杩愮敤澶ф暟鎹绠楁硶鎻愪緵绮惧噯瀵艰埅鏈嶅姟锛屽疄鏃舵洿鏂拌矾鍐碉紝娣卞彈鐢ㄦ埛淇¤禆銆傚畠鎷ユ湁澶氱鐗硅壊璇煶閫夐」锛屽寘鎷湴鏂...
绛旓細鍥犳鍦ㄥ叿浣撶殑搴旂敤涓紝寰寰闇瑕佹牴鎹Щ鍔ㄨ澶囨墍鍏锋湁鐨勪紶鎰熷櫒缁勫悎銆佽绠楄兘鍔涖佺敤鎴峰満鏅瓑锛岄夋嫨鍜屾繁搴﹀畾鍒跺悎閫傜殑SLAM绠楁硶銆傛瘮濡傦紝鏃犱汉椹鹃┒姹借溅鍜屾墜鏈虹AR绫诲簲鐢ㄧ殑SLAM绠楁硶灏遍潪甯镐笉鍚屻係LAM鐨勫吀鍨嬪簲鐢ㄩ鍩 鏈哄櫒浜哄畾浣嶅鑸鍩燂細鍦板浘寤烘ā銆係LAM鍙互杈呭姪鏈哄櫒浜烘墽琛璺緞瑙勫垝銆佽嚜涓绘帰绱佸鑸瓑浠诲姟銆傚浗鍐呯殑绉戞矁鏂佸绫...
绛旓細鍦板浘鏇存柊閫熷害鏄渶鐩存帴褰卞搷瀵艰埅绮惧噯鎬х殑锛屽挨鍏跺湪澶у煄甯傞噷锛屾瘡澶╂柊淇拰缈诲缓鐨勯亾璺緢澶氾紝鍙婃椂鏇存柊鍦板浘鍙互璁╁鑸蒋浠跺鎵惧埌鏈鏂鐨勮矾寰銆2銆佸疄闄呰矾鍐垫洿鏂拌緝蹇殑鏄珮寰峰拰鐧惧害銆傞珮寰峰拰鐧惧害鐨勭敤鎴疯緝澶氾紝鍦ㄥ疄鏃惰矾鍐电殑閲囬泦涓婂叿澶囦笉閿欑殑浼樺娍锛岄氳繃瑙勯伩鎷ュ牭璺鐨勮璁★紝鑳藉璁╁鑸殑璺緞鏇寸簿鍑嗐3銆璺緞绠楁硶鏈濂界殑鏄...
绛旓細2. 鐧惧害鍦板浘锛氱櫨搴﹀叕鍙告帹鍑虹殑杩欐瀵艰埅杞欢浣跨敤渚挎嵎锛岀敤鎴峰彧闇杈撳叆鐩殑鍦帮紝杞欢灏辫兘鎻愪緵瀵艰埅鏈嶅姟銆傚畠鑳藉鏍规嵁鐢ㄦ埛闇姹傦紝鎻愪緵鏈鏂逛究蹇嵎鐨勫嚭琛屾柟寮忓拰鏈鐭殑鍑鸿璺嚎锛岄潪甯镐汉鎬у寲銆傛澶栵紝鐧惧害鍦板浘杩樺叿澶囧疄鏃跺鑸姛鑳姐3. 鑵捐鍦板浘锛氳繖娆捐蒋浠跺埄鐢ㄥぇ鏁版嵁绠楁硶鎻愪緵绮惧噯鐨勫鑸湇鍔★紝瀹炴椂璺喌鏇存柊锛屾繁鍙楃敤鎴蜂俊璧栥傚畠鎻愪緵...
绛旓細鍏朵粬:璁℃暟鎺掑簭(蹇呭)銆佸笇灏旀帓搴忓骞插崄澶х畻娉曠殑瀛︿範,鍋囧浣犱笉澶ф噦鐨勮瘽,閭ｄ箞鎴戣繕鏄尯鎺ㄨ崘浣犲幓鐪嬩功鐨,鍥犱负鐪嬩簡涔,浣犲彲鑳戒笉浠呬粎鐭ラ亾杩欎釜绠楁硶鎬庝箞鍐,杩樿兘鐭ラ亾浠栨槸鎬庝箞鏉ョ殑銆傛帹鑽愪功绫嶆槸銆婄畻娉曠鍥涚増銆,杩欐湰涔﹁鐨勫緢璇︾粏,鑰屼笖閰嶄簡寰堝鍥炬紨绀,杩樻槸鎸哄ソ鎳傜殑銆 3銆佹悳绱笌鍥炴函绠楁硶 璐績绠楁硶(蹇呭) 鍚彂寮鎼滅储绠楁硶:A*瀵...
绛旓細slam绠楁硶鏄疄鐜版満鍣ㄤ汉瀹氫綅銆佸缓鍥俱璺緞瑙勫垝鐨勪竴绉嶇畻娉曘係LAM鏄悓姝ュ畾浣嶄笌鍦板浘鏋勫缓(Simultaneous Localization And Mapping)鐨勭缉鍐欙紝鏈鏃╃敱Hugh Durrant-Whyte 鍜 John J.Leonard鑷1988骞存彁鍑恒傚叾瀹濻LAM鏇村儚鏄竴涓蹇佃屼笉鏄竴涓畻娉曪紝瀹冩湰韬寘鍚澶氭楠わ紝鍏朵腑鐨勬瘡涓涓楠ゅ潎鍙互浣跨敤涓嶅悓鐨勭畻娉瀹炵幇銆備富瑕...
绛旓細1銆侀鍏堣繘鍏モ鐧惧害鍦板浘鈥,鐐瑰嚮宸︿笂瑙掕嚜宸辩殑澶村儚銆 2銆佸湪鎵鎵撳紑鐨勭晫闈,鏈変竴涓剼涓姸鐨勪笢瑗,閭ｅ氨鏄滆冻杩光濆姛鑳藉暒,鐐瑰嚮鎵撳紑銆 3銆佺劧鍚,鐐瑰嚮鎵撳紑鍙充笅瑙掔殑钃濊壊鍔犲彿銆 4銆佸睍寮鍔犲彿鍚,浼氬嚭鐜颁袱涓鍙枫備竴涓槸瀵艰埅绠ご,鍙︿竴涓槸鑴氫斧銆傝繖閲屾垜浠偣鍑讳笂闈㈢殑鈥滃鑸澶粹濄 5銆佺劧鍚庣偣鍑讳笅鏂圭殑钃濊壊褰曞埗鎸夐挳銆傚紑濮嬭褰曡椹...
