最小化加权和 [英] Minimizing weighted sum
问题描述
我最近遇到了这个问题.假设在 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^n 条可能的路径，而不是 n! 条可能的路径(如旅行商问题).
解决路径图上的 TSP/最小权重哈密顿路径可以使用动态规划在多项式时间内完成，您应该应用完全相同的方法，但修改计算目标函数的方式.
由于你不知道起始顶点，你必须运行这个算法n次，每次从不同的顶点开始，这意味着运行时间将乘以n.
I came across this problem quite recently. Suppose there are n points on x-axis, x[0],x[1] .. x[n-1]. Let the weight associated with each of these points be w[0],w[1] .. w[n-1]. Starting from any point between 0 to n-1, the objective is to cover all the points such that the sum of w[i]*d[i] is minimized where d[i] is the distance covered to reach the ith point from the starting point.
Example:
Suppose the points are: 1 5 10 20 40
Suppose the weights are: 1 2 10 50 13
If I choose to start at point 10 and choose to move to point 20 then to 5 then to 40 and then finally to 1, then the weighted sum will become 10*0+50*(10)+2*(10+15)+13*(10+15+35)+1*(10+15+35+39).
I have tried to solve it using greedy approach by starting off from the point which has maximum associated weight and move to second maximum weight point and so on. But the algorithm does not work. Can someone give me pointers about the approach which must be taken to solve this problem?
There's a very important fact that leads to a polynomial time algorithm:
Since the points are located on some axis, they generate a path graph, which means that for every 3 vertices v1,v2,v3, if v2 is between v1 and v3, then the distance between v1 and v3 equals the distance between v1 and v2 plus the distance between v2 and v3. therefor if for example we start at v1, the obj. function value of a path that goes first to v2 and then to v3 will always be less than the value of the path that first goes to v3 and then back to v2 because:
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))
If we subtract the first path value from the second, we are left with w[2]*2*D(v3,v2) which is equal to or greater than 0 unless you consider negative weights.
All this means that if we are located at a certain point, there are always only 2 options we should consider: going to closest unvisited point on the left or the closest unvisited point on the right.
This is very significant as it leaves us with 2^n possible paths rather than n! possible paths (like in the Travelling Salesman Problem).
Solving the TSP/minimum weight hamiltonian path on path graphs can be done in polynomial time using dynamic programming, you should apply the exact same method but modify the way you calculated the objective function.
Since you don't know the starting vertex, you'll have to run this algorithm n time, each time starting from a different vertex, which means the running time will be multiplied by n.
这篇关于最小化加权和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
