1

我试图编写一个函数，它将一个正整数 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]}

起点是哈密顿路径的起点。（我试图编写这个没有起点的函数，这样函数本身就会尝试每个点作为起点，但它变得复杂了。现在，我只是自己遍历所有顶点。）

我知道对于数字 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 很陌生，所以如果这个问题是微不足道的或者我的代码很糟糕，我深表歉意。

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

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

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

现在，问题是函数None在返回列表后返回。因此，这是我为数字 15 运行此函数时的输出，即图表是我之前提到的字典：

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

我怎样才能解决这个问题，所以它不会返回None？顺便说一句，我还是要自己尝试每一个数字作为起点。这就是我所做的：

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

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

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

编辑：我意识到包含整个函数而不是仅包含哈密顿路径部分更有帮助，因为某些变量是未定义的。

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之后，我尝试使用循环将每个数字作为路径的开始。

4

1 回答 1

0

我认为你得到的原因None是因为在hampath_finder函数中你只返回一个值if new_path:。如果没有新路径并且函数返回，那么 Python 将返回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

这将有助于提高速度。

然而，粗略地看一下哈密顿路径问题，它看起来像是一个 NP 完全问题。所以它会很慢。有一些研究论文具有更快的实现，超出了 StackOverflow 的范围。此外，如果需要速度，那么您可能希望将实现切换为 C 或 C++ 之类的东西。

于 2020-07-03T17:24:51.907 回答