最小化加权和

Question

最小化加权和

9

我最近遇到了这个问题。假设在x轴上有n个点，它们分别是x[0]、x[1]、...、x[n-1]。让每个点对应的权值为w[0]、w[1]、...、w[n-1]。从0到n-1中的任意一点开始，目标是覆盖所有的点，使得到达第i个点的距离d[i]与其相应的权值w[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)。

我尝试使用贪心算法来解决这个问题，从具有最大相关权重的点开始，移动到第二大的权重点，以此类推。但是算法不起作用。请问有人可以给我指点一下该如何解决这个问题吗？

- n00bc0d3r

这是TSP的一个简化版本。实际上，我非常确定我们可以将|E|<=2|V|的TSP问题简化为这个问题... - amit

问题的规模是什么？暴力解法显然可行，但效率非常低... - amit

提示：在解决x轴问题时，通常需要从最左侧或最右侧点开始。请更加关注x轴条件！基于此可以使用贪心算法 :) - Pham Trung

@PhamTrung 那么权重为0、1000、0的点0、1、2怎么处理？ - David Eisenstat

1

@amit 覆盖的点集始终是一个区间，因此 DP 表的大小应该是可管理的。 - David Eisenstat

3个回答

0

也许你应该详细说明一下你所谓的算法“不能工作”的含义。你描述的贪心方法的基本思路对我来说似乎可行。你是说贪心方法不一定能找到最优解吗？正如评论中指出的那样，这可能是一个NP完全问题 - 尽管要确定，就必须进一步分析：一些动态规划，以及可能用于距离计算的前缀和，也可以导致多项式时间解决方案。

我用Java快速实现了贪心解决方案（希望我理解得都正确...）。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MinWeightSum
{
    public static void main(String[] args)
    {
        double x[] = { 1, 5, 10, 20, 40 };
        double w[] = { 1, 2, 10, 50, 13 };

        List<Integer> givenIndices = Arrays.asList(2, 3, 1, 4, 0);
        Path path = createPath(x, w, givenIndices);
        System.out.println("Initial result "+path.sum);

        List<Integer> sortedWeightIndices =
            computeSortedWeightIndices(w);
        Path greedyPath = createPath(x, w, sortedWeightIndices);
        System.out.println("Greedy result  "+greedyPath.sum);

        System.out.println("For "+sortedWeightIndices+" sum "+greedyPath.sum);
   }

    private static Path createPath(
        double x[], double w[], List<Integer> indices)
    {
        Path path = new Path(x, w);
        for (Integer i : indices)
        {
            path.append(i);
        }
        return path;
    }


    private static List<Integer> computeSortedWeightIndices(final double w[])
    {
        List<Integer> indices = new ArrayList<Integer>();
        for (int i=0; i<w.length; i++)
        {
            indices.add(i);
        }
        Collections.sort(indices, new Comparator<Integer>()
        {
            @Override
            public int compare(Integer i0, Integer i1)
            {
                return Double.compare(w[i1], w[i0]);
            }
        });
        return indices;
    }

    static class Path
    {
        double x[];
        double w[];

        int prevIndex = -1;
        double distance;
        double sum;

        Path(double x[], double w[])
        {
            this.x = x;
            this.w = w;
        }

        void append(int index)
        {
            if (prevIndex != -1)
            {
                distance += Math.abs(x[prevIndex]-x[index]);
            }
            sum += w[index] * distance;
            prevIndex = index;
        }
    }
}

您在示例中描述的索引序列产生了该解决方案。

For [2, 3, 1, 4, 0] sum 1429.0

你所描述的贪心算法会得到

For [3, 4, 2, 1, 0] sum 929.0

最佳解决方案是

For [3, 2, 4, 1, 0] sum 849.0

我通过检查所有索引的排列方式找到了这个（当然，对于较大的n来说这是不可行的）

- Marco13

1

动态规划似乎行不通，因为系统有内存。例如，与点5相关的成本取决于您是否在给定点x或另一点y开始步行。 - DanielTheRocketMan

@DanielTheRocketMan 你可能是对的，这只是关于解决这类最小化问题可能方法的“头脑风暴”。我也考虑过将其表述为某种最短路径问题，但尚未进行详细分析。如果它是NP完全问题，那么很“不可能”;-)找到一个多项式时间解决方案。 - Marco13

@DanielTheRocketMan 我提供了一个DP答案，因为我认为尽管未来点的绝对成本取决于到目前为止已经行驶的距离，但你可以分离出距离相关的组件并加以考虑 - 无论你采取什么方式访问它们，额外行驶一个单位的距离总是会花费你所有尚未覆盖的点的总重量，因此不会改变不同未来行程的相对价值。 - mcdowella

0

假设您已经解决了一部分问题，并且已经行驶了距离D。如果您再走x距离并看到一个重量为w的点，则成本为（D + x）w。如果您再走y距离并看到一个重量为v的点，则成本为（D + x + y）v。如果将所有这些加起来，就会有一个取决于在距离D后所采取的路径的组件：xw + xv + yv + ...，还有一个取决于距离D和需要访问的点的权重之和的组件：D（v + w + ...）。但是，取决于距离D的组件除了需要访问的点的权重之和以外不依赖于任何其他东西，因此它是固定的，也就是说，无论在距离D后采取什么路径，它都是相同的。

始终有意义去访问我们经过的点，因此最佳路径将从单个点开始（可能位于要访问的点集的边缘，也可能位于中心），然后将其扩展为已访问点的间隔，然后将其扩展为访问所有点。为了预先计算访问间隔外所有点的相对成本，我们只需要知道当前位置和间隔的大小，而不需要知道到目前为止行驶的距离。

因此，一种昂贵但多项式的动态规划方法的状态包括当前位置（必须是其中一个点），当前位置左侧第一个未访问点的位置（如果有的话），以及当前位置右侧第一个未访问点的位置（如果有的话）。我们最多应该考虑访问下一个点的两个位置 - 当前点右侧的点和当前点左侧的点。我们可以通过查看剩余点数更少的状态的预计算成本来计算这两种选择的成本，并将最佳结果存储为从此点开始的最佳可能成本。我们可以在到达当前点时假设D=0来计算这些成本。当我们查找存储的成本时，它们也是在这个假设下存储的（但是在它们的当前点处D=0，而不是我们的当前点），但是我们知道在那个阶段剩下的点的权重之和，因此我们可以添加存储成本和权重之和乘以我们当前点与我们正在查找成本的点之间的距离来补偿这一点。

这将会产生O(n^3)的成本，因为您正在构建一个具有O(n^3)个单元格的表格，每个单元格都是相对简单的过程的乘积。然而，因为没有访问到的单元格永远没有意义，当前点必须在区间两端的其中一个点旁边，因此我们只需要考虑O(n^2)种可能性，这将把成本降低到O(n^2)。例如，像（0，1，-1，2，-2，3，-3，4，-4…）这样的锯齿路径可能是适当奇异权重的最佳解决方案，但即使是从-2到3这样的情况，-2也是两个点3和-3之间尚未采取的最近点。

我在http://www.mcdowella.demon.co.uk/Plumber.java中放了一个Java实现。测试工具针对长度为12及以下的多个随机生成的测试用例检查此DP版本与（慢）几乎穷举的版本。它可能仍然不完全没有漏洞，但希望它能填补细节。

- mcdowella

为什么不能用O(n^2)完成这个任务？“我们访问每个点时，经过的点总是有意义的。”因此，如果起点固定，我们只有两条路径（1.向左端移动并到达右端，2.向右端移动并到达左端）。 - cegprakash

我相信你说的有一个O(n^2)的解决方案，并且我已经在我的答案中添加了文本，但我不确定我们是否同意可能最佳答案的复杂程度。 - mcdowella

这个理论看起来是正确的。但我们应该证明它 :) 我认为可以通过反证法来证明这一点。但我不是一个好的证明写手。我将授予50个赏金给你/任何人，如果你能证明这一点:D - cegprakash

这不是证明，但我已经将实现和测试工具放在http://www.mcdowella.demon.co.uk/Plumber.java中。根据我的Java代码是否清晰，您可能会在此处找到足够的信息来进行证明。如果您觉得这有帮助，请告诉我这个问题来自哪里 - 目前看起来像是一个展示DP的练习，但我很想被证明是错误的。 - mcdowella

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ron Teller · Accepted Answer

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

由于点位于某些轴上，它们生成了一条路径图，这意味着对于每个三个顶点v1，v2，v3，如果v2在v1和v3之间，则v1和v3之间的距离等于v1和v2之间的距离加上v2和v3之间的距离。因此，例如，如果我们从v1开始，则首先到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。