Гамильтонов путь с использованием Python

Я пытаюсь реализовать рекурсивный поиск произвольного пути (не обязательно цикла), пересекающего все вершины графа с использованием Python. Вот мой код:

def hamilton(G, size, pt, path=[]):
    if pt not in set(path):
        path.append(pt)
        if len(path)==size:
            return path
        for pt_next in G[pt]:
            res_path = [i for i in path]
            hamilton (G, size, pt_next, res_path)

Здесь pt — начальная точка, а path — список всех ранее пройденных вершин, не включая pt, по умолчанию пустой. Проблема в том, что всякий раз, когда такой путь найден, оператор return ссылается на какой-то внутренний вызов процедуры, и поэтому программа не завершает работу и не возвращает путь.

Например, возьмите G = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]} (то есть полный 4-граф) и запустите hamilton(G,4,1,[]). Он возвращает None, но если вы напечатаете путь вместо того, чтобы возвращать его как значение, вы увидите, что на самом деле он находит все шесть путей, начиная с 1.

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

Как исправить код, чтобы он прекращал выполнение после нахождения первого подходящего пути?


python recursion backtracking recursive-backtracking
person Max    schedule 26.12.2017    source источник
comment
Вы можете посмотреть здесь.   -  person bgse    schedule 26.12.2017
comment
Можете ли вы добавить небольшой пример ввода для функции, демонстрирующий проблему?   -  person mkrieger1    schedule 26.12.2017
comment
@bgse: Вы имеете в виду, что изменяемый аргумент пути по умолчанию является подвохом? Я удалил его, и, похоже, ничего не изменилось.   -  person Max    schedule 26.12.2017
comment
@mkrieger1: например, возьмите G = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]} (т.е. полный 4-граф) и запустить hamilton(G,4,1,[]). Он возвращает объект NoneType, но если вы напечатаете путь вместо того, чтобы возвращать его как значение, вы увидите, что на самом деле он находит все шесть путей, начиная с 1.   -  person Max    schedule 26.12.2017

Ответы (2)


arrow_upward
4
arrow_downward

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

Кроме того, G[pt] вызовет IndexError, если у точки pt нет соседей. Это легко исправить с помощью dict.get.

def hamilton(G, size, pt, path=[]):
    print('hamilton called with pt={}, path={}'.format(pt, path))
    if pt not in set(path):
        path.append(pt)
        if len(path)==size:
            return path
        for pt_next in G.get(pt, []):
            res_path = [i for i in path]
            candidate = hamilton(G, size, pt_next, res_path)
            if candidate is not None:  # skip loop or dead end
                return candidate
        print('path {} is a dead end'.format(path))
    else:
        print('pt {} already in path {}'.format(pt, path))
    # loop or dead end, None is implicitly returned

Примеры

>>> G = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]}
>>> hamilton(G, 4, 1)
hamilton called with pt=1, path=[]
hamilton called with pt=2, path=[1]
hamilton called with pt=1, path=[1, 2]
pt 1 already in path [1, 2]
hamilton called with pt=3, path=[1, 2]
hamilton called with pt=1, path=[1, 2, 3]
pt 1 already in path [1, 2, 3]
hamilton called with pt=2, path=[1, 2, 3]
pt 2 already in path [1, 2, 3]
hamilton called with pt=4, path=[1, 2, 3]
[1, 2, 3, 4]

>>> G = {1:[2], 2:[3,4], 4:[3]}
>>> hamilton(G, 4, 1)
hamilton called with pt=1, path=[]
hamilton called with pt=2, path=[1]
hamilton called with pt=3, path=[1, 2]
path [1, 2, 3] is a dead end
hamilton called with pt=4, path=[1, 2]
hamilton called with pt=3, path=[1, 2, 4]
[1, 2, 4, 3]

>>> G = {1:[2], 2:[3,4], 4:[3]}
>>> hamilton(G, 4, 2)
hamilton called with pt=2, path=[]
hamilton called with pt=3, path=[2]
path [2, 3] is a dead end
hamilton called with pt=4, path=[2]
hamilton called with pt=3, path=[2, 4]
path [2, 4, 3] is a dead end
path [2, 4] is a dead end
path [2] is a dead end
None

Обратите внимание, что использование функции более одного раза может привести к неправильным результатам из-за проблемы «изменяемого аргумента по умолчанию». Но это не тема этого ответа.

person mkrieger1    schedule 27.12.2017
comment
Спасибо за подробный ответ! Я проверю другие подходы, но, похоже, ваша модификация для генерации одного пути не всегда работает: скажем, для G={1:[2], 2:[3,4], 4:[3]} он застревает на 3 и выдает ошибку. - person Max; 27.12.2017
comment
@Max Хорошо заметил. На самом деле есть две проблемы. Первый пытается получить соседей точки, не имеющей соседей, которая уже существует в исходном коде. Во-вторых, проблема в алгоритме - оказывается, то, что я написал, тоже не соответствует действительности, и ваш исходный вариант можно легко исправить. Мне нужно обновить ответ. - person mkrieger1; 27.12.2017
comment
G = {0:[1], 1:[0, 2], 2:[1, 3], 3:[2, 4, 5], 4:[3, 6], 5:[3], 6:[4]} Попытка с этим, кажется, дает неверные результаты, просто на заметку. Я знаю, что это старое решение, но я бы сказал, что, возможно, изменение имени функции с hamilton в этом вопросе имеет смысл, поскольку любой OP не требует полностью правильного решения с точки зрения пути hamilton. - person Zeromika; 11.11.2019
comment
Как решить проблему с изменяемым аргументом по умолчанию? - person nosense; 13.12.2019

arrow_upward
4
arrow_downward

Вот решение без рекурсии DFS для поиска пути гамильтона из определенной вершины start_v.

сделано для графового представления hashmap массивов:

G = {0:[1], 1:[0, 2], 2:[1, 3], 3:[2, 4, 5], 4:[3, 6], 5:[3], 6:[4]}

def hamilton(graph, start_v):
  size = len(graph)
  # if None we are -unvisiting- comming back and pop v
  to_visit = [None, start_v]
  path = []
  while(to_visit):
    v = to_visit.pop()
    if v : 
      path.append(v)
      if len(path) == size:
        break
      for x in set(graph[v])-set(path):
        to_visit.append(None) # out
        to_visit.append(x) # in
    else: # if None we are comming back and pop v
      path.pop()
  return path

можно ускорить, если представить граф хэш-картой наборов:

G = {0:{1}, 1:{0, 2}, 2:{1, 3}, 3:{2, 4, 5}, 4:{3, 6}, 5:{3}, 6:{4}}

а также поддерживать посещаемый набор и не использовать set(path)

Тогда решение будет немного быстрее:

def hamilton(graph, start_v):
  size = len(graph)
  # if None we are -unvisiting- comming back and pop v
  to_visit = [None, start_v]
  path = []
  visited = set([])
  while(to_visit):
    v = to_visit.pop()
    if v : 
      path.append(v)
      if len(path) == size:
        break
      visited.add(v)
      for x in graph[v]-visited:
        to_visit.append(None) # out
        to_visit.append(x) # in
    else: # if None we are comming back and pop v
      visited.remove(path.pop())
  return path
person Dmitry Sergeev    schedule 31.01.2020
comment
Это терпит неудачу на первой итерации, пытаясь вытолкнуть из пустого списка. - person Prune; 18.03.2021