Рекурсивная функция для поиска всех путей к определенной цели - PullRequest
Новая
       33

Рекурсивная функция для поиска всех путей к определенной цели

0 голосов
/ 23 марта 2019

Мне нужно найти самый длинный путь к данной цели.Данные представляют собой словарь идентификаторов со значением, представляющим список всех идентификаторов, которые указывают на этот идентификатор.Также стоит отметить, что каждый идентификатор может указывать только на один другой идентификатор.

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

def create(main, vec, id):
    if (id not in INFO):
        return(main, vec, id)
    else:
        for source in INFO[id]:
            vec.append(source)
            main.append(vec)
            main, vec, id = create(main, vec, source)
        return main,vec,id

и самая длинная функция 

def longest(main):
    longest = 0
    long_list = 0
    for list in main:
        if len(list) > longest:
            long_list = list
            longest = len(list)
    return long_list

при выполнении 

INFO = {
    'D4': ['B2','B6'],
    'B6': ['D3'],
    'D3': ['F1','A2'],
    'A2': ['G8'],
    'A1': ['C3'],
    'B2': ['E3','A1']}
main, vec, id = create([],[],'D4')
print(longest(main))

Я получаю main, чтобы пути располагались поверх друг друга.Как бы я исправить код, чтобы пути не складывались.Я надеюсь, что main будет выглядеть примерно так: 

[['B2'],
['B2','E3'],
['B2','A1'],
['B2','A1','C3'],
['B6'],
['B6','D3'],
['B6','D3','F1'],
['B6','D3','A2'],
['B6','D3','A2','G8']]

EDIT:

Изменена строка main, vec, id = create(main,[],'D4') на main, vec, id = create([],[],'D4'), чтобы уточнить, что main это списоксписков.

1 Ответ

0 голосов
/ 24 марта 2019

Из-за рекурсивного свойства вашего подхода сложно отследить путь между текущим узлом и начальным узлом (корнем).

Однако, когда вас интересует только самый длинный путь, он, безусловно, связывает корень и отпуск (это узлы, которые не имеют связи ни с каким другим узлом).

В следующем коде при достижении одного из листьев, т.е. когда currentNode not in INFO равно true, я путешествую вверх и записываю путь до достижения корня. 

def create(pathListRef, currentNode, rootNode):
    # pathListRef is the reference to the list containing the paths between all leaves and the root.
    # currentNode holds the current node, e.g. "D3"
    # rootNode holds reference to the root node, i.e. "D4"

    if (currentNode not in INFO):
        # We have reached on of the leaves

        reverseNode = currentNode
        # reverseNode is used to keep track of at which node we are when traveling back to the root.

        path = []
        # holds the relative path between the leave and reverseNode

        while reverseNode is not rootNode:
            # As long as we have not reached the root

            path.insert(0, reverseNode)
            # Prepend (like append, but at the start of the list) the reverseNode to the relative path

            reverseNode = list(INFO.keys())[[i for i,x in enumerate(list(INFO.values())) if reverseNode in x][0]]
            # Get the node linked with the reverseNode and move forward to that one. In essence get the key, where the value contains (since it is a list) the reverseNode.

        pathListRef.append(path)
        # We are at the root, so add the relative path to the final paths list
        return

    # This is only executed when we are not at the leave yet (since we return when we are at a leave)
    for source in INFO[currentNode]:
        create(pathListRef, source, rootNode)

Используется следующим образом: 

myList = []
startNode = "D4"
create(myList, startNode, startNode)
print(myList)  # -> [['B2', 'E3'], ['B2', 'A1', 'C3'], ['B6', 'D3', 'F1'], ['B6', 'D3', 'A2', 'G8']]

И используя функцию longest(), вы получаете: 

print(longest(myList))  # -> ['B6', 'D3', 'A2', 'G8']

Кстати, можно сократить вашу функцию longest() до следующей. Кроме того, этот код также возвращает несколько путей, если не существует только одного самого длинного. 

def longest(main):
    return [x for x in main if len(x) == max([len(x) for x in main])]
...