迷宮問題演算法
Python基於遞歸演算法實現的走迷宮問題
本文實例講述了Python基於遞歸演算法實現的走迷宮問題。分享給大家供大家參考，具體如下：
什麼是遞歸?
簡單地理解就是函數調用自身的過程就稱之為遞歸。
什麼時候用到遞歸？
如果一個問題可以表示為更小規模的迭代運算，就可以使用遞歸演算法。
迷宮問題：一個由0或1構成的二維數組中，假設1是可以移動到的點，0是不能移動到的點，如何從數組中間一個值為1的點出發，每一隻能朝上下左右四個方向移動一個單位，當移動到二維數組的邊緣，即可得到問題的解，類似的問題都可以稱為迷宮問題。
在python中可以使用list嵌套表示二維數組。假設一個6*6的迷宮,問題時從該數組坐標[3][3]出發，判斷能不能成功的走出迷宮。
maze=[[1,0,0,1,0,1],
[1,1,1,0,1,0],
[0,0,1,0,1,0],
[0,1,1,1,0,0],
[0,0,0,1,0,0],
[1,0,0,0,0,0]]
針對這個迷宮問題，我們可以使用遞歸的思想很好的解決。對於數組中的一個點，該點的四個方向可以通過橫縱坐標的加減輕松的表示，每當移動的一個可移動的點時候，整個問題又變為和初始狀態一樣的問題，繼續搜索四個方向找可以移動的點，知道移動到數組的邊緣。
所以我們可以這樣編碼：
# 判斷坐標的有效性，如果超出數組邊界或是不滿足值為1的條件，說明該點無效返回False，否則返回True。
def valid(maze,x,y):
if (x>=0 and x<len(maze) and y>=0 and y<len(maze[0]) and maze[x][y]==1):
return True
else:
return False
# 移步函數實現
def walk(maze,x,y):
# 如果位置是迷宮的出口，說明成功走出迷宮
if(x==0 and y==0):
print("successful!")
return True
# 遞歸主體實現
if valid(maze,x,y):
# print(x,y)
maze[x][y]=2 # 做標記，防止折回
# 針對四個方向依次試探，如果失敗，撤銷一步
if not walk(maze,x-1,y):
maze[x][y]=1
elif not walk(maze,x,y-1):
maze[x][y]=1
elif not walk(maze,x+1,y):
maze[x][y]=1
elif not walk(maze,x,y+1):
maze[x][y]=1
else:
return False # 無路可走說明，沒有解
return True
walk(maze,3,3)
遞歸是個好東西呀！
⑵ 求走迷宮的演算法！（計算機的演算法）（編程也可以
我的思路：
按照人類走迷宮的方法，貼著左邊走，左邊有路就向左走，左邊沒路向前走，左邊前面都沒路向右走
機器人的應該是：1.判斷左邊是否有牆，無牆：機器人左轉，前進一步，繼續判斷左。。
2.左邊有牆，則判斷前方是否有牆，無則向前一步，跳回第一步
3.前方有牆（此時狀態是左有牆，前有牆），則向機器人右轉，跳回第一步
另外有個前提條件，機器人轉彎需要原地轉，有轉彎半徑的肯定不行。
還有個問題，就是機器人自己不知道自己已經從迷宮出來了，會一直走。。
⑶ 數據結構演算法 用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尋路演算法
先構建一個如下的模型圖,其中黑色為牆壁,紅色為路徑節點。牆可以為一個方形格子也可以僅僅是一條線(為方格時對角線上的牆壁始終無法被打通)。
先構建一個除了外圈為黑色牆壁,內部全是灰色通路的迷宮模型
⑸ 迷宮演算法復雜度如何計算
迷宮生成可以O(n*m)完成。走迷宮的話可以O(n*m*2)左右。
只要記錄走到每一格的最優解就可以了。
最好不要用深度優先搜索。用廣度優先的實現方便。
⑹ 簡單的迷宮演算法
用python遞歸求解
dirs=[(0,1),(1,0),(0,-1),(-1,0)] #當前位置四個方向的偏移量
path=[] #存找到的路徑
def mark(maze,pos): #給迷宮maze的位置pos標"2"表示「倒過了」
maze[pos[0]][pos[1]]=2
def passable(maze,pos): #檢查迷宮maze的位置pos是否可通行
return maze[pos[0]][pos[1]]==0
def find_path(maze,pos,end):
mark(maze,pos)
if pos==end:
print(pos,end=" ") #已到達出口，輸出這個位置。成功結束
path.append(pos)
return True
for i in range(4): #否則按四個方向順序檢查
nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1]
#考慮下一個可能方向
if passable(maze,nextp): #不可行的相鄰位置不管
if find_path(maze,nextp,end):#如果從nextp可達出口，輸出這個位置，成功結束
print(pos,end=" ")
path.append(pos)
return True
return False
def see_path(maze,path): #使尋找到的路徑可視化
for i,p in enumerate(path):
if i==0:
maze[p[0]][p[1]] ="E"
elif i==len(path)-1:
maze[p[0]][p[1]]="S"
else:
maze[p[0]][p[1]] =3
print("\n")
for r in maze:
for c in r:
if c==3:
print('\033[0;31m'+"*"+" "+'\033[0m',end="")
elif c=="S" or c=="E":
print('\033[0;34m'+c+" " + '\033[0m', end="")
elif c==2:
print('\033[0;32m'+"#"+" "+'\033[0m',end="")
elif c==1:
print('\033[0;;40m'+" "*2+'\033[0m',end="")
else:
print(" "*2,end="")
print()
if __name__ == '__main__':
maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],\
[1,0,0,0,1,1,0,0,0,1,0,0,0,1],\
[1,0,1,0,0,0,0,1,0,1,0,1,0,1],\
[1,0,1,0,1,1,1,1,0,1,0,1,0,1],\
[1,0,1,0,0,0,0,0,0,1,1,1,0,1],\
[1,0,1,1,1,1,1,1,1,1,0,0,0,1],\
[1,0,1,0,0,0,0,0,0,0,0,1,0,1],\
[1,0,0,0,1,1,1,0,1,0,1,1,0,1],\
[1,0,1,0,1,0,1,0,1,0,1,0,0,1],\
[1,0,1,0,1,0,1,0,1,1,1,1,0,1],\
[1,0,1,0,0,0,1,0,0,1,0,0,0,1],\
[1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
start=(1,1)
end=(10,12)
find_path(maze,start,end)
see_path(maze,path)
⑺ 試設計迷宮求解演算法:迷宮是一個m行n列的0-1矩陣,其中0表示無障礙,1表示有障礙
假設8個方位被簡單定義為 char a[8];
int path(point *location)
{
if(「location不為出口」&&「location.a[0]未涉足過」)
path(location->a[0]);
else if(「location不為出口」&&「location.a[1]未涉足過」)
path(location->a[0]);
else if(「location不為出口」&&「location.a[2]未涉足過」)
path(location->a[0]);
` ````````````````````
``````````
``````
``
else return 0;
}
這是一個迭代過程，需要對每一個方位的位置都遍歷一遍，也是一個深度優先的遍歷過程。
我在這只給lz一個示意，具體的演算法在《數據結構》的書上基本都有，蠻經典的。希望能對lz有所幫組。
加油！
⑻ 李氏迷宮演算法的發展
迷宮演算法最初是由C．Y．Lee提出的,又稱為李氏演算法或波擴法，其優點是只要最短路徑存在，就一定能找到，然而其缺點也是明顯的，對於n×n的網格空間，它需要O（n2）的運行時間和存儲空間並產生了較多的層間引線孔。
C.Y.LEE簡介:
William C.Y.Lee(威廉．C．Y．李)博士，國際著名科學家，教育家，近代移動通信奠基人之一。
李博士於1963年獲得美國Ohio State University電氣工程博士學位；1964～1979年，開創了美國貝爾試驗室下的移動無線電通信研究室；1979～1985年，任美國ITT公司國防通信部的尖端技術開發部主管；1985～2000年，任美國Vodafone AirTouch公司副總裁和首席科學家。2000～2005年，任美國LinkAir通信公司董事長，現任美國Treyspan公司董事長。
李博士因開發了商用的AMPS和CDMA技術而享譽全世界，在其幾十年的科研生涯中，獲得殊榮無數。1982年成為IEEE會員，1987年成為全美無線電俱樂部會員，1982～1998年應美國George Washington University邀請，主講最早的面向產業的蜂窩和移動通信課程。還有ITTDCD的技術貢獻獎(1984)，Ohio State University有突出貢獻的校友(1990)，IEEE VTSAvant Garde獎(1990)，美國CTIA的獎勵證書(1994)，IEEE車載技術協會技術服務獎(1996)，中美(SATEC)傑出貢獻證書(1997)以及貝爾試驗室致力服務獎(1998)，等等。李博士還是美國國家競爭委員會的會員，美國加利福尼亞州科學技術委員會成員，北京航空航天大學、西南交大的名譽教授。
李博士為蜂窩通信領域作出了巨大的貢獻。他的重要專著和教科書《無線與蜂窩通信》(1989年第1版，1997年第2版，本書是2006年第3版的中文版)風靡全球，已被翻譯成俄文版、漢語版、日語版、韓語版等多種文字。在該書第1版的序言里，李博士就明確闡述了他為蜂窩通信產業制定的目標：「讓我們攜起手來，使蜂窩產業發揮它最大的潛力，我們的目標是：在不遠的將來，讓攜帶型蜂窩電話把我們的通話遍及世界每一個角落。」
⑼ C語言迷宮問題，求該演算法的時間和空間的復雜度。迷宮的路徑已經定義好，求出路的演算法。
該演算法是不穩定的，其時空復雜度不僅和m,n有關，還和mg[][]的具體數值有關。
最壞情況下：每個點都試探過才走到終點。此時時間復雜度為：(m*n-1)*4，（其中4為4個方向），空間復雜度m*n*2，(其中m*n為存儲迷宮圖空間，m*n為棧空間);
再好情況下：一次試探過就走到終點。此時時間復雜度為：(min(m,n)-1)，空間復雜度m*n;
所以：
該演算法時間復雜度為：[(m*n-1)*4+(min(m,n)-1)]/2，約為2×m×n
空間復雜度為3*m*n/2