После увеличения лимита рекурсии Python программа вылетает.Зачем? - PullRequest
Новая
       41

После увеличения лимита рекурсии Python программа вылетает.Зачем?

0 голосов
/ 30 мая 2018

Я пытался решить лабиринт с помощью возврата.Код использует несколько рекурсий: 

def solve_maze(x,y):    
        if maze[x][y] == 'G': #checking if we've reached the target
            solution[x][y] = 1
            return True
        if x>=0 and y>=0 and x<length and y<width and solution[x][y] == 0 and maze[x][y] == ' ':
            solution[x][y] = 1
            if solve_maze(x+1, y):
                return True
            if solve_maze(x, y+1):
                return True
            if solve_maze(x-1, y):
                return True
            if solve_maze(x, y-1):
                return True
            solution[x][y] = 0
            return False

При первом запуске программы появилась ошибка «Превышен предел рекурсии».Чтобы исправить это, я увеличил лимит: 

sys.setrecursionlimit(10000)

Теперь, когда я запускаю программу, происходит сбой Python.Что происходит?как я могу решить это?Лабиринт не очень большой.его размеры 10 * 9: 

maze = [['#'] * 10,
        ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', '#', ' ', '#', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', '#', '#', '#', ' ', '#', '#'],
        ['#', ' ', '#', '#', '#', '*', '#', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', ' ', ' ', '#', '#', ' ', '#'],
        ['#', ' ', '#', ' ', '#', '#', '#', '#', ' ', '#'],
        ['G', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
        ['#'] * 10]

*, это добавляется позже: в конце определения solve_maze был этот кусок кода: 

if solve_maze(x, y):
        for i in solution:
            print(i)
    else:
        print('no solution')

Я заметил, удалив его,программа работает нормально. До сих пор понятия не имею, почему

Ответы [ 3 ]

0 голосов
/ 30 мая 2018

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

  1. проблема связана с переполнением стека.
  2. редактирование этого предела не рекомендуется.
  3. рекурсия по умолчаниюпредел глубины довольно велик, и если программа продолжает превышать предел, это признак того, что в коде есть какая-то ошибка.
  4. оператор if solve_maze(x, y):, находящийся в теле определения solve_maze, был причинойбесконечная рекурсия.

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

0 голосов
/ 30 мая 2018

Глубина рекурсии глубже, чем необходимо для решения проблемы лабиринта.

Максимальная глубина рекурсии не должна быть намного глубже, чем " длина вашего пути довыход ».Длина вашего пути составляет 33 (= шаги, которые необходимо выполнить на карте 10 * 9 плиток до того, как будет достигнут выход).

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

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

0 голосов
/ 30 мая 2018

Заполнение недостающих частей вашего кода, похоже, работает: 

from pprint import pprint

maze = [['#'] * 10,
        ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', '#', ' ', '#', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', '#', '#', '#', ' ', '#', '#'],
        ['#', ' ', '#', '#', '#', '*', '#', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', ' ', ' ', '#', '#', ' ', '#'],
        ['#', ' ', '#', ' ', '#', '#', '#', '#', ' ', '#'],
        ['G', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
        ['#'] * 10]

length = len(maze)
width = len(maze[0])
solution = [[0 for _ in range(width)] for _ in range(length)]


def solve_maze(x, y):
    if maze[x][y] == 'G':  # checking if we've reached the target
        solution[x][y] = 1
        return True
    if x >= 0 and y >= 0 and x < length and y < width and solution[x][y] == 0 and maze[x][y] in ' *':
        solution[x][y] = 1
        if solve_maze(x + 1, y):
            return True
        if solve_maze(x, y + 1):
            return True
        if solve_maze(x - 1, y):
            return True
        if solve_maze(x, y - 1):
            return True
        solution[x][y] = 0
        return False


solve_maze(4, 5)
pprint(solution)

Единственное, что я изменил в solve_maze, это изменение maze[x][y] == ' ' на maze[x][y] in ' *', чтобы начальная позиция не изменялась.не ломайте его.

Вывод: 

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [0, 1, 0, 0, 0, 0, 0, 1, 1, 0],
 [0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
 [0, 1, 0, 0, 0, 1, 0, 1, 1, 0],
 [0, 1, 0, 1, 1, 1, 0, 0, 1, 0],
 [0, 1, 0, 1, 0, 0, 0, 0, 1, 0],
 [1, 1, 0, 1, 1, 1, 1, 1, 1, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

Если вы хотите узнать, что случилось с вашим кодом, вам необходимо предоставить MCVE .

...