路径问题的算法或方法，n <= 12 时有 n 个点的最短路径

Question

我在 2d 平面上有 n 个点，其中 n <= 12，并且我需要可用的最短路径的距离，包括所有点，从其中任何一个点开始，但不形成闭合电路，

我一直在尝试弗洛伊德元帅、旅行推销员问题等算法均未成功。

这个问题对我的老师来说很容易，所以我不认为它需要阿罗拉近似，但我不知道解决这个问题的最佳方法是什么，但也许一些动态算法和类似的

for i = 0 to n
    for j = 0 to n
    if path_distance(i,j) < mininum
        set minimum

帮助？

Answer 1

如果您知道只有 12 个点并且想要找到访问每个节点一次的最短路径，那么您始终可以通过尝试节点的所有可能排列并计算沿该路径的路径长度来暴力破解解决方案排列。这根本无法很好地扩展，但如果节点数量有固定的上限，那么它应该是合理的。

Answer 2

当且仅当n <= 12时，我推荐分支定界算法，这是暴力算法的改进版本。

Answer 3

我只会提供一个提示，因为这是家庭作业：

在分解此类问题时，递归非常有用。

您可以编写一个函数，该函数获取迄今为止的路线列表、迄今为止的最佳/最小距离以及未访问节点的列表。对于每个未访问的节点，它会尝试将其添加到迄今为止的路线中，如果该路线仍然短于迄今为止的最佳/最小距离，那么它将使用新路线和未访问节点列表来调用自身。