最小化加权求和 [英] Minimizing weighted sum

问题描述

我过这个问题相当最近来了。 假设有n个点上的x轴，X [0]中，x [1]。X [N-1]。 让与这些点有关的重量为w [0]，W [1] ..瓦特[N-1]。 从到n-1之间0的任何点开始，目标是覆盖所有的点，使得w的总和[I] * D [i]的最小化，其中d [i]为覆盖从到达第i个点的距离起点。

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.

例：
假设点：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）。

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:

由于点都位于某个坐标轴，它们产生的路径图，这意味着，每3个顶点 V1，V2，V3 ，如果 V2 之间 V1 和 V3 ，然后之间的距离 V1 和 V3 等于>之间 V1 V2 之间加 V2 和距离 V3 。为此，例如，我们开始 V1 的OBJ。路径的函数值，首先进入 V2 再到 V3 将始终小于该路径的价值首先进入 V3 ，然后重新设置为 V2 ，因为：

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:

第一路径的值=瓦特[2] * D（V1，V2）+ W [3] *（D（V1，V2）+ D（V2，V3））

第二路径的值=瓦特[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））

如果我们从第二减去第一路径值，我们剩下的瓦特[2] * 2 * D（第三版，v2）的其等于或大于比0，除非你认为负权重。

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.

这一切都意味着，如果我们设在某一点上，总有一些我们应该考虑的只有2个选择：去左边或右边的最近访问过的点最近访问过的点

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.

这是因为它给我们留下了 2的n次方可能的路径，而不是 N！可能的路径（非常显著像旅行商问题）。

This is very significant as it leaves us with 2^n possible paths rather than n! possible paths (like in the Travelling Salesman Problem).

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

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.

既然你不知道的起始顶点，你必须运行此算法 N 的时间，从不同的顶点，这意味着运行时间开始，每次将成倍 N 。

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屋！