Python 實現遞歸法解決迷宮問題的示例代碼

 更新時間:2020-01-12 19:00:24   作者:佚名   我要評論(0)

迷宮問題
問題描述:
迷宮可用方陣 [m, n] 表示,0 表示可通過,1 表示不能通過。若要求左上角 (0, 0) 進入,設計算法尋求一條能從右下角 (m-1, n-1) 出去的路徑。

迷宮問題

問題描述:

迷宮可用方陣 [m, n] 表示,0 表示可通過,1 表示不能通過。若要求左上角 (0, 0) 進入,設計算法尋求一條能從右下角 (m-1, n-1) 出去的路徑。

示例圖:

期望輸出路徑圖

此示例圖基本參數為:

  • m:對應
  • x 軸n:對應 y 軸
  • 綠色線代表期望輸出的路徑

算法思路

  1. 標記當前所在位置
  2. 如果此時所在位置為終點,說明可以到達終點,退出遞歸;

否則,則存在 4 種可能的移動方向即上、下、左、右,遍歷這 4 個方向,如果這 4 個方向存在相鄰值為 0 的點,則將當前點坐標標記為該相鄰值為 0 的點坐標,進入遞歸

直觀理解為:

遞歸理解圖

上圖中紅色圈的相鄰值為 0 的點有 3 個,則會依次遍歷這 3 個點尋求某一條件并進入遞歸

實現過程

標記函數

def mark(maze, pos):
  """
  標記函數,用來標記歷史走過的位置
  :param maze: 一個 m*n 大小的二維矩陣迷宮
  :param pos: 當前需要標記的位置坐標 pos = (x, y),x = pos[0], y = pos[1]
  """
  maze[pos[0]][pos[1]] = 2 # 將走過的位置標記為 2

移動函數

def move(maze, pos):
  """
  移動函數,用來測試當前位置是否可繼續移動,移動條件為當前位置為 0
  :param maze: 一個 m*n 大小的二維矩陣迷宮
  :param pos: 當前需要標記的位置坐標 pos = (x, y),x = pos[0], y = pos[1]
  :return: bool 類型
  """
  return maze[pos[0]][pos[1]] == 0

核心函數 - 路徑查找函數

def find_path(maze, start, end):
  """
  路徑查找函數
  :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):
        # 這里之所以仍然添加起始點坐標是因為當查詢到下一個位置就是終點或者可到達終點時記錄此時位置
        move_path.append(start)
        path_direction.append(direction[i]) # 記錄路徑方向
        return True
  return False # 遍歷遞歸了 4 種可能方向后仍不能到達終點則說明無法走出迷宮

算法到這里基本上已經算完成,整體上不算太復雜

美化輸出

生成帶有移動路徑數據的迷宮矩陣

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 print_maze(maze, text='原始迷宮為:', end1='  ', end2='\n\n', xs=0, xe=0, ys=0, ye=0):
  """
  輸出迷宮矩陣,非必要,可注釋刪除
  :param maze: 一個 m*n 大小的二維矩陣迷宮
  :param text: 輸出提示
  :param end1: 控制每行尾結束符
  :param end2: 控制每行尾結束符
  :param xs: 控制是否輸出最上方的 1 環,0 為輸出,1 為不輸出
  :param xe: 控制是否輸出最上方的 1 環,0 為輸出,1 為不輸出
  :param ys: 控制是否輸出最上方的 1 環,0 為輸出,1 為不輸出
  :param ye: 控制是否輸出最上方的 1 環,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)

最終輸出結果:

美化打印

效果尚可

完整代碼

# -*- 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):
  """
  標記函數,用來標記歷史走過的位置
  :param maze: 一個 m*n 大小的二維矩陣迷宮
  :param pos: 當前需要標記的位置坐標 pos = (x, y),x = pos[0], y = pos[1]
  """
  maze[pos[0]][pos[1]] = 2 # 將走過的位置標記為 2


def move(maze, pos):
  """
  移動函數,用來測試當前位置是否可繼續移動,移動條件為當前位置為 0
  :param maze: 一個 m*n 大小的二維矩陣迷宮
  :param pos: 當前需要標記的位置坐標 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):
  """
  路徑查找函數
  :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):
        # 這里之所以仍然添加起始點坐標是因為當查詢到下一個位置就是終點或者可到達終點時記錄此時位置
        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 是為了構造最外層的 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 的情況下內部隨機取 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: 控制每行尾結束符
  :param end2: 控制每行尾結束符
  :param xs: 控制是否輸出最上方的 1 環,0 為輸出,1 為不輸出
  :param xe: 控制是否輸出最上方的 1 環,0 為輸出,1 為不輸出
  :param ys: 控制是否輸出最上方的 1 環,0 為輸出,1 為不輸出
  :param ye: 控制是否輸出最上方的 1 環,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 環包圍住,目的是方便后續的處理,可以用 gen_maze() 函數自生成
  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 環
    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()

 以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

您可能感興趣的文章:

  • Python基于遞歸算法實現的走迷宮問題

相關文章

  • Python 實現遞歸法解決迷宮問題的示例代碼

    Python 實現遞歸法解決迷宮問題的示例代碼

    迷宮問題 問題描述: 迷宮可用方陣 [m, n] 表示,0 表示可通過,1 表示不能通過。若要求左上角 (0, 0) 進入,設計算法尋求一條能從右下角 (m-1, n-1) 出去的路徑。
    2020-01-12
  • html2canvas屬性和使用方法以及如何使用html2canvas將HTML內容寫入Canvas生成圖片

    html2canvas屬性和使用方法以及如何使用html2canvas將HTML內容寫入Canvas生成圖片

    如何使用JS截取HTML頁面為圖片呢,下面為大家介紹一款JS截圖插件html2canvas.js html2canvas.js 能夠實現在用戶瀏覽器端直接對整個或部分頁面進行截屏。 html2can
    2020-01-12
  • golang并發編程的實現

    golang并發編程的實現

    go main函數的執行本身就是一個協程,當使用go關鍵字的時候,就會創建一個新的協程 channel channel 管道,用于在多個協程之間傳遞信號 無緩存管道 當對無
    2020-01-12
  • python opencv實現信用卡的數字識別

    python opencv實現信用卡的數字識別

    本項目利用python以及opencv實現信用卡的數字識別 前期準備 導入工具包 定義功能函數 模板圖像處理 讀取模板圖像 cv2.imread(img) 灰度化處理 cv2
    2020-01-12
  • 2019年度web前端面試題總結(主要為Vue面試題)

    2019年度web前端面試題總結(主要為Vue面試題)

    畢業之后就在一直合肥小公司工作,沒有老司機、沒有技術氛圍,在技術的道路上我只能獨自摸索。老板也只會畫餅充饑,前途一片迷?床坏饺魏蜗M。于是乎,我果斷辭
    2020-01-12
  • 深入理解redux之compose的具體應用

    深入理解redux之compose的具體應用

    應用 最近給自己的react項目添加redux的時候,用到了redux中的compose函數,使用compose來增強store,下面是我在項目中的一個應用: import {createStore,apply
    2020-01-12
  • Java使用DateTimeFormatter實現格式化時間

    Java使用DateTimeFormatter實現格式化時間

    用掃描器獲取輸入的時間(年月日時分),這個時間的格式是常用的格式,然后格式化這個時間,把格式化的時間輸出到控制臺,可以在控制臺重復輸入時間.格式化的時間參考企業
    2020-01-12
  • Ranorex通過Python將報告發送到郵箱的方法

    Ranorex通過Python將報告發送到郵箱的方法

    Ranorex測試報告如何發送到郵箱在網上看了下,其實可以通過在Ranorex上或者VS調用編寫發送郵箱代碼就可以執行發送了,RX主要涉及到的開發語言是C++或者.NET。但是我
    2020-01-12
  • 通過實例解析JMM和Volatile底層原理

    通過實例解析JMM和Volatile底層原理

    這篇文章主要介紹了通過實例解析JMM和Volatile底層原理,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下 JMM和
    2020-01-11
  • 淺談pytorch卷積核大小的設置對全連接神經元的影響

    淺談pytorch卷積核大小的設置對全連接神經元的影響

    3*3卷積核與2*5卷積核對神經元大小的設置 #這里kerner_size = 2*5 class CONV_NET(torch.nn.Module): #CONV_NET類繼承nn.Module類 def __init__(self): super(
    2020-01-11

最新評論

双色球基本走势图200