Как заставить мой рекурсивный алгоритм останавливаться после достижения цели? - PullRequest
Новая
       48

Как заставить мой рекурсивный алгоритм останавливаться после достижения цели?

0 голосов
/ 26 октября 2019

Я пытаюсь решить проблему для следующего вопроса.

Find path for a robot in a maze from top left corner to bottom right corner. The robot can move only to the right or bottom. There are certain restricted areas where the robot cannot go into.

Моя идея состоит в том, чтобы сначала использовать поиск по глубине, сначала направо, а затем снизу. Мой алгоритм работает. Но я стал довольно ржавым с рекурсией. Я не могу вернуть вывод правильно. Это мой код 

def robot_path(r, c, off_limits):
    """
    r -> number of rows in grid
    c -> number of columns in grid
    off_limits -> nested list containing positions of restricted areas
    """
    grid = list()
    for i in range(0, r):
        grid.append([1] * c)
    for off_limit in off_limits:
        grid[off_limit[0]][off_limit[1]] = 'X'
    path = list()
    return __move(grid, (0,0), path, (r-1, c-1))

def __move(grid, position, path, target):
    if position == target:
        return path
    x = position[0]
    y = position[1]
    if x < len(grid) and y < len(grid[0]):
        if grid[x][y] != 'X':
            path.append(1)
            __move(grid, (x, y+1), path, target)
            path.pop()
            path.append(0)
            __move(grid, (x+1, y), path, target)
            path.pop()

Как мне вернуть путь? В списке path 0 означает перемещение дна, а 1 означает перемещение вправо. Тем не менее, мой алгоритм не останавливается, как только он достигает правого нижнего угла. Он запускается даже после этого, и я получаю вывод None. Как мне изменить это, чтобы вернуть мой путь, как только будет достигнут нижний правый угол.

Тестовый вывод

robot_path(4, 4, [[0,2], [2,2], [3,0], [3, 1]])

должен вернуть

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

1 Ответ

0 голосов
/ 26 октября 2019

Не просто давая ответ, я бы предложил подумать о следующем

  • Вторая функция не имеет return во всех путях, только в первом if
  • Рекурсивные функции обычно не комбинируются с изменяемыми объектами. Ваш объект пути видоизменяется с помощью pop(). Обычно в рекурсивных функциях становится понятнее, если объекты только передаются и возвращаются, а не мутируют inline

Например: 

def sum(l):
    if len(l) == 0:
        return 0
    return l[0] + sum(l[1:])

Хвост передается следующей функции, результатпередается обратно вверх по цепочке. Сам список не видоизменяется в функции sum(), он просто разбивается на части с целью передачи вниз.

...