我制作了一個程式，詢問用戶一個大小并使用遞回回溯演算法生成一個大小為 n^2 的完美迷宮。我遇到了這個錯誤，發現我可以簡單地使用：
sys.setrecursionlimit(8000)
一開始它運行良好，但是當我增加迷宮的大小時，我的 python 程式就直接退出了，什么也沒說……
這是我用來檢查方向的字典：
_dic = {
"N": (-1, 0),
"S": (1, 0),
"E": (0, 1),
"W": (0, -1),
}
我將迷宮存盤在 str 的 numpy 陣列中，我只存盤將要修改的迷宮部分，并在將其轉換為字串時添加其余部分以供顯示。例如，大小為 3 (3x3) 的迷宮在 display 中將如下所示：
.######
..#.#.#
#######
#.#.#.#
#######
#.#.#..
######.
但在我的陣列中，我只有中間部分：
.#.#.
#####
.#.#.
#####
.#.#.
這只是為了嘗試優化一點......
這是實際的回溯功能：
# Recursive backtracking function that takes a posx and posy as position of the cell to visit
def _backtrack(self, posx, posy):
self._map[posx][posy] = 'V' # Mark the cell as visited
while True:
# hasNeighbors returns a empty list if no valid neighbors ar found
# but returns a list of cardinal directions corresponding to valid neighbors if found such as ["N", "E"]
# if there si a valid neighbor on the right and beneath.
dir = self._hasNeighbors(posx, posy)
lenght = len(dir)
# If there is no valid neighbors this is a dead end then return to backtrack
if lenght == 0:
return
# select a random direction to move to and remove it from the list
toBreak = dir.pop(dir.index(random.choice(dir)))
# Replace '#' by '.'
self._map[posx self._dic[toBreak][0]][posy self._dic[toBreak][1]] = '.'
# If there is only one valid neightbor break the wall and update posx and posy
# It uses the while loop to keep visiting cells without recursion as long as there is only one choice
if lenght == 1:
posx = self._dic[toBreak][0] * 2
posy = self._dic[toBreak][1] * 2
self._map[posx][posy] = 'V'
#recursive call of the backtrack function with the position of the cell we want to visit
else:
self._backtrack(posx self._dic[toBreak][0] * 2, posy self._dic[toBreak][1] * 2)
這是 hasNeighbors 之一：
def _hasNeighbors(self, posx, posy):
result = []
# Checking neighbors in each direction
for dir in self._dic.keys():
# If the indexes doesn't exceed the size of the maze
if 0 <= posx self._dic[dir][0] < self._size * 2 - 1 and 0 <= posy self._dic[dir][1] < self._size * 2 - 1:
# If the neighbor hasn't been visited
if self._map[posx self._dic[dir][0] * 2][posy self._dic[dir][1] * 2] == '.':
#Append this direction to the list of valid neighbors
result.append(dir)
return result
對于 5、20、50 等小尺寸，它就像一個魅力......但是當我開始變大一點時，如果我不增加限制并且如果我增加它，我要么有最大遞回深度錯誤直接退出而不說這樣的話：
PS C:\Users\pierr\Travail\Code\Amazing-Maze> python -m amazingmaze
Please entre the size of the maze : 100
PS C:\Users\pierr\Travail\Code\Amazing-Maze>
我真的不知道如何解決這個問題。我不明白為什么它會以如此小的尺寸阻塞我的意思是我應該能夠生成更大的尺寸而不會出汗......是我的遞回回溯實作是我錯過了什么的問題嗎？我的老師告訴我，這是因為我的停止條件不起作用，我可能正在訪問我已經訪問過的牢房，但我有點不同意，顯然有問題，但我真的不認為是那樣。您可以在https://github.com/lebair-pierre-alexis/Amazing-Maze找到完整的代碼
uj5u.com熱心網友回復：
您的遞回函式_backtrack適用于Tail Call Optimization。尾呼叫優化允許無限遞回（如果適用）。但是，由于 Python 的開發者Guido van Rossum 在此解釋的原因，Python 并沒有開箱即用。
- 但是，我們可以使用Chris Penner的方法添加它
- 將尾遞回裝飾器添加到函式定義中
- 使用遞回函式遞回
- 使用這種方法，我能夠修改 github 存盤庫中的代碼以運行大小為 100 的矩陣。
- 下面的代碼顯示了您發布的代碼所需的模塊。
代碼
# Tail recursion decorator (could place in file tail_recursion.py)
class Recurse(Exception):
def __init__(self, *args, **kwargs):
self.args = args
self.kwargs = kwargs
def recurse(*args, **kwargs):
raise Recurse(*args, **kwargs)
def tail_recursive(f):
def decorated(*args, **kwargs):
while True:
try:
return f(*args, **kwargs)
except Recurse as r:
args = r.args
kwargs = r.kwargs
continue
return decorated
# Recursive backtracking function that takes a posx and posy as position of the cell to visit
@tail_recursive # add recursive decorator
def _backtrack(self, posx, posy):
self._map[posx][posy] = 'V' # Mark the cell as visited
while True:
# hasNeighbors returns a empty list if no valid neighbors ar found
# but returns a list of cardinal dir_ections corresponding to valid neighbors if found such as ["N", "E"]
# if there is a valid neighbor on the right and beneath.
dir_ = self._hasNeighbors(posx, posy) # refactor dir to dir_ to avoid overwriting builtin function
lenght = len(dir_)
# If there is no valid neighbors this is a dead end then return to backtrack
if lenght == 0:
return
# select a random direction to move to and remove it from the list
toBreak = dir_.pop(dir_.index(random.choice(dir_)))
# Replace '#' by '.'
self._map[posx self._dic[toBreak][0]][posy self._dic[toBreak][1]] = '.'
# If there is only one valid neightbor break the wall and update posx and posy
# It uses the while loop to keep visiting cells without recursion as long as there is only one choice
if lenght == 1:
posx = self._dic[toBreak][0] * 2
posy = self._dic[toBreak][1] * 2
self._map[posx][posy] = 'V'
#recursive call of the backtrack function with the position of the cell we want to visit
else:
# Replace call with tail recursive call
# self._backtrack(posx self._dic[toBreak][0] * 2, posy self._dic[toBreak][1] * 2)
recurse(self, posx self._dic[toBreak][0] * 2, posy self._dic[toBreak][1] * 2)
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/515761.html
下一篇：回傳通用樹節點n的高度（遞回）