最小化加权和

Question

我最近遇到过这个问题.假设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).

我试图通过贪婪的方法解决它,从具有最大相关权重的点开始并移动到第二个最大权重点,依此类推.但算法不起作用.有人可以指点一下解决这个问题必须采取的方法吗？

Answer 1

有一个非常重要的事实导致了多项式时间算法：

由于这些点位于某个轴上，因此它们会生成一个路径图，这意味着对于每 3 个顶点v1,v2,v3，如果v2位于v1和 之间v3，则 和 之间的距离等于v1和之间v3的距离加上和 之间的距离。因此，如果我们从 开始，则 obj. 先到达然后返回的路径的函数值将始终小于先到达然后返回的路径的值，因为：v1v2v2v3v1v2v3v3v2

value of the first path = w[2]*D(v1,v2)+W[3]*(D(v1,v2)+D(v2,v3))

value of the second path = 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^n可能的路径，而不是n!可能的路径（如旅行商问题）。

求解路径图上的 TSP/最小权重哈密顿路径可以使用动态规划在多项式时间内完成，您应该应用完全相同的方法，但修改计算目标函数的方式。

由于您不知道起始顶点，因此您必须运行该算法n一次，每次都从不同的顶点开始，这意味着运行时间将乘以n。