python - 在 python 中使用递归解决迷宫

Question

所以，我有一个作业要求我使用递归解决迷宫问题。我将发布作业指南，以便您了解我在说什么。教授没有太多解释递归，他给了我们递归的例子，我会贴出来，但我希望有人能给我更深入的递归解释，以及我将如何应用它来解决问题一个迷宫。我不要求任何人编写代码，我只是希望一些解释能让我走上正确的道路。感谢任何回答的人。

以下是我的示例:

    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 坐标。您可以假设迷宫中至多存在一个这样的角色。如果在迷宫中未找到“S”，则返回 -1 作为 x 和 y 坐标。

在继续之前，在多个位置(包括没有位置)使用“S”测试您的代码。

问题 3 - 解迷宫!

最后，您可以递归地解决迷宫问题了!您的解决方案应该只需要一个方法:solve(y,x)

解决方法的单个实例应该解决迷宫中的单个位置。参数 y 和 x 是当前要求解的坐标。您的 solve 方法应该完成一些事情。它应该检查它当前是否正在解决“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]!= ' ')

Answer 1

(约会我自己，我实际上在高中时用 COBOL 做过这道题。)

您可以将解决迷宫视为采取步骤。

当您迈出一步时，每次都适用相同的规则。因为每次都应用相同的规则，所以您可以对每个步骤使用完全相同的指令集。当您采取一个步骤时，您只需再次调用相同的例程，更改参数以指示新的步骤。这就是递归。一步一步分解问题。

Note: Some recursion solutions break the problem in half, solving each half independent of the other, that works when the two solutions are actually independent. It doesn't work here because each step (solution) depends on the previous steps.

如果你遇到了死胡同，你就会退出死胡同，直到你找到仍然有可行的方 block 要检查的步骤。

Helpful Hint: You don't mark the correct path on the way to the exit, because you don't know that the step you're taking right now is part of the path to the exit. You mark the path on the way back, when you know that each step is indeed part of the path. You can do this because each step remembers which square it was in before it took the next step.

Instead, you put a mark in each square you've tried that only says: I've been here, no need to check this one again. Clean those up before you print the solution.