Создайте все гамильтоновы пути из списка ребер

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

Я продолжаю приближаться, но пропускаю какой-то путь.

Например, допустим, у нас есть этот список соединений:

connections = [(1, 4), (1, 5), (2, 5), (3, 4), (4, 1), (4, 3), (4, 5), (5, 1), (5, 2), (5, 4)]

желаемый результат:

[[1,4,3], [1,4,5,2], [1,5,2], [1,5,4,3], 
 [2,5,1,4,3], [2,5,4,1], [2,5,4,3],
 [3,4,1,5,2], [3,4,5,1], [3,4,5,2], 
 [4, 3], [4,1,5,2], [4,5,1], [4,5,2],
 [5, 2], [5,1,4,3], [5,4,1], [5,4,3]
]

Таким образом, каждый возможный путь сохраняется, и каждый узел посещается только один раз:

Вот что у меня есть, но не хватает многих путей:

def find_paths(current_vertex):
    if current_vertex not in current_path:
        current_path.append(current_vertex)

    possible_next_verticies = [v2 for v1,v2 in connections if v1 == current_vertex]

    # if the current vertex is in the current_path
    if current_vertex in current_path:
        # if all the possible_next_vertices are in the current_path, return
        adjacencies = [v for v in possible_next_verticies if v not in current_path]
        if not adjacencies:
            print "current_path: %s" % current_path
            if current_path not in TESTED_PATHS:
                TESTED_PATHS.append(current_path)
            current_path.remove(current_vertex)
            return

    for next_vertice in possible_next_verticies:
        if next_vertice not in current_path:
            current_path.append(next_vertice)
            find_paths(next_vertice)
            continue
        else:
            continue

    return current_path

python recursion tree-traversal hamiltonian-cycle
person yekta    schedule 14.02.2015    source источник
comment
Направлены ли края? т. е. разрешен ли путь в любом направлении для каждого указанного вами ребра? Достаточно ли посетить каждый узел ровно один раз, или вам действительно требуется цикл, когда он возвращается к первому узлу в конце? Пожалуйста, отредактируйте вопрос соответствующим образом   -  person Aaron McDaid    schedule 14.02.2015
comment
Мне не нужно, чтобы он возвращался к первому узлу, а просто посещал все возможные узлы (из каждого узла), посещая каждый узел только один раз.   -  person yekta    schedule 14.02.2015
comment
@yekta: тогда это гамильтонов путь, а не гамильтонов цикл?   -  person Willem Van Onsem    schedule 14.02.2015
comment
Да, это не цикл, мне просто нужен путь.   -  person yekta    schedule 14.02.2015

Ответы (1)


arrow_upward
3
arrow_downward

Хорошо, у меня было так много проблем из-за структуры данных, с которой я пытался работать, поскольку в исходном графе соединений были дубликаты.

Лучше использовать такую ​​структуру данных:

connections = {1: [4, 5], 2: [5], 3: [4], 4: [1, 3, 5], 5: [1, 2, 4]}

Затем можно использовать следующие два алгоритма из https://www.python.org/doc/essays/graphs/

def find_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not graph.has_key(start):
        return None
    for node in graph[start]:
        if node not in path:
            newpath = find_path(graph, node, end, path)
            if newpath: return newpath
    return None

и для полных путей

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths
person yekta    schedule 14.02.2015
comment
Улучшили ли вы свое решение с течением времени? :) - person Nikolay Fominyh; 14.02.2016
comment
Это, кажется, не решает ваш первоначальный вопрос. Он находит путь от определенного начального узла к определенному конечному узлу, но вам нужен гамильтонов путь, который может начинаться и заканчиваться на любом узле (судя по желаемому результату). Ваш ответ может легко пройти через все начальные узлы, но получение всех гамильтоновых путей к произвольным конечным узлам с этим алгоритмом кажется более сложным. - person tobiasvl; 02.10.2018
comment
Вы можете перебирать все вершины и выполнять эту функцию каждый раз. Но это очень неэффективно, это займет вечность при работе с DAG с ‹ 1000 вершин. - person nosense; 13.12.2019