算法或途径路径问题，最短路径与n点n = 12

我有一个2d平面上的n个点，其中n < = 12，我需要包括所有点在内的最短路径的距离，在他们中的任何一个，但没有闭路算法或途径路径问题，最短路径与n点n = 12

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

问题被认为是容易让我的老师，所以我不认为这将需要阿罗拉近似左右，但我不知道什么是最好的办法来解决这个问题，但也许一些动态的算法和像

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

东西

有帮助吗？

2011-03-03 Daniel

您是否被允许多次重访积分？或者你必须一次访问每个点，而且只需要访问一次？ – templatetypedef 2011-03-03 01:18:53

访问每个点一次，并且只是一次 – Daniel 2011-03-03 01:31:33

这是一个O（n！）问题，而不是您尝试的O（n^2）问题。十亿条可能的路径。先在一张纸上做。 – 2011-03-03 02:00:44

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

2011-03-03 01:34:18 templatetypedef

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

2011-03-09 08:28:03

我将只提供一个提示因为这是家庭作业：打破这类问题时

递归是非常有用的。

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

2011-03-09 10:05:10 GrahamS

回答