在python中使用递归解决迷宫-Java 学习之路

所以，我有一个任务，要求我使用递归解决迷宫 . 我将发布作业指南，以便您可以看到我在说什么 . 教授没有解释这么多的递归，他给了我们递归的例子，我将发布，但我希望有人能够给我一个更深入的递归解释，以及我如何将其用于解决一个迷宫 . 我不是要求任何人编写代码，我只是希望一些解释会让我走上正确的道路 . 谢谢任何回答的人 .

Here are the examples I have:

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

Here are the guidelines:

你将创建一个迷宫爬行器，能够通过递归的力量解决你给它的任何迷宫！

问题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是要求解的当前坐标 . 你的解决方法应该完成一些事情 . 它应该检查它当前是否正在解决'E'的位置 . 在这种情况下，您的求解方法已成功完成 . 否则它应该尝试递归地解决右边的空间 . 注意，你的方法应该只尝试解决空间，而不是墙（'＃'） . 如果该递归没有导致结束，那么尝试下来，然后向左，向上 . 如果全部失败，您的代码应该回溯一步，并尝试另一个方向 .

最后，在解决迷宫时，您的代码应该留下其进度的指标 . 如果它向右搜索，则当前位置应该有一个'>'来代替空白区域 . 如果搜索下来放'v' . 如果向左搜索“<”，则向上搜索“^” . 如果您的代码必须回溯删除方向箭头，并将位置设置回'' .

一旦你的迷宫解决了，再次打印出迷宫 . 您应该看到走迷宫的分步指南 . 例如 . ，

main("somemaze.maze")
    ######### 
    #S#   #E# 
    # # #   # 
    #   # # # 
    #########

S在（1,1）

######### 
     #S#>>v#E# 
     #v#^#>>^# 
     #>>^# # # 
     #########

使用不同的开始和结束位置以及可选的各种迷宫测试代码 .

Here is the code I have so far: 但是代码实际上并没有在迷宫中打印轨道，我不知道为什么 .

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]!= ' ')

4 回答

这是我对CodeEval的The 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)

回复于 2024-04-28T08:12:58+08:00

1

（约会自己，我实际上在COBOL，高中时就已经解决了这个问题 . ）

您可以考虑将迷宫解决为采取措施 .

当您采取措施时，每次都适用相同的规则 . 由于每次都适用相同的规则，因此您可以对每个步骤使用完全相同的指令集 . 当您迈出一步时，您只需再次调用相同的例程，更改参数以指示新步骤 . 这是递归 . 你可以一步一步地解决问题 .

注意：一些递归解决方案将问题分成两半，独立解决另一半问题，这两个解决方案实际上是独立的 . 它在这里不起作用，因为每个步骤（解决方案）取决于前面的步骤 .

如果你走到了死胡同，你就会退出死胡同，直到找到一个仍然可以检查的方格的步骤 .

有用的提示：你没有在出口的路上标记正确的路径，因为你不知道你现在采取的步骤是退出路径的一部分 . 当您知道每个步骤确实是路径的一部分时，您可以在返回途中标记路径 . 您可以执行此操作，因为每个步骤都会记住它在下一步之前所处的位置 . 相反，你在你试过的每个方格中都加了一个标记，只说：我来过这里，不需要再检查一下 . 在打印解决方案之前清理它们 .

回复于 2024-04-28T08:12:58+08:00

递归实际上是一个简单的想法：要解决问题，您将问题缩小一步，然后解决减少的问题 . 这一直持续到你遇到一个你知道如何完全解决的“基本问题” . 您返回基本解决方案，然后添加到每个步骤返回的解决方案，直到您拥有完整的解决方案 .

所以要解决n !,我们记住n并求解（n-1）！基本情况是1 !,我们返回1;然后在每个返回步骤，我们乘以记忆的数字（2 * 1！是2,3 * 2！是6,4 * 3！是24,5 * 4！是120），直到我们乘以n并得到完整解 . 这实际上是一种非常苍白和贫血的递归;每一步都只有一个可能的决定 . 被称为“尾递归”，这很容易从里到外转换并转换为迭代解决方案（从1开始并乘以每个数字直到n） .

一种更有趣的递归方法是将问题分成两半，求解每一半，然后合并两个半解;例如，快速排序通过选择一个项目对列表进行排序，将列表划分为“小于项目的所有内容”和“大于项目的所有内容”，快速分配每一半，然后返回快速排序（较小）项目快速排序（更大） . 基本情况是“当我的列表只有一个项目时，它被排序” .

对于迷宫，我们将以四种方式分解问题 - 如果我从当前位置向右，向左，向上和向下移动，所有解决方案都可能 - 特殊功能是只有一个递归搜索实际上会找到解决方案 . 基本情况是“我站在E”，失败是“我在墙上”或“我在一个我已经去过的空间” .

Edit: 为了感兴趣，这是一个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("\r\n") 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#
    ####################################

请注意，给定的赋值有一些unPythonic元素：

它要求 camelCase 函数名而不是 underscore_separated
它建议使用全局变量而不是显式传递数据
它要求 find_start 在失败时返回标志值而不是引发异常

回复于 2024-04-28T08:12:58+08:00

Maze solving with python显示了我的答案 . 但是，如果您想自己完成代码，请执行以下步骤 .

1. Start at the entrance.  
 2. Call the function solve(x,y) with the entrance co-ordinates  
 3. in solve, return false if the input point has already been handled or is a wall.  
 4. Mark the current point as handled (tag = 'o')  
 5. go to the right and call solve on that point. If it returns true, set tag to '>'  
 6 elif do the same for left and '<'  
 7 elif do the same for up and '^'  
 8 elif do the same for down and 'v'  
 9 else this is a false path, set tag = ' ' 
10 set the current maze point to tag
11 return (tag != ' ')

或者，将步骤9退出并进行步骤11

return(tag != 'o')

然后搜索迷宫并用''替换每个'o'

您可以双向显示迷宫，以便显示您尝试解决它的方式以及最终答案 . 这已被用作Solaris屏幕保护程序，潜在路径以一种颜色显示，实际路径以不同颜色显示，以便您可以看到它尝试然后成功 .

回复于 2024-04-28T08:12:58+08:00

在python中使用递归解决迷宫

4 回答

相关问题