歷史路徑演算法
『壹』 路徑的運算方法有幾種
題主沒有說明路徑的演算法具體指哪種？比較常規的話，比舉個例子來說，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條線路，可以上海-天津-北京，上海-南京-北京，上海-廣州-西藏-北京等等等，選擇一條需要的線路這就是路徑搜索，用來實現該選擇的演算法是路徑搜索演算法，可以選擇最短路徑，關鍵路徑，如果有費用（權值）就可以選擇最便宜路徑（權最小），如果有路徑需用時（飛機、火車，有些地方只有單一交通工具）就可以選擇時間最短路徑
用於計算機中的路徑搜索就比較廣泛了，但大體就是根據上述情況變化來得