编写一个 Python 函数来查找图中的哈密顿路径

Question

我正在尝试编写一个函数，它将一个正整数 n 作为输入，并将整数 1 到 n 排序，使得每个相邻数字的总和是一个完美的平方（如果这样的顺序存在）。我意识到，如果我创建一个顶点是数字的图，并且如果两个顶点之和是一个完美的平方，则两个顶点之间有一条边，那么这个问题就等同于试图在图中找到哈密顿路径。因此，我正在尝试编写一个函数，该函数将在给定图中找到哈密顿图（如果存在）。这是我的代码：

def hampath_finder(moves, start, path=None):
    if path is None:
        path = []
    if len(path) == bound:
        return path
    if not path:
        path = path + [start]
    for candidate in moves[start]:
        if candidate not in path:
            path = path + [candidate]
            new_path = hampath_finder(moves, candidate, path)
            if new_path:
                return new_path
            else:
                continue
    else:
        return None
    return None

"Moves"是一个图的字典（变量"graph"已经被使用了，我不擅长命名变量），其中每个顶点是一个键，每个键的值是一个列表包含与关键顶点相邻的其他顶点。比如当输入为15时，字典是这样的：

{1: [3, 8, 15], 2: [7, 14], 3: [1, 6, 13], 4: [5, 12], 5: [4, 11], 6: [3, 10], 7: [2, 9], 8: [1], 9: [7], 10: [6, 15], 11: [5, 14], 12: [4, 13], 13: [3, 12], 14: [2, 11], 15: [1, 10]}

Start 是哈密顿路径的起点。（我曾尝试在没有起点的情况下编写此函数，以便函数本身尝试将每个点作为起点，但它变得复杂了。现在，我只是自己遍历所有顶点。）

我知道对于数字 15，它应该给我以下列表：

[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]

但是，它给了我这个列表：

[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 1, 8, 15, 10, 6]

仔细想想这个函数是如何运行的，我意识到一旦它到达1，它首先将8作为下一个数字。但是，8 在除 1 以外的顶点之间没有边。老实说，我不知道它接下来会做什么。我意识到一旦没有可能的候选人可以尝试，它就需要回溯并回到上次正常的位置。我不知道如何实现这个。

我该如何解决这个问题？另外，我该如何改进我的代码？

我是 Python 的新手，如果这个问题很琐碎或者我的代码很糟糕，我深表歉意。

编辑：我想我解决了主要问题，现在 return 是正确的列表。这是新代码：

def hampath_finder(moves, start, path=None):
    if path is None:
        path = []
    if len(path) == bound:
        return path
    if not path:
        path = path + [start]
    for candidate in moves[start]:
        if candidate not in path:
            new_path = hampath_finder(moves, candidate, path + [candidate])
            if new_path:
                return new_path

我认为问题在于，一旦我们走到死胡同，错误的路径已经附加到列表中 path，这就是为什么前面代码的输出中有一个 8 .

现在，问题是函数 returns None 在 returning 列表之后。所以，这是当我运行这个函数用于数字 15 时的输出，即图表是我之前提到的字典：

[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]
None

我该如何解决这个问题，使其不会 return None？顺便说一句，我仍然必须自己尝试每个数字作为起点。这是我的做法：

for number in range(1, 16):
    if hampath_finder(moves, number):
        print(hampath_finder(moves,number))

换句话说，我必须手动尝试将每个数字作为路径的开始。如何调整原始函数，使其不需要起点，并自行尝试所有可能的数字？

此外，即使对于小数字，此函数也需要很长时间。我怎样才能让它更有效率？

编辑：我意识到包含 entire 函数而不是仅包含哈密顿路径部分更有用，因为一些变量未定义。

from math import sqrt


def adjacent_square(bound):
    def blueprint(bound):
        graph = {}
        for number in range(1, bound + 1):
            pos_neighbours = []
            for candidate in range(1, bound + 1):
                if sqrt(number + candidate) == int(sqrt(number + candidate)) and number != candidate:
                    pos_neighbours.append(candidate)
            graph[number] = pos_neighbours
        return graph

    graph = blueprint(bound)

    def hampath_finder(mapping, start, path=None):
        if path is None:
            path = []
        if len(path) == bound:
            return path
        if not path:
            path = path + [start]
        for candidate in mapping[start]:
            if candidate not in path:
                new_path = hampath_finder(mapping, candidate, path + [candidate])
                if new_path:
                    return new_path

    for num in range(1, bound+1):
        if hampath_finder(graph, num):
            print(hampath_finder(graph, num))
            break
    else:
        print("No such order exists.")

函数 blueprint 通过检查每个可能对的总和来创建图形。我已经解释过了 hampath_finder。之后，我尝试使用 for 循环将每个数字作为路径的起点。

Answer 1

我认为你得到 None 的原因是因为在 hampath_finder 函数中你只是 return 一个值 if new_path:。如果没有新路径和函数 returns，那么 Python 将 return None。你可以通过这个例子看到：

def testfunct(test):
  if test:
    return True

print(testfunct(False))

>>> None

此外，您正在计算 hampath_finder 两次。一次查看它是否存在，然后再次打印它。我会更改您代码的这一部分：

for num in range(1, bound+1):
    if hampath_finder(graph, num):
       print(hampath_finder(graph, num))
       break

更像这样：

for num in range(1, bound+1):
    this_path = hampath_finder(graph, num)
    if len(this_path) > 0:
       print(this_path)
       break

这将有助于提高速度。

不过粗看一下Hamiltonian Path Problem好像是个NP完全问题。所以它会很慢。有些研究论文的实现速度更快，但超出了 Whosebug 的范围。此外，如果需要速度，那么您可能希望将实现切换到 C 或 C++ 之类的东西。

编写一个 Python 函数来查找图中的哈密顿路径

Writing a Python function that finds a Hamiltonian path in a graph

python

recursion

hamiltonian-cycle