Решение лабиринта с использованием рекурсии в 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','#'], 
    ['#',' ','#',' ','#',' ',' ',' ','#'], 
    ['#',' ',' ',' ','#',' ','#',' ','#'], 
    ['#', #','#','#','#','#','#','#','#']] 

Обратите внимание, что списки были лишены всех «\ г» и ' \ n '. Чтобы упростить следующий вопрос, вы можете сделать этот список глобальной переменной.

Следующая написать функцию, которая выводит из лабиринта в гораздо более удобном формате:

Е.Г.,

#################################### 
    #S# ## ######## # #  #  # # 
    # # #    # #  # # 
    # # ##### ## ###### # ####### # # 
    ### # ## ##  # # #  #### # 
    # # # ####### # ### #E# 
    #################################### 

Проверьте свой код с различными лабиринтами перед продолжением.

Вопрос 2 - Подготовка к решению лабиринту

Перед тем, как можно решить лабиринт вам нужно найти отправную точку! Добавьте функцию в свой код под названием findStart(), который будет искать лабиринт (по-символу) и возвращать координату x и y символа «S». Вы можете предположить, что в лабиринте существует не более одного такого персонажа. Если в лабиринте return -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]!= ' ') 

Answer 1

Рекурсия на самом деле простая идея: чтобы решить проблему, вы уменьшить проблему на один шаг, а затем решить проблему пониженной. Это продолжается до тех пор, пока вы не достигнете «базовой проблемы», которую вы знаете, как решить полностью. Вы возвращаете базовое решение, затем добавляете к решению, возвращаемому на каждом шагу, пока не получите полное решение.

Итак, чтобы решить n !, мы помним n и решаем для (n-1) !. Базовый регистр равен 1 !, для которого мы возвращаем 1; то на каждом шаге возврата умножим на запоминаемое число (2 * 1! 2, 3 * 2! 6, 4 * 3! 24, 5 * 4! - 120), пока мы не умножим на n и не получим полного решения , Это на самом деле довольно бледная и анемичная рекурсия; на каждом шаге есть только одно возможное решение. Известный как «хвостовая рекурсия», это очень легко превратить наизнанку и преобразовать в итерационное решение (начинаться с 1 и умножать на каждое число до n).

Более интересный вид рекурсии - это то, где вы разбиваете проблему пополам, решаете каждую половину, затем объединяете два полурешения; например quicksort сортирует список, выбирая один элемент, разделяя список на «все меньше, чем элемент» и «все, что больше, чем элемент», быстро сортирует каждую половину, а затем возвращает quicksorted (меньше) + item + quicksorted (больше). Основной случай - «когда мой список - это только один элемент, он сортируется».

Для лабиринта мы собираемся разделить проблему четырьмя способами - все решения возможны, если я иду вправо, влево, вверх и вниз от своего текущего местоположения - со специальной особенностью, которая на самом деле будет только одним из рекурсивных поисков найти решение. Основной случай: «Я стою на Е», а неудача - «Я нахожусь в стене» или «Я нахожусь в пространстве, которое я уже посетил».

---

Edit: ради интерес к, вот это решение OO (совместим с 2.x Python и 3.х):

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 возвращать значения флага на провал, а не поднимая исключение

Answer 2

(Встречаюсь себя, я на самом деле эта проблема в COBOL, в средней школе.)

Вы можете думать о решении лабиринт как шаги.

Когда вы делаете шаг, те же правила применяются каждый раз. Поскольку одни и те же правила применяются каждый раз, вы можете использовать один и тот же набор инструкций для каждого шага. Когда вы делаете шаг, вы просто вызываете ту же самую процедуру снова, изменяя параметры, чтобы указать новый шаг. Это рекурсия. Вы нарушаете проблему, делая это шаг за шагом.

Примечание. Некоторые решения для рекурсии ломают проблему пополам, решая каждую половину независимо от другой, которая работает, когда два решения фактически независимы. Он не работает здесь, потому что каждый шаг (решение) зависит от предыдущих шагов.

Если вы зашли в тупик, вы возвращаетесь из тупика, пока не найдете шаг, на котором есть все еще жизнеспособные квадраты для проверки.

Полезный совет: Вы не отметить правильный путь на пути к выходу, потому что вы не знаете, что шаг, который вы везете сейчас является частью пути к выходу. Вы отмечаете путь на обратном пути, когда вы знаете, что каждый шаг действительно является частью пути. Вы можете сделать это, потому что каждый шаг запоминает, в каком квадрате он находился, прежде чем он сделал следующий шаг.

Вместо этого вы помещаете отметку на каждый квадрат, который вы пробовали, и только говорит: «Я здесь, вам не нужно снова проверять это. Перед тем, как распечатать решение, очистите их.

Answer 3

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 с потенциальными путями, показывающими один цвет и фактический путь в другом цвете, чтобы вы могли видеть, как он пытается, а затем преуспевает.

Answer 4

Вот мое решение The Labirynth вызов CodeEval в:

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)