在python中使用递归解决迷宫问题
所以，我有一项任务，要求我使用递归解决迷宫问题。 我将发布作业指南，以便您可以看到我在说什么。 教授没有多少解释递归，他给了我递归的例子，我会发布，但我希望有人能够给我一个更深入的递归解释，以及我将如何应用它来解决一个迷宫。 我没有要求任何人写代码，我只是希望有一些解释能让我走上正确的道路。 感谢任何回答的人。
这里是我有的例子：
def foo():
print("Before")
bar()
print("After")
def bar():
print("During")
def factorial(n):
"""n!"""
product = 1
for i in range(n,0,-1):
product *= i
return product
def recFac(n):
"""n! = n * (n-1)!"""
if(n == 1):
return 1
return n * recFac(n-1)
def hello():
"""Stack overflow!"""
hello()
def fib(n):
"""f(n) = f(n-1) + f(n-2)
f(0) = 0
f(1) = 1"""
if n == 0 or n == 1: #base case
return n
return fib(n-1) + fib(n-2) #recursive case
def mult(a,b):
"""a*b = a + a + a + a ..."""
#base case
if (b == 1):
return a
#recursive case
prod = mult(a,b-1)
prod *= a
return prod
def exp(a,b):
"""a ** b = a* a * a * a * a *.... 'b times'"""
#base case
if (b==0):
return 1
if (b == 1):
return a
#recursive case
return exp(a,b-1)*a
def pallindrome(word):
"""Returns True if word is a pallindrome, False otherwise"""
#base case
if word == "" or len(word)==1:
return True
#recursive case
if word[0] == word[len(word)-1]:
word = word[1:len(word)-1]
return pallindrome(word)
else:
return False
以下是指导方针：
您将创建一个迷宫爬行程序，能够解决您使用递归功能给出的任何迷宫！
问题1 - 加载迷宫
在你解开迷宫之前，你必须加载它。 对于这项任务，您将使用迷宫的简单文本格式。 你可以使用这个样本迷宫或创建你自己的。
这个问题的目标是加载任何给定的迷宫文件，并将其读入一个二维列表。 例如：loadMaze（“somemaze.maze”）应加载somemaze.maze文件并创建如下所示的列表...
[['#','#','#','#','#','#','#','#','#'],
['#','S','#',' ',' ',' ','#','E','#'],
['#',' ','#',' ','#',' ',' ',' ','#'],
['#',' ',' ',' ','#',' ','#',' ','#'],
['#', #','#','#','#','#','#','#','#']]
请注意，列表中的所有' r'和' n'字符已被删除。 为了使下一个问题更简单，你可以将这个列表变成一个全局变量。
接下来编写一个函数，以更好的格式打印出迷宫：
例如，
####################################
#S# ## ######## # # # # #
# # # # # # #
# # ##### ## ###### # ####### # #
### # ## ## # # # #### #
# # # ####### # ### #E#
####################################
在继续之前，用不同的迷宫测试你的代码。
问题2 - 准备解决迷宫问题
在你解开迷宫之前，你需要找到起点！ 在您的代码中添加一个名为findStart（）的函数，它将搜索迷宫（逐个字符）并返回'S'字符的x和y坐标。 你可能会认为在迷宫中至多存在一个这样的人物。 如果在迷宫返回-1中找不到'S'作为x和y坐标。
在继续之前在多个位置（包括无位置）用'S'测试您的代码。
问题3 - 解决迷宫！
最后，你准备好递归地解决迷宫问题！ 您的解决方案应该只需要一个方法：solve（y，x）
解决方法的单个实例应该解决迷宫中的单个位置。 参数y和x是当前要解决的坐标。 你的解决方法应该完成一些事情。 它应该检查它是否正在解决'E'的位置。 在这种情况下，您的解决方法已成功完成。 否则，它应该尝试递归地解决右边的空间。 请注意，您的方法应该只尝试解决空格，而不是墙（'＃'）。 如果该递归不会导致结束，那么尝试下来，然后离开，然后向上。 如果所有失败，你的代码应该回溯一步，并尝试另一个方向。
最后，在解决迷宫的同时，你的代码应该留下它的进展指标。 如果它正在搜索右侧，则当前位置应该有一个'>'来代替空白空间。 如果向下搜索放置'v'。 如果向左搜索'<'，并搜索'^'。 如果您的代码必须回溯移除方向箭头，并将位置设回“”。
一旦你的迷宫解决了，再次打印出迷宫。 你应该看一步一步地走迷宫。 例如，
main("somemaze.maze")
#########
#S# #E#
# # # #
# # # #
#########
S在（1,1）
#########
#S#>>v#E#
#v#^#>>^#
#>>^# # #
#########
用不同的开始和结束位置测试你的代码，并可选择在各种迷宫中测试。
以下是我到目前为止的代码：但代码实际上并不是在迷宫中打印曲目，我不知道为什么。
def loadMaze():
readIt = open('Maze.txt', 'r')
readLines = readIt.readlines()
global mazeList
mazeList = [list(i.strip()) for i in readLines]
def showMaze():
for i in mazeList:
mazeprint = ''
for j in i:
mazeprint = mazeprint + j
print(mazeprint)
print('n')
def solve(x,y, mazeList):
mazeList[x][y] = "o"
#Base case
if y > len(mazeList) or x > len(mazeList[y]):
return False
if mazeList[y][x] == "E":
return True
if mazeList[y][x] != " ":
return False
#marking
if solve(x+1,y) == True: #right
mazeList[x][y]= '>'
elif solve(x,y+1) == True: #down
mazeList[x][y]= 'v'
elif solve(x-1,y) == True: #left
mazeList[x][y]= '<'
elif solve(x,y-1) == True: #up
mazeList[x][y]= '^'
else:
mazeList[x][y]= ' '
return (mazeList[x][y]!= ' ')
这是我对CodeEval的Labirynth挑战的解决方案：
import sys
sys.setrecursionlimit(5000)
class Maze(object):
FLOOR = ' '
WALLS = '*'
PATH = '+'
def __init__(self):
self.cols = 0
self.rows = 0
self.maze = []
def walk_forward(self, current_k, r, c):
self.maze[r][c] = current_k
next_k = current_k + 1
# up
if r > 1:
up = self.maze[r - 1][c]
if up != self.WALLS:
if up == self.FLOOR or int(up) > current_k:
self.walk_forward(next_k, r - 1, c)
# down
if r < self.rows - 1:
down = self.maze[r + 1][c]
if down != self.WALLS:
if down == self.FLOOR or int(down) > current_k:
self.walk_forward(next_k, r + 1, c)
# left
if c > 1:
left = self.maze[r][c - 1]
if left != self.WALLS:
if left == self.FLOOR or int(left) > current_k:
self.walk_forward(next_k, r, c - 1)
# right
if c < self.cols - 1:
right = self.maze[r][c + 1]
if right != self.WALLS:
if right == self.FLOOR or int(right) > current_k:
self.walk_forward(next_k, r, c + 1)
def walk_backward(self, r, c):
current_k = self.maze[r][c]
if not isinstance(current_k, int):
return False
self.maze[r][c] = self.PATH
up = self.maze[r - 1][c] if r > 0 else None
down = self.maze[r + 1][c] if r < self.rows - 1 else None
left = self.maze[r][c - 1] if c > 1 else None
right = self.maze[r][c + 1] if c < self.cols else None
passed = False
if up and isinstance(up, int) and up == current_k - 1:
self.walk_backward(r - 1, c)
passed = True
if down and isinstance(down, int) and down == current_k - 1:
self.walk_backward(r + 1, c)
passed = True
if left and isinstance(left, int) and left == current_k - 1:
self.walk_backward(r, c - 1)
passed = True
if right and isinstance(right, int) and right == current_k - 1:
self.walk_backward(r, c + 1)
def cleanup(self, cleanup_path=False):
for r in range(0, self.rows):
for c in range(0, self.cols):
if isinstance(self.maze[r][c], int):
self.maze[r][c] = self.FLOOR
if cleanup_path and self.maze[r][c] == self.PATH:
self.maze[r][c] = self.FLOOR
def solve(self, start='up', show_path=True):
# finding start and finish points
upper = lower = None
for c in range(0, self.cols):
if self.maze[0][c] == self.FLOOR:
upper = (0, c)
break
for c in range(0, self.cols):
if self.maze[self.rows - 1][c] == self.FLOOR:
lower = (self.rows - 1, c)
break
if start == 'up':
start = upper
finish = lower
else:
start = lower
finish = upper
self.cleanup(cleanup_path=True)
self.walk_forward(1, start[0], start[1])
length = self.maze[finish[0]][finish[1]]
if not isinstance(length, int):
length = 0
if show_path:
self.walk_backward(finish[0], finish[1])
self.cleanup(cleanup_path=False)
else:
self.cleanup(cleanup_path=True)
return length
def save_to_file(self, filename):
with open(filename, 'w') as f:
f.writelines(str(self))
def load_from_file(self, filename):
self.maze = []
with open(filename, 'r') as f:
lines = f.readlines()
for line in lines:
row = []
for c in line.strip():
row.append(c)
self.maze.append(row)
self.rows = len(self.maze)
self.cols = len(self.maze[0]) if self.rows > 0 else 0
def get_maze(self):
return copy.copy(self.maze)
def __str__(self):
as_string = u''
for row in self.maze:
as_string += u''.join([str(s)[-1] for s in row]) + "n"
return as_string
maze = Maze()
maze.load_from_file(sys.argv[1])
maze.solve(show_path=True)
print str(maze)
（约会自己，我实际上是在高中时在COBOL中做过这个问题。）
你可以考虑解决迷宫作为采取步骤。
当你采取措施时，每次都应用相同的规则。 由于每次都应用相同的规则，因此每个步骤都可以使用完全相同的说明。 当你迈出一步时，你只需再次调用相同的例程，改变参数来指示新的步骤。 这是递归。 你一次一步地解决问题。
注意：一些递归解决方案将问题解决了一半，解决了每个独立于另一个问题的一半，这两种解决方案实际上是独立的。 它在这里不起作用，因为每个步骤（解决方案）都依赖于前面的步骤。
如果你陷入死胡同，你会退出死胡同，直到你找到一个仍然有可行方格来检查的步骤。
有用的提示：你不会在出口的路上标记正确的路径，因为你不知道你现在正在采取的步骤是退出路径的一部分。 当你知道每一步确实是路径的一部分时，你在回来的路上标记路径。 你可以做到这一点，因为每一步都会记住下一步之前的哪个方块。
相反，你在每一个你试过的方块上写上一个标记，只是说：我一直在这里，不需要再检查一次。 在打印解决方案之前将其清理干净。
递归实际上是一个简单的想法：解决一个问题，你将问题缩小一步，然后解决减少的问题。 这个过程会持续到你遇到一个你知道如何完全解决的“基本问题”。 您返回基本解决方案，然后添加到每个步骤返回的解决方案，直到获得完整解决方案。
所以要解决n！，我们记住n并解决（n-1）!. 基本情况是1！，为此我们返回1; 然后在每一个返回步骤，我们乘以记忆的数字（2 * 1！是2,3 * 2！是6，4 * 3！是24,5 * 4！是120），直到我们乘以n并且具有完全解。 这实际上是一个相当苍白和贫乏的递归; 每一步只有一个可能的决定。 被称为“尾递归”，这是很容易从里到外，并转换为迭代解决方案（从1开始，乘以每个数字到n）。
一个更有趣的递归方式是将问题分成两半，解决每一半，然后结合两个半解; 例如快速排序通过挑选一个项目对列表进行排序，将列表分为“小于项目的所有项目”和“比项目大的项目”，快速排序每个部分，然后返回快速排序（较小）+项目+快速排序（较大）。 基本情况是“当我的列表只有一个项目时，它被排序”。
对于迷宫来说，我们要从四个方面来分解问题 - 如果我从当前位置向右，向左，向上和向下移动，所有解决方案都可能实现 - 只有其中一个递归搜索实际上可以找到解决方案。 基本情况是“我站在E上”，失败是“我在墙上”或“我在我已经去过的空间”。
编辑：出于利益的考虑，这是一个OO解决方案（兼容Python 2.x和3.x）：
from collections import namedtuple
Dir = namedtuple("Dir", ["char", "dy", "dx"])
class Maze:
START = "S"
END = "E"
WALL = "#"
PATH = " "
OPEN = {PATH, END} # map locations you can move to (not WALL or already explored)
RIGHT = Dir(">", 0, 1)
DOWN = Dir("v", 1, 0)
LEFT = Dir("<", 0, -1)
UP = Dir("^", -1, 0)
DIRS = [RIGHT, DOWN, LEFT, UP]
@classmethod
def load_maze(cls, fname):
with open(fname) as inf:
lines = (line.rstrip("rn") for line in inf)
maze = [list(line) for line in lines]
return cls(maze)
def __init__(self, maze):
self.maze = maze
def __str__(self):
return "n".join(''.join(line) for line in self.maze)
def find_start(self):
for y,line in enumerate(self.maze):
try:
x = line.index("S")
return y, x
except ValueError:
pass
# not found!
raise ValueError("Start location not found")
def solve(self, y, x):
if self.maze[y][x] == Maze.END:
# base case - endpoint has been found
return True
else:
# search recursively in each direction from here
for dir in Maze.DIRS:
ny, nx = y + dir.dy, x + dir.dx
if self.maze[ny][nx] in Maze.OPEN: # can I go this way?
if self.maze[y][x] != Maze.START: # don't overwrite Maze.START
self.maze[y][x] = dir.char # mark direction chosen
if self.solve(ny, nx): # recurse...
return True # solution found!
# no solution found from this location
if self.maze[y][x] != Maze.START: # don't overwrite Maze.START
self.maze[y][x] = Maze.PATH # clear failed search from map
return False
def main():
maze = Maze.load_maze("somemaze.txt")
print("Maze loaded:")
print(maze)
try:
sy, sx = maze.find_start()
print("solving...")
if maze.solve(sy, sx):
print(maze)
else:
print(" no solution found")
except ValueError:
print("No start point found.")
if __name__=="__main__":
main()
并在运行时产生：
Maze loaded:
####################################
#S# ## ######## # # # # #
# # # # # # #
# # ##### ## ###### # ####### # #
### # ## ## # # # #### #
# # # ####### # ### #E#
####################################
solving...
####################################
#S# ## ######## # #>>>>>v# >>v# #
#v#>>v# >>>v #^# >>>>^#>>v#
#>>^#v#####^##v######^# ####### #v#
### #v##>>>^##>>>>>v#^# # ####v#
# #>>>^# #######>>^# ### #E#
####################################
请注意，赋予的赋值有几个非平凡的元素：
camelCase函数名称而不是underscore_separated find_start在失败时返回标志值而不是引发异常