"Hamiltonian" 路径使用 Python

Question

我正在尝试使用 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 语句就会引用过程的某些内部调用，因此程序不会终止或 return 路径。

例如，取 G = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]}（即完整的 4-graph）和运行 hamilton(G,4,1,[])。它 returns None，但是如果你打印路径而不是 return 将它作为一个值，你会看到它实际上找到了从 1.[=19 开始的所有六个路径=]

如果我告诉程序将路径与 return 语句一起打印，它最终会打印所有此类路径，因此运行s 比需要的时间长得多。

如何修复代码，使其在找到第一个合适的路径后终止执行？

Answer 1

基本错误是递归调用的结果需要返回，如果它没有导致死胡同。

此外，如果 pt 点没有邻居，G[pt] 将引发 IndexError。使用 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

请注意，由于 "mutable default argument" 问题，多次使用该函数可能会导致错误结果。但这不是这个答案的范围。

Answer 2

这是一个没有递归 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

"Hamiltonian" 路径使用 Python

"Hamiltonian" path using Python

python

recursion

backtracking

recursive-backtracking

例子