路径问题的算法或方法，对于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

有帮助吗？

我在2d平面上有n个点，n <= 12，并且我需要包括所有点在内的最短路径的距离，从任何一个点开始，但我没有尝试过闭合电路。 。

Answer 1

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

Answer 2

[仅当n <= 12时，我建议the Branch and Bound algorithm，它是蛮力算法的改进版本。

Answer 3

我只会提供

提示