我最近遇到了这个问题。 假设x轴上有n个点，x[0],x[1] .. x[n-1]。 设与这些点中的每一个相关联的权重为 w[0]、w[1] .. w[n-1]。 从 0 到 n-1 之间的任意点开始，目标是覆盖所有点，使 w[i]*d[i] 的总和最小化，其中 d[i] 是到达第 i 个点所覆盖的距离起点。
例子:
假设点数是:1 5 10 20 40
假设权重为:1 2 10 50 13
如果我选择从点 10 开始并选择移动到点 20 然后移动到 5 然后移动到 40 最后移动到 1，那么加权和将变为 10*0+50*(10)+2*(10+15) +13*(10+15+35)+1*(10+15+35+39)。
我试图通过从具有最大关联权重的点开始并移动到第二个最大权重点等来使用贪婪方法来解决它。但是该算法不起作用。有人可以指点一下解决这个问题必须采取的方法吗？
最佳答案
有一个非常重要的事实导致多项式时间算法:
由于点位于某个轴上，因此它们生成路径图，这意味着对于每 3 个顶点 v1,v2,v3，如果 v2 介于 v1和v3，那么v1和v3之间的距离等于v1之间的距离和v2加上v2和v3之间的距离。因此，如果我们从 v1 开始，obj.先到 v2 然后到 v3 的路径的函数值将始终小于先到 v3 的路径的值然后回到 v2 因为:
第一条路径的值 = w[2]*D(v1,v2)+W[3]*(D(v1,v2)+D(v2,v3))
第二条路径的值 = w[3]*D(v1,v3)+W[2]*((v1,v3)+D(v3,v2)) = w[3]*D (v1,v2)+w[3]*D(v2,v3)+w[2]*(D(v1,v2)+2*D(v3,v2))
如果我们从第二个路径值中减去第一个路径值，我们剩下的 w[2]*2*D(v3,v2) 等于或大于 0，除非您认为负数权重。
所有这一切意味着，如果我们位于某个点，我们应该考虑的始终只有 2 个选项:前往左侧最近的未访问点或右侧最近的未访问点。
这非常重要，因为它给我们留下了 2^n 个可能的路径，而不是 n! 个可能的路径(就像在旅行商问题中一样)。
可以使用动态规划在多项式时间内求解路径图上的 TSP/最小权重哈密尔顿路径，您应该应用完全相同的方法，但修改您计算目标函数的方式。
由于您不知道起始顶点，因此您必须运行此算法 n 次，每次从不同的顶点开始，这意味着运行时间将乘以 n.
关于algorithm - 最小化加权和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21875795/