0

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

我一直在尝试弗洛伊德元帅、旅行推销员问题和其他算法，但没有成功。

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

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

有什么帮助吗？

4

3 回答 3

1

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

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

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

于 2011-03-09T10:05:10.887 回答
1

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

于 2011-03-09T08:28:03.110 回答
1

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

于 2011-03-03T01:34:18.597 回答