算法走地图
‘壹’ 如果人物地图都是按格子来的，那么可以用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定位误差和交通矢量地图精度误差的综合误差效应。