我写了一个递归解决迷宫的程序。它打开一个包含迷宫的文本文件,将其转换为列表列表,然后尝试递归解决它。这是解决迷宫的部分:
def search(x,y, mazeList):
# returns True if it has found end of maze
if mazeList[x][y] == 'E':
return True
# returns False if it encounters a wall
elif mazeList[x][y] == '-':
return False
elif mazeList[x][y] == '+':
return False
elif mazeList[x][y] == "|":
return False
# returns False if it finds a visited path
elif mazeList[x][y] == '*':
return False
# marks path with '*'
mazeList[x][y] = '*'
# recursive search
if ((search(x+1, y, mazeList))
or (search(x, y-1, mazeList))
or (search(x-1, y, mazeList))
or (search(x, y+1, mazeList))):
return True
return False
在迷宫中,"-","+"和"|"构成了迷宫的墙壁,空白空间可以导航,"E"是迷宫的尽头。它从迷宫的左下角开始,然后从那里开始。我希望正确的路径用 * 标记,但是它用 * 标记它所采用的每条路径,即使它是回溯的错误路径。
那么我如何编辑我的代码,以便最终只用 * 标记从开始到结束的正确路径
您可以尝试在"返回的路上"重写路径,使用与用于创建访问路径的"*"不同的符号。
示例:替换
if mazeList[x][y] == 'E':
return True
跟
if mazeList[x][y] == 'E':
mazeList[x][y] = 'o'
return True
和
if ((search(x+1, y, mazeList))
or (search(x, y-1, mazeList))
or (search(x-1, y, mazeList))
or (search(x, y+1, mazeList))):
return True
跟
if ((search(x+1, y, mazeList))
or (search(x, y-1, mazeList))
or (search(x-1, y, mazeList))
or (search(x, y+1, mazeList))):
mazeList[x][y] = 'o'
return True
希望路径将用 o 书写。虽然没有测试它
简而言之,每当return True
时,将单元格标记为属于正确的路径。你必须用星星以外的东西标记它。此外,一旦你找到一个给你正确的方向,不要尝试其他方向。(更新:Python 确实支持短路布尔计算,但以下代码不依赖于它。所以你可以写这样的东西:
dx = [1, -1, 0, 0] # better define dx and dy globally
dy = [0, 0, 1, -1]
for i in range(4):
if search(x+dx[i], y+dy[i], mazeList):
mazeList[x][y] = '!'
return True
return False
第一部分可以更简洁:
if mazeList[x][y] == 'E':
return True
elif mazeList[x][y] != ' ':
return False
else:
或者,您可以使用 mazeList[x][y] in ['+', '-']
.
进行某种深度优先搜索时,你会在递归函数的末尾打印出正确的答案,当你回溯时,而不是当你第一次输入它时,因为你不知道先验,哪个方向是正确的。这同样适用于在图中查找和打印欧拉循环(如果有的话)。
除了"取消标记"路径,您可以尝试以下方法: 不要只返回True
或False
,而是返回找到的路径,然后使用其他方法绘制标记。
当你找到"E"
时,你只需返回[(x, y)]
。然后,您的递归搜索可能如下所示:
for (dx,dy) in [(+1,0), (-1,0), (0,+1), (0,-1)]:
path = search(x+dx, y+dy, mazeList)
if path: # path is a (non-empty) list
return [(x, y)] + path
随着递归调用的返回,这将逐渐构建并返回目标的路径,从目标到开始。
当然,由于您依靠标记的路径来避免重新访问以前的位置,因此您将需要一些其他方法,例如对以前访问过的位置进行全局set
。
另请注意,您的算法是深度优先搜索,因此不会找到最短的路径,而是找到通往目标的任何路径。对此最好使用广度优先搜索,但这需要对代码进行一些重大重组,使用队列而不是递归来实现。