迷宮尋路演算法
㈠ 數據結構演算法 用C++ 迷宮最短路徑
一般迷宮尋路可以用遞歸的演算法，或者用先進後出的棧數據結構實現
用的是深度優先的演算法，可以尋找到走出迷宮的路徑
但本題要求求出最短的路徑，這就要使用廣度優先的演算法
一般在程序中需要用到先進先出的隊列數據結構
下面是程序的代碼，主要原理是用到
quei，quej和prep三個數組來構成隊列
分別儲存路徑的行，列坐標和上一個節點在隊列中的位置
大致演算法如下，右三個嵌套的循環實現
首先是第一個節點進入隊列
當隊列不空（循環1）
｛
遍歷隊列中每節點(循環2）
｛
將八個方向能夠走的節點加入隊列（循環3）
｝
舊的節點出列
｝
#include<iostream>
#include<ctime>
usingnamespacestd;
#defineMAXNUM50
voidmain()
{
intm,n,i,j,x;
cout<<"請輸入迷宮大小"<<endl;
cin>>m>>n;
intmaze[MAXNUM][MAXNUM];
srand((int)time(NULL));
for(i=0;i<=m+1;i++){
for(j=0;j<=n+1;j++){
if(i==0||j==0||i==m+1||j==n+1)
maze[i][j]=1;
else
{
x=rand()%1000;
if(x>700){maze[i][j]=1;}//控制矩陣中1的個數，太多1迷宮很容易走不通
else{maze[i][j]=0;}
}
cout<<maze[i][j]<<'';
}
cout<<endl;
}
//以上是輸入和迷宮生成，一下是走迷宮
intmove[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
int*quei=newint[m*n];//儲存行坐標隊列
int*quej=newint[m*n];//儲存列坐標隊列
int*prep=newint[m*n];//儲存之前一步在隊列中的位置
inthead,rear,length;//隊列頭，隊列尾，隊列長度
head=0;rear=1;length=1;
quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置進隊列
intpos;//當前節點在隊列中的位置，
intii,jj,ni,nj;//當前節點的坐標，新節點的坐標
intdir;//移動方向
if(maze[1][1]==1)length=0;//第一點就不能通過
elsemaze[1][1]=1;
while(length)//隊列非空繼續
{
for(pos=head;pos<head+length;pos++)//尋找這一層所有節點
{
ii=quei[pos];jj=quej[pos];//當前位置坐標
if(ii==m&&jj==n)break;
for(dir=0;dir<8;dir++)//尋找8個方向
{
ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐標
if(maze[ni][nj]==0)//如果沒有走過
{
quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新節點入隊
rear=rear+1;
maze[ni][nj]=1;//標記已經走過
}
}
}
if(ii==m&&jj==n)break;
head=head+length;
length=rear-head;//這一層節點出列
}
if(ii==m&&jj==n)
{
while(pos!=-1)
{
cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
pos=prep[pos];
if(pos!=-1)cout<<',';
}
}
else
{
cout<<"THEREISNOPATH."<<endl;
}
delete[]quei;
delete[]quej;
delete[]prep;
}
㈡ 求廣度優先演算法C++走迷宮程序，可以顯示路徑
一般迷宮尋路可以用遞歸的演算法，或者用先進後出的棧數據結構實現
用的是深度優先的演算法，可以尋找到走出迷宮的路徑
但本題要求求出最短的路徑，這就要使用廣度優先的演算法
一般在程序中需要用到先進先出的隊列數據結構
下面是程序的代碼，主要原理是用到
quei，quej和prep三個數組來構成隊列
分別儲存路徑的行，列坐標和上一個節點在隊列中的位置
大致演算法如下，右三個嵌套的循環實現
首先是第一個節點進入隊列
當隊列不空（循環1）
｛
遍歷隊列中每節點(循環2）
｛
將八個方向能夠走的節點加入隊列（循環3）
｝
舊的節點出列
｝
#include<iostream>
#include<ctime>
usingnamespacestd;
#defineMAXNUM50
voidmain()
{
intm,n,i,j,x;
cout<<"請輸入迷宮大小"<<endl;
cin>>m>>n;
intmaze[MAXNUM][MAXNUM];
srand((int)time(NULL));
for(i=0;i<=m+1;i++){
for(j=0;j<=n+1;j++){
if(i==0||j==0||i==m+1||j==n+1)
maze[i][j]=1;
else
{
x=rand()%1000;
if(x>700){maze[i][j]=1;}//控制矩陣中1的個數，太多1迷宮很容易走不通
else{maze[i][j]=0;}
}
cout<<maze[i][j]<<'';
}
cout<<endl;
}
//以上是輸入和迷宮生成，一下是走迷宮
intmove[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
int*quei=newint[m*n];//儲存行坐標隊列
int*quej=newint[m*n];//儲存列坐標隊列
int*prep=newint[m*n];//儲存之前一步在隊列中的位置
inthead,rear,length;//隊列頭，隊列尾，隊列長度
head=0;rear=1;length=1;
quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置進隊列
intpos;//當前節點在隊列中的位置，
intii,jj,ni,nj;//當前節點的坐標，新節點的坐標
intdir;//移動方向
if(maze[1][1]==1)length=0;//第一點就不能通過
elsemaze[1][1]=1;
while(length)//隊列非空繼續
{
for(pos=head;pos<head+length;pos++)//尋找這一層所有節點
{
ii=quei[pos];jj=quej[pos];//當前位置坐標
if(ii==m&&jj==n)break;
for(dir=0;dir<8;dir++)//尋找8個方向
{
ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐標
if(maze[ni][nj]==0)//如果沒有走過
{
quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新節點入隊
rear=rear+1;
maze[ni][nj]=1;//標記已經走過
}
}
}
if(ii==m&&jj==n)break;
head=head+length;
length=rear-head;//這一層節點出列
}
if(ii==m&&jj==n)
{
while(pos!=-1)
{
cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
pos=prep[pos];
if(pos!=-1)cout<<',';
}
}
else
{
cout<<"THEREISNOPATH."<<endl;
}
delete[]quei;
delete[]quej;
delete[]prep;
}
㈢ A*path與Dijkstra尋路、迷宮生成
假設有人想從 A 點移動到一牆之隔的 B 點，如下圖，綠色的是起點 A，紅色是終點 B，藍色方塊是中間的牆。
在 A*尋路演算法中，我們通過從綠色起點 A 開始，檢查相鄰方格的方式，向外擴展直到找到目標。
我們做如下操作開始搜索：
通常對於方格節點，我們認為水平/垂直移動一格耗費為 10，對角線移動耗費為 14。
G = 從 起點 沿著生成的路徑，移動到當前節點的總移動耗費。
H = 從當前節點移動到 終點 的移動耗費估算。這經常被稱為啟發式的，因為它只是個猜測，我們沒辦法事先知道路徑的實際長度。
對於方格節點通常使用 曼哈頓方法 ，它計算從當前格到 終點 之間水平和垂直的方格的數量總和，忽略對角線方向和障礙物。然後把結果乘以水平/垂直的移動耗費。
對於允許走對角線的節點使用 對角線方法 ，允許任意走的節點使用 歐幾里得方法
當H值總為0時，退化為Dijkstra尋路演算法
先構建一個如下的模型圖,其中黑色為牆壁,紅色為路徑節點。牆可以為一個方形格子也可以僅僅是一條線(為方格時對角線上的牆壁始終無法被打通)。
先構建一個除了外圈為黑色牆壁,內部全是灰色通路的迷宮模型
㈣ 【尋路】A星演算法淺析
**A*演算法：智能尋路的導航燈**
在尋找最優路徑的眾多演算法中，A*演算法憑借其高效性和實用性脫穎而出。它巧妙地結合了Dijkstra演算法的精確性和Greedy Best First Search的效率，為我們解決復雜地圖上的路徑問題提供了有力工具。讓我們一起探索A*演算法的精髓，看看它是如何在迷宮中指引我們前進的。
**1. A*演算法的基礎原理**
A*演算法的關鍵在於引入了一個啟發式函數H，它代表從當前節點到目標節點的預估距離。與Dijkstra演算法的純距離計算不同，A*演算法考慮了目標節點的直接可達性，通過計算每個節點的F值（G + H，G為從起點到當前節點的實際代價，H為預估目標距離）來決定搜索路徑。
**2. 與BFS和Dijkstra的對比**
- BFS（廣度優先搜索）是盲目搜索，不考慮未來路徑的成本，A*則是深度優先搜索的優化，通過啟發式函數避免了不必要的探索。
- Dijkstra演算法雖然找到的是最短路徑，但時間復雜度較高。A*在保證路徑效率的同時，尋求的是更短路徑，特別是當目標節點位置信息可用時。
**3. A*演算法的偽代碼**
A*的搜索過程如下：
- 將起始節點加入開放列表，F值最小的節點優先處理。
- 選擇F值最小的節點，如果它是目標節點，搜索結束；否則，將其所有鄰居節點加入開放列表，更新它們的F值。
- 重復步驟3，直到找到目標節點或者開放列表為空。
**4. 實現細節與優化**
- 使用優先隊列（如二叉堆）存儲節點，便於快速訪問F值最小的節點。
- 在計算F值時，檢查斜線路徑，利用曼哈頓距離或歐幾里得距離（視情況而定）。
- 判斷直接通行的節點，避免重復搜索。
- 對路徑進行平滑處理，提升視覺效果。
- 設計多級尋路系統，應對復雜環境中的路徑選擇。
**5. A*與B*與JPS的異同**
- B*演算法更偏向於目標導向，可能會在目標附近產生較寬的探索范圍。
- JPS（Jump Point Search）在A*的基礎上，通過尋找跳躍點加速搜索，尤其在大量障礙物中表現優秀。
通過A*演算法，我們能夠在游戲、機器人導航、實時路徑規劃等領域找到最短或較短的路徑，它的靈活性和效率使得它成為現代計算機科學中的瑰寶。理解並掌握A*演算法，就像擁有了一把智慧的鑰匙，能幫助我們在迷宮般的現實世界中輕松尋路。
㈤ C++ DFS演算法實現走迷宮自動尋路
深度優先搜索（DFS）是一種遍歷圖或搜索樹的演算法。它的基本思想是從樹或圖的根節點開始，盡可能地深入到樹的某一分支中。當無法繼續向下探索時，回溯並嘗試其他分支。DFS演算法在圖或樹的遍歷中非常常用，但在迷宮問題中同樣適用。
在迷宮問題中，DFS演算法用於尋找從起點到終點的路徑。通過深度優先搜索，我們可以探索每個可能的路徑，直至找到通向目標的路線。
實現此演算法的代碼展示了手動操控與自動尋路兩種模式。手動模式允許用戶逐步探索迷宮，而自動模式則自動尋找並顯示從起點到終點的路徑。
程序的靈活性在於，只需調整迷宮地圖的二維數組和相關常量，即可改變地圖大小。自動尋路功能同樣可用。
理論上，DFS演算法在任何大小和復雜度的迷宮中都能有效尋找路徑。然而，這種演算法採用遞歸實現，導致空間佔用較大。當迷宮地圖增大到一定程度，如20*20，可能會觸發堆棧溢出異常。因此，程序中提供了18*18和15*15的迷宮地圖用於測試。
編譯環境為Windows VS2019。該演算法的代碼包含游戲類（Game.h）和主函數文件（迷宮.cpp），並提供了一定的調試支持。如果您在使用過程中發現任何問題，歡迎指出，感謝您對本項目的貢獻。