演算法走地圖
『壹』 如果人物地圖都是按格子來的，那麼可以用A星演算法自動尋路，如果路徑跟地圖都不是格子的，怎麼自動尋路，手
這個不行，尋路可能要遍歷到整個地圖，所以定幾個特殊點沒法得出路徑的。
『貳』 百度地圖的路徑搜索演算法
這個還是要問程序猿，現在比較流行A*演算法，至於網路是否開發出了新的演算法不得而知，畢竟沒有完全相同的程序。
給你看一篇文獻：
地圖中最短路徑的搜索演算法研究
學生:李小坤 導師：董巒
摘要：目前為止, 國內外大量專家學者對「最短路徑問題」進行了深入的研究。本文通過理論分析, 結合實際應用，從各個方面較系統的比較廣度優先搜索演算法(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
『叄』 按鍵精靈a星演算法尋路怎麼製作地圖
你可以查找有關a星演算法走路，一步步去學，別人也不知道你說的是什麼地圖，怎麼判斷
『肆』 求隨機地圖的演算法
問題的關鍵是你要用這地圖來作什麼，以及需要用什麼數據結構表示地圖
如果說你需要上面的「圖片」本身，那拿來好像沒什麼用處
如果說需要作為游戲的地圖，那數據結構是真正重要的東西，地圖的形式只是一堆坐標即可，沒必要渲染成圖片（或者說渲染是游戲主體的任務，不在地圖生成器范圍）
『伍』 數據結構：用什麼演算法可以走出迷宮
演算法應該很多的，循環的，遞歸的，還有用棧的我有兩個可以看看，第一個是網路上下的，後面的是我自己編的和修改的
1.
//////////////////////////////////////////////////////////////////////
//文件名 :Maze.cpp
//功能 : 線性表的應用——迷宮求解
//創建 : 2007.6.20
//修改日期 : 2007.6.20
//作者 :
////////////////////////////////////////////////////////////////////////
#include <windows.h>
#include <iostream>
#include <stdio.h>
#include<time.h>
//#include "format.h"
//#include "stack.h"
using namespace std;
#define OK 0
#define ERR -1
#define UP '↑' //用於存儲方向的常量
#define DOWN '↓'
#define LEFT '→'
#define RIGHT '←'
#define Rank 20
#define File 63
#define Rand 16
char Maze[Rank][File]; //定義存儲迷宮用的字元型二維數組
char mark=1; //標記
char Bar=2; //地圖
char Player=12; //游戲者
typedef struct SNode
{
int data;
struct SNode *next;
}SNode;
typedef struct
{
int length;
SNode *top;
}STACK;
void InitStack(STACK *S)
{
S->top=NULL;
S->length=0;
}
/*元素e入棧*/
int Push(STACK *S,int e)
{
SNode *p;
p=new SNode[sizeof(SNode)];
if(!p) return ERR;
p->data=e;
p->next=S->top;
S->top=p;
S->length++;
return OK;
}
/*棧頂元素出棧,e帶回棧頂元數*/
int Pop(STACK *S,int *e)
{
SNode *p;
if(S->top==NULL) return ERR;
p=S->top;
*e=p->data;
S->top=p->next;
S->length--;
delete p;
return OK;
}
/*判斷S是否為空棧*/
int Empty(STACK S)
{
if(S.top==NULL) return OK;
return ERR;
}
void ShowMaze();
void InitMaze();
void RunMaze();
int main()
{
int i=1;
system("color 1E");
while(i==1)
{
RunMaze();
cout<<"\t\t 『選擇：Prsss 1：再來一次 Else：退出程序』\n";
cin>>i;
}
return 0;
}
void ShowMaze()
{
int i,j;
system("cls");
cout<<"\n\t\t\t 『迷 宮 求 解』"<<"\n";
cout<<"\t\t 『注:"<<Player<<"為游戲者"<<Bar<<"為地圖障礙"<<mark<<"為所留印記』"<<endl;
for(i=0;i<Rank;i++)
{
cout<<"\t"<<Bar;
for(j=0;j<File;j++)
cout<<Maze[i][j];
cout<<Bar<<"\n";
}
}
void InitMaze()
{
int i,j;
for(i=0;i<Rank;i++)
for(j=0;j<File;j++)
Maze[i][j]=Bar;
srand((unsigned)time(NULL));
int n;
cout<<"請輸入數字選圖";
cin>>n;
for(i=1;i<Rank-1;i++) //for開始
for(j=1;j<File;j++)
{
//n=rand()%Rand; //隨機函數
//if(n<Rand*2/3) Maze[i][j]=' ';
if (((n^i+4*j^3))%11!=5)Maze[i][j]=' ';
} //for結束
Maze[1][0]=' '; //給迷宮留入口
Maze[1][1]=' ';
Maze[1][2]=' ';
Maze[1][3]=' ';
Maze[Rank-2][File-4]=' '; //給迷宮留出口
Maze[Rank-2][File-3]=' ';
Maze[Rank-2][File-2]=' ';
Maze[Rank-2][File-1]=' ';
}
void RunMaze()
{
int path,i=1,j=0,speed=0;
time_t Start,End;
STACK S; //定義一個用於存儲走過的路線的棧
time(&Start);
InitMaze(); //隨機成生迷宮
InitStack(&S); //初始化棧
Maze[1][0]=Player; //初始化位置
ShowMaze(); //顯示迷宮
cout<<"\n\t\t\t『請選擇速度:1 快速 2 較慢 』"<<endl;
while(speed!=1 && speed!=2) cin>>speed;
while(i>=0 && i<Rank && j>=0 && j<File)//開始遍歷迷宮
{
ShowMaze(); //顯示迷宮
if(speed==2) //選擇2較慢時進入空循環延時
Sleep(100);
if(i==Rank-2&&j==File-1) //判斷是否到達出口
{
time(&End);
cout<<"\n\t\t『恭喜成功走出!所用的步數為:"<<S.length<<" 所用時間："<<End-Start<<" 秒』"<<endl;
return;
}
if(Maze[i][j+1]==' ') //向右走一步
{
char dir=26;
Maze[i][j]=dir;
j=j+1;
Maze[i][j]=Player;
Push(&S,RIGHT);
}
else
{
if(Maze[i+1][j]==' ') //向下走一步
{
char dir=25;
Maze[i][j]=dir;
i=i+1;
Maze[i][j]=Player;
Push(&S,DOWN);
}
else
{
if(Maze[i-1][j]==' ') //向上走一步
{
char dir=24;
Maze[i][j]=dir;
i=i-1;
Maze[i][j]=Player;
Push(&S,UP);
}
else
{
if(Maze[i][j-1]==' ') //向左走一步
{
char dir=27;
Maze[i][j]=dir;
j=j-1;
Maze[i][j]=Player;
Push(&S,LEFT);
}
else //遇到障礙往回走一步
{
if(Empty(S)==OK) //判斷是否回到起點了,是則退出程序
{
time(&End);
cout<<"\n\t\t\t『迷宮沒有出路! 所用時間："<<End-Start<<"秒』\n";
return;
}
else
{
if(Pop(&S,&path)==OK) //判斷能否取回上一步路徑
{
switch(path)
{
case LEFT:
Maze[i][j]=mark;
j=j+1;
Maze[i][j]=Player;
break;
case UP:
Maze[i][j]=mark;
i=i+1;
Maze[i][j]=Player;
break;
case DOWN:
Maze[i][j]=mark;
i=i-1;
Maze[i][j]=Player;
break;
case RIGHT:
Maze[i][j]=mark;
j=j-1;
Maze[i][j]=Player;
break;
} //結束分支語句switch
} //結束判斷能否取回上一步路徑
}
}
}
}
}
} //結束while循環
}
第二個。
#include <windows.h>
#include <iostream>
#include <stdio.h>
#include<time.h>
//#include "format.h"
//#include "stack.h"
using namespace std;
//#define OK 0
//#define ERR -1
//#define UP '↑' //用於存儲方向的常量
//#define DOWN '↓'
//#define LEFT '→'
//#define RIGHT '←'
#define Rank 17
#define File 63
#define Rand 16
char Maze[Rank][File]; //定義存儲迷宮用的字元型二維數組
char mark=1; //標記
char Bar=2; //地圖
char Player=12; //游戲者
void ShowMaze();
void InitMaze();
void RunMaze();
int main()
{
int i=1;
system("color 1E");
while(i==1)
{
RunMaze();
cout<<"\t\t 『選擇：Prsss 1：再來一次 Else：退出程序』\n";
cin>>i;
}
return 0;
}
void ShowMaze()
{
int i,j;
system("cls");
cout<<"\n\t\t\t 『迷 宮 求 解』"<<"\n";
cout<<"\t\t 『注:"<<Player<<"為游戲者"<<Bar<<"為地圖障礙"<<mark<<"為所留印記』"<<endl;
for(i=0;i<Rank;i++)
{
cout<<"\t"<<Bar;
for(j=0;j<File;j++)
cout<<Maze[i][j];
cout<<Bar<<"\n";
}
}
void InitMaze()
{
int i,j;
for(i=0;i<Rank;i++)
for(j=0;j<File;j++)
Maze[i][j]=Bar;
srand((unsigned)time(NULL));
int n=5;
cout<<"請輸入數字選圖";
cin>>n;
for(i=1;i<Rank-1;i++) //for開始
for(j=1;j<File;j++)
{
//n=rand()%Rand; //隨機函數
//if(n<Rand*2/3) Maze[i][j]=' ';
if (((n^i+4*j^3))%5!=1)Maze[i][j]=' ';
} //for結束
Maze[1][0]=' '; //給迷宮留入口
Maze[1][1]=' ';
Maze[1][2]=' ';
Maze[1][3]=' ';
Maze[Rank-2][File-4]=' '; //給迷宮留出口
Maze[Rank-2][File-3]=' ';
Maze[Rank-2][File-2]=' ';
Maze[Rank-2][File-1]=' ';
}
void RunMaze()
{ int a=2;
int i=1,j=1,speed=0;
time_t Start,End;
//STACK S; //定義一個用於存儲走過的路線的棧
time(&Start);
InitMaze(); //隨機成生迷宮
//InitStack(&S); //初始化棧
//Maze[1][0]=Player; //初始化位置
ShowMaze(); //顯示迷宮
cout<<"\n\t\t\t『請選擇速度:1 快速 2 較慢 』"<<endl;
while(speed!=1 && speed!=2) cin>>speed;
while(i>=0 && i<Rank && j>=0 && j<File)//開始遍歷迷宮
{
ShowMaze(); //顯示迷宮
if(speed==2) //選擇2較慢時進入空循環延時
Sleep(100);
if(i==Rank-2&&j==File-1) //判斷是否到達出口
{
time(&End);
cout<<"\n\t\t『恭喜成功走出!"<<" 所用時間："<<End-Start<<" 秒』"<<endl;
return ;
}
else
{
switch(a)
{
case 1:if (Maze[i-1][j]==' '||Maze[i-1][j]==26)
{i=i-1;
a=-2;
Maze[i][j]=26;
break;
}
else
if (Maze[i][j+1]==' '||Maze[i][j+1]==26)
{j=j+1;
a=1;
Maze[i][j]=26;
break;
}else
if (Maze[i+1][j]==' '||Maze[i+1][j]==26)
//if(Maze[i+1]][j]==' '||Maze[i+1][j]==26)
{i=i+1;
a=2;
Maze[i][j]=26;
break;
}
else
{
Maze[i][j]=26;
a=-a;
break;
}
case 2:if(Maze[i][j+1]==' '||Maze[i][j+1]==26)
{
j=j+1;
a=1;
Maze[i][j]=26;
break;
}
else
if(Maze[i+1][j]==' '||Maze[i+1][j]==26)
{
i=i+1;
a=2;
Maze[i][j]=26;
break;
}
else
if(Maze[i][j-1]==' '||Maze[i][j-1]==26)
{
j=j-1;
a=-1;
Maze[i][j]=26;
break;
}
else
{
Maze[i][j]=26;
a=-a;
break;
}
case -1:if (Maze[i+1][j]==' '||Maze[i+1][j]==26)
{i=i+1;
a=2;
Maze[i][j]=26;
break;
}
else
if (Maze[i][j-1]==' '||Maze[i][j-1]==26)
{j=j-1;
a=-1;
Maze[i][j]=26;
break;
}
else
if (Maze[i-1][j]==' '||Maze[i-1][j]==26)
{i=i-1;
a=-2;
Maze[i][j]=26;
break;
}
else
{
a=-a;
Maze[i][j]=26;
break;
}
case -2:if (Maze[i][j-1]==' '||Maze[i][j-1]==26)
{j=j-1;
a=-1;
Maze[i][j]=26;
break;
}
else
if (Maze[i-1][j]==' '||Maze[i-1][j]==26)
{i=i-1;
a=-2;
Maze[i][j]=26;
break;
}
else
if (Maze[i][j+1]==' '||Maze[i][j+1]==26)
{j=j+1;
a=1;
Maze[i][j]=26;
break;
}
else
{
Maze[i][j]=26;
a=-a;
break;
}
}
if (i==1&&j==1)
{
time(&End);
cout<<"迷宮沒有出路"<<"所用時間"<<End-Start<<endl;
return;
}
}
} //結束while循環
}
『陸』 vb人物走地圖
你問的是能不能，答案是能。這種只涉及演算法的問題都有解決辦法。
無論你是什麼迷宮通道，都有個邊界地圖，這個邊界地圖的構成必須是數據地圖（就是01010101那樣的，0代表可以走，1代表是牆）
即使你是要IMAGE地圖，你首先要把這個圖像轉換稱為數據地圖，要麼你在設計這個迷宮圖案的時候就創立了自己的數據地圖，要麼你用更復雜的辦法來做自動生成數據地圖。
『柒』 求一個戰棋游戲的六邊形地圖尋路演算法(AS3實現)
樓上的都講完了，我也沒啥好說的，拿走兩分好了
『捌』 地圖演算法
自己想
『玖』 演算法 地圖上如何搜索一個點附近的點
這個還是要問程序猿，現在比較流行A*演算法，至於網路是否開發出了新的演算法不得而知，畢竟沒有完全相同的程序。
給你看一篇文獻：
地圖中最短路徑的搜索演算法研究
學生:李小坤 導師：董巒
摘要：目前為止, 國內外大量專家學者對「最短路徑問題」進行了深入的研究。本文通過理論分析, 結合實際應用，從各個方面較系統的比較廣度優先搜索演算法(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]其過程簡要來說是沿著頂點的鄰點一直搜索下去，直到當前被搜索的頂點不再有未被訪問的鄰點為止，此時，從當前輩搜索的頂點原路返回到在它之前被搜索的訪問的頂點，並以此頂點作為當前被搜索頂點。繼續這樣的過程，直至不能執行為止。
『拾』 gps地圖如何導航編輯為你揭秘導航演算法
4.1 地圖匹配問題介紹
利用車載GPS接收機實時獲得車輛軌跡，進而確定其在交通矢量地圖道路上的位置，是當前車載導航系統的基礎。獨立GPS車載導航系統中克服GPS誤差以及地圖誤差顯示車輛在道路網上的位置主要是通過地圖匹配演算法，也就是根據GPS信號中的數據和地圖道路網信息，利用幾何方法、概率統計方法、模式識別
或者人工神經網路等技術將車輛位置匹配到地圖道路上的相應位置 [8-12]。由於行駛中的車輛絕大部分都是在道路上的，所以通常的地圖演算法都有一個車輛在道路上的默認前提。地圖匹配的准確性決定了
GPS車輛導航系統的准確性、實時性與可靠性。具體來說取決於兩方面：確定當前車輛正在行駛的路段的准確性與確定車輛在行駛路段上的位置的准確性。前者是現有演算法的研究重點，而後者涉及到沿道路方向的誤差校正，在現有演算法中還沒有得以有效解決。地圖匹配的目標是將軌跡匹配到道路上，當道路是准確的時，也就成了確定GPS的准確位置，然後利用垂直映射方法完成匹配。要實時獲得車輛所在的道路及位置通過地圖匹配來實現是一種比較普遍而且成本較低的方法。車輛導航與定位系統中的地圖匹配問題概括來講就是將車載GPS接收機獲得的帶有誤差的GPS軌跡位置匹配到帶有誤差的交通矢量地圖道路上的相應位置。下面我們通過具體的數學模型來給地圖匹配問題以詳細的數學描述。
地圖匹配的基本過程如圖4.1所示。符號定義及其物理意義說明如下：
1) g(k)是車輛GPS軌跡點，內容為k時刻車輛上的GPS定位數據（經緯度），對應於矢量地圖上相應的經緯度位置點。由於GPS誤差和矢量地圖誤差的存在，當車輛在道路弧段Si 上行駛時，g(k)通常並不位於弧段Si 上。
2) p(k )為g(k)的地圖道路匹配點，表示地圖匹配演算法對g(k)進行偏差修正獲得的車輛k時刻在矢量地圖道路上的對應點，簡稱g(k)的匹配點。匹配點所在矢量地圖弧段Si上的位置，應該盡可能反映出實際車輛在該段道路上的相應位置。
3) e(k)為g(k)的地圖匹配修正量，表示g(k)與其匹配點p(k)間的誤差修正。需要指明匹配點所在的弧段p(k) .Si 時，使用符號e(k)[Si ] 表示g(k)對於弧段Si 上的匹配點所使用的匹配修正量。上述3個基本量之間的關系如圖畫所示，即p(k) = g(k) + e(k) (4)
地圖匹配修正量e(k)源自於GPS定位誤差和交通矢量地圖精度誤差的綜合誤差效應。