“汉密尔顿"使用 Python 的路径 [英] "Hamiltonian" path using Python

问题描述

我正在尝试使用 Python 实现对遍历所有图顶点的任意路径(不一定是循环)的递归搜索.这是我的代码:

I am trying to implement a recursive search for an arbitrary path (not necessarily a cycle) traversing all graph vertices using Python. Here's my code:

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 语句就会引用过程的某个内部调用，因此程序不会终止或返回路径.

Here, pt is the starting point and path is the list of all previously traversed vertices not including pt, empty by default. The problem is, whenever such a path is found, the return statement refers to some inner call of the procedure and therefore the program does not terminate or return the path.

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

For example, take G = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]} (i.e. the complete 4-graph) and run hamilton(G,4,1,[]). It returns None, but if you print the path instead of returning it as a value, you'll see that it actually finds all six paths starting at 1.

如果我告诉程序连同 return 语句一起打印路径，它最终会打印所有这些路径，因此运行时间比需要的要长得多.

If I tell the program to print the path together with the return statement, it eventually prints all such paths and hence runs much longer than needed.

如何修复代码以便在找到第一个合适的路径后终止执行?

How can I fix the code so that it would terminate the execution after the first suitable path is found?

推荐答案

基本错误是递归调用的结果需要返回，如果没有导致死机.

The basic mistake is that the result of the recursive call needs to be returned, if it didn't lead to a dead end.

此外，如果点 pt 没有邻居，G[pt] 将引发 IndexError.这可以通过使用 dict.get 轻松解决.

In addition, G[pt] will raise an IndexError if the point pt has no neighbors. This can easily be fixed by using 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

请注意，由于可变默认参数"问题，多次使用该函数可能会导致错误结果.但这不是这个答案的范围.

Note that using the function more than once can lead to wrong results because of the "mutable default argument" problem. But that's not the scope of this answer.

这篇关于“汉密尔顿"使用 Python 的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！