Ошибка превышения максимальной глубины рекурсии при поиске кратчайшего пути - PullRequest
Новая
       7

Ошибка превышения максимальной глубины рекурсии при поиске кратчайшего пути

0 голосов
/ 06 февраля 2020

Я пытаюсь найти кратчайшую точку от источника к цели, но получаю ошибку: RecursionError: maximum recursion depth exceeded while calling a Python object

Вот мой код, где neighbors_for_id возвращает список идентификаторов соседей источника: 

    """
    Returns the shortest list of person_ids that connect the source to the target.

    If no possible path, returns None.
    """
    visited = set()
    path = []
    if source == target:
        return path
    while source != target:
        destinations = neighbors_for_id(source)
        for neighbor in destinations:
            path.append(neighbor)
            if neighbor == target:
                return path
            if neighbor not in visited:
                visited.add(neighbor)
                source = neighbor
                shortest_path(source, target, visited)```

1 Ответ

1 голос
/ 06 февраля 2020

2 вещи:

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

когда вы вызываете функцию извне, чтобы запустить ее, просто пропустите пустой набор: 

shortest_path(source, target, set())

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

Вы можете немного очистить его с помощью значений по умолчанию, таких как: 

def shortest_path(source, target, visited=set(), path=list() ):
...