最小化加权和
我是最近才遇到这个问题的。假设在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因为：
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。
以上是 最小化加权和 的全部内容， 来源链接： utcz.com/qa/405834.html
