Python使用回溯法子集樹模板解決迷宮問題示例
本文實(shí)例講述了Python使用回溯法解決迷宮問題。分享給大家供大家參考,具體如下:
問題
給定一個(gè)迷宮,入口已知。問是否有路徑從入口到出口,若有則輸出一條這樣的路徑。注意移動(dòng)可以從上、下、左、右、上左、上右、下左、下右八個(gè)方向進(jìn)行。迷宮輸入0表示可走,輸入1表示墻。為方便起見,用1將迷宮圍起來避免邊界問題。
分析
考慮到左、右是相對(duì)的,因此修改為:北、東北、東、東南、南、西南、西、西北八個(gè)方向。在任意一格內(nèi),有8個(gè)方向可以選擇,亦即8種狀態(tài)可選。因此從入口格子開始,每進(jìn)入一格都要遍歷這8種狀態(tài)。
顯然,可以套用回溯法的子集樹模板。
注意,解的長度是不固定的。
代碼
# 迷宮(1是墻,0是通路) maze = [[1,1,1,1,1,1,1,1,1,1], [0,0,1,0,1,1,1,1,0,1], [1,1,0,1,0,1,1,0,1,1], [1,0,1,1,1,0,0,1,1,1], [1,1,1,0,0,1,1,0,1,1], [1,1,0,1,1,1,1,1,0,1], [1,0,1,0,0,1,1,1,1,0], [1,1,1,1,1,0,1,1,1,1]] m, n = 8, 10 # 8行,10列 entry = (1,0) # 迷宮入口 path = [entry] # 一個(gè)解(路徑) paths = [] # 一組解 # 移動(dòng)的方向(順時(shí)針8個(gè):N, EN, E, ES, S, WS, W, WN) directions = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)] # 沖突檢測(cè) def conflict(nx, ny): global m,n,maze # 是否在迷宮中,以及是否可通行 if 0 <= nx < m and 0 <= ny < n and maze[nx][ny]==0: return False return True # 套用子集樹模板 def walk(x, y): # 到達(dá)(x,y)格子 global entry,m,n,maze,path,paths,directions if (x,y) != entry and (x % (m-1) ==0 or y % (n-1) == 0): # 出口 #print(path) paths.append(path[:]) # 直接保存,未做最優(yōu)化 else: for d in directions: # 遍歷8個(gè)方向(亦即8個(gè)狀態(tài)) nx, ny = x+d[0], y+d[1] path.append((nx,ny)) # 保存,新坐標(biāo)入棧 if not conflict(nx, ny): # 剪枝 maze[nx][ny] = 2 # 標(biāo)記,已訪問(奇怪,此兩句只能放在if區(qū)塊內(nèi)?。? walk(nx, ny) maze[nx][ny] = 0 # 回溯,恢復(fù) path.pop() # 回溯,出棧 # 解的可視化(根據(jù)一個(gè)解x,復(fù)原迷宮路徑,'2'表示通路) def show(path): global maze import pprint, copy maze2 = copy.deepcopy(maze) for p in path: maze2[p[0]][p[1]] = 2 # 通路 pprint.pprint(maze) # 原迷宮 print() pprint.pprint(maze2) # 帶通路的迷宮 # 測(cè)試 walk(1,0) print(paths[-1], '\n') # 看看最后一條路徑 show(paths[-1])
效果圖
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
django實(shí)現(xiàn)類似觸發(fā)器的功能
今天小編就為大家分享一篇django實(shí)現(xiàn)類似觸發(fā)器的功能,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-11-11將自己的數(shù)據(jù)集制作成TFRecord格式教程
今天小編就為大家分享一篇將自己的數(shù)據(jù)集制作成TFRecord格式教程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-02-02深入了解和應(yīng)用Python 裝飾器 @decorator
在編程過程中,經(jīng)常遇到這樣的場(chǎng)景:登錄校驗(yàn),權(quán)限校驗(yàn),日志記錄等,這些功能代碼在各個(gè)環(huán)節(jié)都可能需要,但又十分雷同,通過裝飾器來抽象、剝離這部分代碼可以很好解決這類場(chǎng)景,這篇文章主要介紹了Python的裝飾器 @decorator,探討了使用的方式,需要的朋友可以參考下2019-04-04Python?任務(wù)自動(dòng)化工具nox?的配置與?API詳情
這篇文章主要介紹了Python?任務(wù)自動(dòng)化工具nox?的配置與?API詳情,Nox?會(huì)話是通過被@nox.session裝飾的標(biāo)準(zhǔn)?Python?函數(shù)來配置的,具體詳情下文相關(guān)介紹需要的小伙伴可以參考一下2022-07-07Python中函數(shù)參數(shù)調(diào)用方式分析
這篇文章主要介紹了Python中函數(shù)參數(shù)調(diào)用方式,結(jié)合實(shí)例形式分析了Python函數(shù)參數(shù)定義與使用的四種常見操作方法,需要的朋友可以參考下2018-08-08