历史路径算法

‘壹’ 路径的运算方法有几种

题主没有说明路径的算法具体指哪种？比较常规的话，比举个例子来说，a到b有三种途径，b到c有四种途径。提问，从a到c有几种路径可以走？那么这种题目需要用乘法，因为
从a到b
有四种。选择从b到c有三种选择，所以每次都有
不同的选择
，需要用乘法那应该是3×4等于12所以从a到c有12种路径。

‘贰’ 百度地图的路径搜索算法

这个还是要问程序猿，现在比较流行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

‘叁’ 历史年代及世纪的算法 （比如算哪个朝代

历史年代及世纪的算法。（比如算哪个朝代距今多少年？）
我们现在一般是用公元纪年法，此纪年法就有公元前和公元后之分，耶稣基督出生那年是公元元年，这年之前的就叫公元前，这年后就叫公元后，简称公元。
这就像数学上的数轴一样，原点左边为负数，右边为正数。算时间的方法也和负数的加减法一样，有三种情况。
第一、计算的年代都为公元前，就用绝对值大的减去小的（如，算公元前211年与公元前118年相隔几年，就可以用211减去118年等于3） ；
第二、计算的时间一个是公元前，一个是公元后，就用公元后减去公元前（如，算公元前209年与公元100年相隔几年，就可以用100减去—209等于309年）；
第三、时间都为公元，就比较好算了，也是用大的减去小的。

‘肆’ 算法问题：如何遍历所有路径

//全排列问题吧？
//递归算法
#include <iostream>

using namespace std;

const int MAX=10;

int a[MAX];

long long ans=0;

int noIn(int b,int k)
{
for(int i=0;i<k;i++)
if(a[i]==b)
return 0;
return 1;
}

void print()
{
/*for(int i=0;i<MAX;i++)
cout<<a[i]+1;
cout<<endl; */
ans++;
}

void search(int k)
{
if(k>=MAX)
{print();return;}

for(int i=0;i<MAX;i++)
if(noIn(i,k))
{
a[k]=i;
search(k+1);
}
}

int main()
{
search(0);
cout<<ans<<endl;
system("pause");
}
//非递归算法
#include <iostream>

using namespace std;

const int MAX=9;

int a[MAX]={0};

long long ans=0;

void print()
{
/*for(int i=0;i<MAX;i++)
cout<<a[i];
cout<<endl;*/
ans++;
}

int noIn(int b,int k)
{
for(int i=0;i<k;i++)
if(a[i]==b)
return 0;
return 1;
}

void search(int k)
{
while(k>=0)
{
a[k]++;
if(a[k]>MAX)
k--;
else
{
if(noIn(a[k],k))
{
k++;a[k]=0;
if(k>=MAX)
{print();k--;}
}
}
}
}

int main()
{
search(0);
cout<<ans<<endl;
system("pause");
}

‘伍’ 历史年代及世纪的算法 ,（比如算哪个朝代距今多少年。......）

我们现在一般是用公元纪年法，此纪年法就有公元前和公元后之分，耶稣基督出生那年是公元元年，这年之前的就叫公元前，这年后就叫公元后简称公元。这就像数学上的数轴一样，原点左边为负数，右边为正数！算时间的方法也和负数的加减法一样有三种情况，第一、计算的年代都为公元前，就用绝对值大的减去小的（如，算公元前211年与公元前118年相隔几年，就可以用211减去118年等于3）
；第二、计算的时间一个是公元前，一个是公元后，就用公元后减去公元前（如，算公元前209年与公元100年相隔几年，就可以用100减去—209等于309年）；第三、时间都为公元就比较好算了，也是用大的减去小的！

‘陆’ 最短路径问题5种类型

最短路径问题5种类型有Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，

扩展知识：

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：
Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，本文主要介绍其中的三种。
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
算法具体的形式包括：确定起点的最短路径问题：即已知起始结点，求最短路径的问题。
确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

‘柒’ 最短路径法如何计算

最短路径算法有三种，Floyd，dijkstra，Bellman_Ford。其中，Floyd适合用于计算每两点间的路径，dijkstra适合稀疏图，bellman则适合稠密图中的已知起点终点，计算最短路径的问题。时间复杂度，floyd算法为n立方，dijk为n平方，bellman为n平方，其中n是点数。dijk可用堆维护，时间复杂度可减至nlogn，而bellman可用队列维护，此方法于1994年被国人提出，命名比较土鳖叫SPFA(shortest path faster algorithm。。。)。至于如何计算，有了名字，搜一下就ok。

‘捌’ 求离散里面哈米尔顿图的最短路径的算法

本程序参考了风云的最短路径代码( http://member.nease.com/~cloudwu)，
并加以改进和优化：
1、把原来用于存放已处理节点的堆栈改为(store_queue)队列，这样在从
sort_queue队列出列时可直接放入store_queue中。
2、解除了地图大小的限制(如果有64K内存限制时，地图大小只能是180x180)
3、删除了原程序中的一些冗余，见程序中的注释。
4、程序继续使用dis_map数组保存各点历史历史最佳距离，也包含了某点是否已经
经过的信息，虽然这样做可能会比使用链表多用一些内存，但是在搜索时可以
节省不时间。
5、程序更具有实用性，可直接或修改后运用于你的程序中，但请你使用该代码后
应该返回一些信息给我，如算法的改进或使用于什么程序等。
本程序可以用Borland C++或DJGPP编译，并附带有一个数据文件 map.dat,
保存有地图的数据，（注：该地图文件格式与风云的原代码的地图格式不一样）
算法描述：
findpath()
{
把S点加入树根（各点所在的树的高度表示从S点到该点所走过的步数）；
把S点加入排序队列（按该点到E点的距离排序+走过的步数从小到大排序）；
1、排序队列sort_queue中距离最小的第一个点出列，并保存入store_queue中
2、从出列的点出发，分别向4个（或8个）方向中的一个各走出一步
3、并估算第2步所走到位置到目标点的距离，并把该位置加入树，
最后把该点按距离从小到大排序后并放入队列中。(由trytile函数实现)。
4、如果该点从四个方向上都不能移动，则把该点从store_queue中删除
5、回到第一点，直到找到E点则结束
从目标点回溯树，直到树根则可以找到最佳路径，并保存在path[]中
}
-------------------------------------------------------------------------*/
//#define NDEBUG
#include <stdio.h>
#include <conio.h>
#include <assert.h>
#include <stdlib.h>
#include <mem.h>

#define tile_num(x,y) ((y)*map_w+(x)) //将 x,y 坐标转换为地图上块的编号
#define tile_x(n) ((n)%map_w) //由块编号得出 x,y 坐标
#define tile_y(n) ((n)/map_w)

#define MAPMAXSIZE 180 //地图面积最大为 180x180，如果没有64K内存限制可以更大
#define MAXINT 32767

//树结构, 比较特殊, 是从叶节点向根节点反向链接，方便从叶节点找到根节点
typedef struct tree_node *TREE;

struct tree_node {
int h; //节点所在的高度，表示从起始点到该节点所有的步数
int tile; //该节点的位置
TREE father; //该节点的上一步
};

//链接结构，用于保存处理过的和没有处理过的结点
typedef struct link_node *LINK;

struct link_node {
TREE node;
int f;
LINK next;
};

LINK sort_queue; // 保存没有处理的行走方法的节点
LINK store_queue; // 保存已经处理过的节点 (搜索完后释放)

unsigned char * map; //地图数据
unsigned int * dis_map; //保存搜索路径时,中间目标地最优解

int map_w,map_h; //地图宽和高
int start_x,start_y,end_x,end_y; //地点,终点坐标

// 初始化队列
void init_queue(void)
{
sort_queue=(LINK)malloc(sizeof(*sort_queue));
sort_queue->node=NULL;
sort_queue->f=-1;
sort_queue->next=(LINK)malloc(sizeof(*sort_queue));
sort_queue->next->node=NULL;
sort_queue->next->f=MAXINT;
sort_queue->next->next=NULL;

store_queue=(LINK)malloc(sizeof(*store_queue));
store_queue->node=NULL;
store_queue->f=-1;
store_queue->next=NULL;
}

// 待处理节点入队列, 依靠对目的地估价距离插入排序
void enter_queue(TREE node,int f)
{
LINK p=sort_queue,father,q;
while(f>p->f) {
father=p;
p=p->next;
assert(p);
}
q=(LINK)malloc(sizeof(*q));
assert(sort_queue);
q->f=f,q->node=node,q->next=p;
father->next=q;
}

// 将离目的地估计最近的方案出队列
TREE get_from_queue(void)
{
LINK bestchoice=sort_queue->next;
LINK next=sort_queue->next->next;
sort_queue->next=next;

bestchoice->next=store_queue->next;

Top

3 楼keikei007（keikei）回复于 2004-06-21 19:16:02 得分 0
store_queue->next=bestchoice;
return bestchoice->node;
}

// 释放栈顶节点
void pop_stack(void)
{
LINK s=store_queue->next;
assert(s);
store_queue->next=store_queue->next->next;
free(s->node);
free(s);
}

// 释放申请过的所有节点
void freetree(void)
{
int i;
LINK p;
while(store_queue){
p=store_queue;
free(p->node);
store_queue=store_queue->next;
free(p);
}
while (sort_queue) {
p=sort_queue;
free(p->node);
sort_queue=sort_queue->next;
free(p);
}
}

// 估价函数,估价 x,y 到目的地的距离,估计值必须保证比实际值小
int judge(int x,int y)
{
int distance;
distance=abs(end_x-x)+abs(end_y-y);
return distance;
}

// 尝试下一步移动到 x,y 可行否
int trytile(int x,int y,TREE father)
{
TREE p=father;
int h;
if (map[tile_num(x,y)]!=' ') return 1; // 如果 (x,y) 处是障碍,失败
//这一步用来判断(x,y)点是否已经加入队列，多余可以删除，因为dis_map已经
//保存该点是否已经保存
//while (p) {
// if (x==tile_x(p->tile) && y==tile_y(p->tile)) return 1; //如果 (x,y) 曾经经过,失
败
// p=p->father;
//}
h=father->h+1;
if (h>=dis_map[tile_num(x,y)]) return 1; // 如果曾经有更好的方案移动到 (x,y) 失败
dis_map[tile_num(x,y)]=h; // 记录这次到 (x,y) 的距离为历史最佳距离

// 将这步方案记入待处理队列
p=(TREE)malloc(sizeof(*p));
p->father=father;
p->h=father->h+1;
p->tile=tile_num(x,y);
enter_queue(p,p->h+judge(x,y));
return 0;
}

// 路径寻找主函数
int * findpath(void)
{
TREE root;
int i,j;
int * path;
memset(dis_map,0xff,map_h*map_w*sizeof(*dis_map)); //填充dis_map为0XFF，表示各点未
曾经过
init_queue();
root=(TREE)malloc(sizeof(*root));
root->tile=tile_num(start_x,start_y);
root->h=0;
root->father=NULL;
enter_queue(root,judge(start_x,start_y));
for (;;) {
int x,y,child;
TREE p;
root=get_from_queue();
if (root==NULL) {
return NULL;
}
x=tile_x(root->tile);
y=tile_y(root->tile);
gotoxy(x+1,y+1);
putchar('\'');
if (x==end_x && y==end_y) break; // 达到目的地成功返回

child=trytile(x,y-1,root); //尝试向上移动
child&=trytile(x,y+1,root); //尝试向下移动
child&=trytile(x-1,y,root); //尝试向左移动
child&=trytile(x+1,y,root); //尝试向右移动
//child&=trytile(x+1,y-1,root);//尝试向右上移动
//child&=trytile(x+1,y+1,root); //尝试向右下移动
//child&=trytile(x-1,y+1,root); //尝试向左下移动
//child&=trytile(x-1,y-1,root); //尝试向左上移动

if (child!=0)
pop_stack(); // 如果四个方向均不能移动,释放这个死节点
}

// 回溯树，将求出的最佳路径保存在 path[] 中
path=(int*)malloc((root->h+2)*sizeof(int));
assert(path);
for (i=0;root;i++) {
path[i]=root->tile;
root=root->father;
}
path[i]=-1;
freetree();
return path;
}

void printpath(int *path)
{
int i;
if(path==NULL) return ;
for (i=0;path[i]>=0;i++) {
gotoxy(tile_x(path[i])+1,tile_y(path[i])+1);
cprintf(".");
}
}

int readmap(void)
{
FILE *f;
int i,j;
f=fopen("map.dat","r");
assert(f);
fscanf(f,"%d,%d\n",&map_w,&map_h);
map=malloc(map_w*map_h+1);
assert(map);
for(i=0;i<map_h;i++)
fgets(map+tile_num(0,i),map_w+2,f);
fclose(f);
start_x=-1,end_x=-1;
for (i=0;i<map_h;i++)
for (j=0;j<map_w;j++) {
if (map[tile_num(j,i)]=='s') map[tile_num(j,i)]=' ',start_x=j,start_y=i;
if (map[tile_num(j,i)]=='e') map[tile_num(j,i)]=' ',end_x=j,end_y=i;
}
assert(start_x>=0 && end_x>=0);
dis_map=malloc(map_w*map_h*sizeof(*dis_map));
assert(dis_map);
return 0;
}

void showmap(void)
{
int i,j;
clrscr();
for (i=0;i<map_h;i++) {
gotoxy(1,i+1);
for (j=0;j<map_w;j++)
if (map[tile_num(j,i)]!=' ') cprintf("O");
else cprintf(" ");
}
gotoxy(start_x+1,start_y+1);
cprintf("s");
gotoxy(end_x+1,end_y+1);
cprintf("e");
}

int main()
{
int * path;
readmap();
showmap();
getch();
path=findpath();
printpath(path);
if(dis_map) free(dis_map);
if(path) free(path);
if(map) free(map);
getch();
return 0;
}

‘玖’ 什么是路径搜索算法

举个例子你大概就明白了，假设从上海东方明珠电视塔到北京天安门有N条线路，可以上海-天津-北京，上海-南京-北京，上海-广州-西藏-北京等等等，选择一条需要的线路这就是路径搜索，用来实现该选择的算法是路径搜索算法，可以选择最短路径，关键路径，如果有费用（权值）就可以选择最便宜路径（权最小），如果有路径需用时（飞机、火车，有些地方只有单一交通工具）就可以选择时间最短路径
用于计算机中的路径搜索就比较广泛了，但大体就是根据上述情况变化来得