Python 實現(xiàn)遞歸法解決迷宮問題的示例代碼
更新時間：2020年01月12日 11:20:42 作者：HibiscusToYou
這篇文章主要介紹了Python 實現(xiàn)遞歸法解決迷宮問題的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
迷宮問題
問題描述：
迷宮可用方陣 [m, n] 表示，0 表示可通過，1 表示不能通過。若要求左上角 (0, 0) 進入，設(shè)計算法尋求一條能從右下角 (m-1, n-1) 出去的路徑。
示例圖：
此示例圖基本參數(shù)為：
- m：對應(yīng)
- x 軸n：對應(yīng) y 軸
- 綠色線代表期望輸出的路徑
算法思路
- 標記當(dāng)前所在位置
- 如果此時所在位置為終點，說明可以到達終點，退出遞歸；
否則，則存在 4 種可能的移動方向即上、下、左、右，遍歷這 4 個方向，如果這 4 個方向存在相鄰值為 0 的點，則將當(dāng)前點坐標標記為該相鄰值為 0 的點坐標，進入遞歸
直觀理解為：
上圖中紅色圈的相鄰值為 0 的點有 3 個，則會依次遍歷這 3 個點尋求某一條件并進入遞歸
實現(xiàn)過程
標記函數(shù)
def mark(maze, pos): """ 標記函數(shù)，用來標記歷史走過的位置 :param maze: 一個 m*n 大小的二維矩陣迷宮 :param pos: 當(dāng)前需要標記的位置坐標 pos = (x, y)，x = pos[0], y = pos[1] """ maze[pos[0]][pos[1]] = 2 # 將走過的位置標記為 2
移動函數(shù)
def move(maze, pos): """ 移動函數(shù)，用來測試當(dāng)前位置是否可繼續(xù)移動，移動條件為當(dāng)前位置為 0 :param maze: 一個 m*n 大小的二維矩陣迷宮 :param pos: 當(dāng)前需要標記的位置坐標 pos = (x, y)，x = pos[0], y = pos[1] :return: bool 類型 """ return maze[pos[0]][pos[1]] == 0
核心函數(shù) - 路徑查找函數(shù)
def find_path(maze, start, end):
"""
路徑查找函數(shù)
:param maze: 一個 m*n 大小的二維矩陣迷宮
:param start: 起始點位置坐標，start = (1, 1)
:param end: 終點坐標，end = (m, n)
:return: bool 類型
"""
mark(maze, start) # 將起始位置標記
if start == end: # 路徑查找（遞歸）終止條件為到達終點
move_path.append(start)
return True
# 未到達終點時，存在 4 種可能的移動方向，即上 (-1, 0)，下 (1, 0)，左 (0, -1)，右 (0, 1)
move_direction = [
(-1, 0), (1, 0), (0, -1), (0, 1)
]
direction = ['↑', '↓', '←', '→']
for i in range(4): # 遍歷 4 種可能的方向
next_start = (start[0] + move_direction[i][0], start[1] + move_direction[i][1]) # 下一個可能的起始點坐標
if move(maze, next_start): # 找出存在 0 即可移動的下一個起始點坐標，進入遞歸
if find_path(maze, next_start, end):
# 這里之所以仍然添加起始點坐標是因為當(dāng)查詢到下一個位置就是終點或者可到達終點時記錄此時位置
move_path.append(start)
path_direction.append(direction[i]) # 記錄路徑方向
return True
return False # 遍歷遞歸了 4 種可能方向后仍不能到達終點則說明無法走出迷宮
算法到這里基本上已經(jīng)算完成，整體上不算太復(fù)雜
美化輸出
生成帶有移動路徑數(shù)據(jù)的迷宮矩陣
def path_maze(maze, directions_map):
"""
生成帶有移動路徑的迷宮矩陣
:param maze: 一個 m*n 大小的二維矩陣迷宮
:param directions_map: 一個記錄移動方向坐標的字典，有 ↑，↓，←，→ 4 個元素
:return: path_maze
"""
n, m = len(maze[0]), len(maze)
for x in range(1, m-1):
for y in range(1, n-1):
maze[x][y] = maze[x][y] if maze[x][y] != 2 else 0 # 將標記的 2 還原為 0
for x in range(m):
for i in range(1, 2 * n - 1, 2):
maze[x].insert(i, ' ') # 重初始化 maze，在每兩個元素間插入占位符 ' ' 3 個空格
for x in range(1, 2 * m - 1, 2):
maze.insert(x, [' ', ' '] * (n-1) + ['']) # 插入兩種空格占位符 ' ' 和 ' '
for direction in directions_map:
for directions_position in directions_map[direction]:
i, j = directions_position
i = 2 * i
j = 2 * j
if direction == "↑":
maze[i - 1][j] = "↑"
if direction == "↓":
maze[i + 1][j] = "↓"
if direction == "←":
maze[i][j] = " ← "
if direction == "→":
maze[i][j + 1] = " → "
return maze
生成的帶路徑數(shù)據(jù)的迷宮矩陣部分數(shù)據(jù)截圖如下：
美化打印迷宮矩陣
def print_maze(maze, text='原始迷宮為：', end1=' ', end2='\n\n', xs=0, xe=0, ys=0, ye=0):
"""
輸出迷宮矩陣，非必要，可注釋刪除
:param maze: 一個 m*n 大小的二維矩陣迷宮
:param text: 輸出提示
:param end1: 控制每行尾結(jié)束符
:param end2: 控制每行尾結(jié)束符
:param xs: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出
:param xe: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出
:param ys: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出
:param ye: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出
"""
print(text)
n, m = len(maze[0]), len(maze)
for x in range(xs, m-xe):
for y in range(ys, n-ye):
print(maze[x][y], end=end1)
print(end=end2)
最終輸出結(jié)果：
效果尚可
完整代碼
# -*- coding: utf-8 -*-
"""
Created on 2020/1/11 10:51
Author : zxt
File : maze_recursion.py
Software: PyCharm
"""
from random import randint
def mark(maze, pos):
"""
標記函數(shù)，用來標記歷史走過的位置
:param maze: 一個 m*n 大小的二維矩陣迷宮
:param pos: 當(dāng)前需要標記的位置坐標 pos = (x, y)，x = pos[0], y = pos[1]
"""
maze[pos[0]][pos[1]] = 2 # 將走過的位置標記為 2
def move(maze, pos):
"""
移動函數(shù)，用來測試當(dāng)前位置是否可繼續(xù)移動，移動條件為當(dāng)前位置為 0
:param maze: 一個 m*n 大小的二維矩陣迷宮
:param pos: 當(dāng)前需要標記的位置坐標 pos = (x, y)，x = pos[0], y = pos[1]
:return: bool 類型
"""
return maze[pos[0]][pos[1]] == 0
move_path = [] # 記錄能成功到達出口的移動路徑坐標
path_direction = [] # 記錄能成功到達出口的移動路徑方向
def find_path(maze, start, end):
"""
路徑查找函數(shù)
:param maze: 一個 m*n 大小的二維矩陣迷宮
:param start: 起始點位置坐標，start = (1, 1)
:param end: 終點坐標，end = (m, n)
:return: bool 類型
"""
mark(maze, start) # 將起始位置標記
if start == end: # 路徑查找（遞歸）終止條件為到達終點
move_path.append(start)
return True
# 未到達終點時，存在 4 種可能的移動方向，即上 (-1, 0)，下 (1, 0)，左 (0, -1)，右 (0, 1)
move_direction = [
(-1, 0), (1, 0), (0, -1), (0, 1)
]
direction = ['↑', '↓', '←', '→']
for i in range(4): # 遍歷 4 種可能的方向
next_start = (start[0] + move_direction[i][0], start[1] + move_direction[i][1]) # 下一個可能的起始點坐標
if move(maze, next_start): # 找出存在 0 即可移動的下一個起始點坐標，進入遞歸
if find_path(maze, next_start, end):
# 這里之所以仍然添加起始點坐標是因為當(dāng)查詢到下一個位置就是終點或者可到達終點時記錄此時位置
move_path.append(start)
path_direction.append(direction[i]) # 記錄路徑方向
return True
return False # 遍歷遞歸了 4 種可能方向后仍不能到達終點則說明無法走出迷宮
def gen_maze(m, n):
"""
生成隨機迷宮陣列
:param m: int 類型
:param n: int 類型
:return: maze
"""
m += 2
n += 2 # m 和 n 均 +2 是為了構(gòu)造最外層的 1
maze = [[1 for i in range(n)] for j in range(m)] # 初始化大小為 m * n，值全為 1 的二維矩陣
for x in range(1, m-1):
for y in range(1, n-1):
"""
這里 x, y 取值范圍為 x ∈ [1, m-1)，y ∈ [1, n-1) 是因為我們令此迷宮的最外層（四周）均為 1，如：
考察 3 * 3 矩陣，一種可能的陣列為：
[
_ |←--- n:y ---→|
↑ [1, 1, 1, 1, 1],
| [1, 0, 1, 0, 1],
m:x [1, 0, 0, 1, 1],
| [1, 1, 0, 0, 1],
↓ [1, 1, 1, 1, 1]
]
"""
if (x == 1 and y == 1) or (x == m - 2 and y == n - 2):
maze[x][y] = 0 # 起始點和終點必為 0
else:
maze[x][y] = randint(0, 1) # 在最外層均為 1 的情況下內(nèi)部隨機取 0，1
return maze
def print_maze(maze, text='原始迷宮為：', end1=' ', end2='\n\n', xs=0, xe=0, ys=0, ye=0):
"""
輸出迷宮矩陣，非必要，可注釋刪除
:param maze: 一個 m*n 大小的二維矩陣迷宮
:param text: 輸出提示
:param end1: 控制每行尾結(jié)束符
:param end2: 控制每行尾結(jié)束符
:param xs: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出
:param xe: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出
:param ys: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出
:param ye: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出
"""
print(text)
n, m = len(maze[0]), len(maze)
for x in range(xs, m-xe):
for y in range(ys, n-ye):
print(maze[x][y], end=end1)
print(end=end2)
def path_maze(maze, directions_map):
"""
生成帶有移動路徑的迷宮矩陣
:param maze: 一個 m*n 大小的二維矩陣迷宮
:param directions_map: 一個記錄移動方向坐標的字典，有 ↑，↓，←，→ 4 個元素
:return: path_maze
"""
n, m = len(maze[0]), len(maze)
for x in range(1, m-1):
for y in range(1, n-1):
maze[x][y] = maze[x][y] if maze[x][y] != 2 else 0 # 將標記的 2 還原為 0
for x in range(m):
for i in range(1, 2 * n - 1, 2):
maze[x].insert(i, ' ') # 重初始化 maze，在每兩個元素間插入占位符 ' ' 3 個空格
for x in range(1, 2 * m - 1, 2):
maze.insert(x, [' ', ' '] * (n-1) + ['']) # 插入兩種空格占位符 ' ' 和 ' '
for direction in directions_map:
for directions_position in directions_map[direction]:
i, j = directions_position
i = 2 * i
j = 2 * j
if direction == "↑":
maze[i - 1][j] = "↑"
if direction == "↓":
maze[i + 1][j] = "↓"
if direction == "←":
maze[i][j] = " ← "
if direction == "→":
maze[i][j + 1] = " → "
return maze
def main():
# maze = gen_maze(m=10, n=12)
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]
] # 輸入樣式矩陣，這里最外層用 1 環(huán)包圍住，目的是方便后續(xù)的處理，可以用 gen_maze() 函數(shù)自生成
print_maze(maze)
if find_path(maze, start=(1, 1), end=(10, 12)):
mp = move_path[::-1]
pd = path_direction[::-1]
# 這里 pos[0] 和 pos[1] 都要 -1 是因為原來的遞歸計算中存在最外層的 1 環(huán)
print('坐標移動順序為:', [(pos[0]-1, pos[1]-1) for pos in mp])
path_direction_map = {
'↑': [],
'↓': [],
'←': [],
'→': []
} # 路徑方向的映射表
for i in range(len(pd)):
path_direction_map[pd[i]].append(mp[i])
maze = path_maze(maze, path_direction_map)
print_maze(maze, text='迷宮移動路徑為：', end1='', end2='\n', xs=1, xe=1, ys=1, ye=1)
else:
print('此迷宮無解')
if __name__ == '__main__':
main()
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了Python設(shè)計模式之觀察者模式,簡單描述了觀察者模式的概念、原理,并結(jié)合實例形式分析了Python觀察者模式的相關(guān)定義與使用技巧,需要的朋友可以參考下2018-01-01
這篇文章主要為大家介紹了pymilvus?offset參數(shù)不生效解決示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
這篇文章主要介紹了matplotlib 向任意位置添加一個子圖(axes)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
對Pytorch神經(jīng)網(wǎng)絡(luò)初始化kaiming分布詳解
今天小編就為大家分享一篇對Pytorch神經(jīng)網(wǎng)絡(luò)初始化kaiming分布詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-08-08
python基礎(chǔ)之面對對象基礎(chǔ)類和對象的概念
這篇文章主要介紹了python面對對象基礎(chǔ)類和對象的概念,實例分析了Python中返回一個返回值與多個返回值的方法,需要的朋友可以參考下2021-10-10
Python+Tkinter實現(xiàn)股票K線圖的繪制
K線圖又稱蠟燭圖，常用說法是“K線”。K線是以每個分析周期的開盤價、最高價、最低價和收盤價繪制而成。本文將利用Python+Tkinter實現(xiàn)股票K線圖的繪制，需要的可以參考一下2022-08-08
今天小編就為大家分享一篇對Python中9種生成新對象的方法總結(jié)，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-05-05
一文教會你用Python獲取網(wǎng)頁指定內(nèi)容
Python用做數(shù)據(jù)處理還是相當(dāng)不錯的,如果你想要做爬蟲,Python是很好的選擇,它有很多已經(jīng)寫好的類包,只要調(diào)用即可完成很多復(fù)雜的功能,下面這篇文章主要給大家介紹了關(guān)于Python獲取網(wǎng)頁指定內(nèi)容的相關(guān)資料,需要的朋友可以參考下2022-03-03
這篇文章主要介紹了Python 實現(xiàn)定積分與二重定積分的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-05-05
Python?sklearn?中的?make_blobs()?函數(shù)示例詳解
make_blobs()?是?sklearn.datasets中的一個函數(shù)，這篇文章主要介紹了Python?sklearn?中的?make_blobs()?函數(shù),本文結(jié)合實例代碼給大家介紹的非常詳細，需要的朋友可以參考下2023-02-02