1/0具有加权边的背包变化 [英] 1/0 Knapsack Variation with Weighted Edges

问题描述

我目前正在调查一个路由问题（找到一个地方的子集[每个都有一定的分数]，我想在不超过最大旅行时间的情况下访问），并提出了1/0背包问题的变化似乎解决了我原来的问题。

根据维基百科的说法，1/0背包被描述为：

一组项目，每个项目都有一个质量和一个值，决定了要包括在一个集合中的每个项目的数量，以便总重量小于或等于给定限制，并且总值尽可能大。因此，对于每个项目，都有一个固定的权重（质量），可以在尝试解决问题时轻松使用，例如使用动态规划。

但是，如果特定商品的重量取决于包包的以前内容，该怎么办？换句话说（以更一般的方式）：让我们考虑下面的完整图：

值（在图中省略）。我仍然希望有一个最佳的背包，因此是具有最高分数的节点的子集，但是这次重量（或将特定节点添加到当前背包的成本）未分配给节点本身，而是分配给边缘导致它。

这意味着添加节点的成本取决于背包的先前内容（例如，通过使用任何已包含节点的成本最低的边）。例如，如果我现在的背包由{A，C}组成，则添加B的成本为2（以A-> B或C-> B）。如果我现在的背包由{D，E}组成，那么加入B的代价是3。

不幸的是，我无法真正想出一个好的算法来解决这个问题。
传统的背包DP方法在这里并不真正起作用，因为您可以轻松构建不返回最优解的案例。例如，如果你开始用错误的节点构建你的背包，那么添加一个非常好的节点（应该包含在最佳解决方案中但是很晚才会尝试）的成本可能会超出容量。

我对这个问题采取了一种完全错误的方法吗？你认为有更好的算法来解决这个问题吗？

解决方案

首先，这个问题是NP难题。这是从加权完整图中的最短哈密尔顿路径减少到这个。给定一个图，我们可以将所有节点的值分配给1，然后对答案进行二分搜索。如果存在这个问题的多项式解决方案，它可以确定是否存在包含所有顶点并且不长于给定值的路径。因此，我们能够在多项式时间内求解最短哈密尔顿路径问题。实际上，这意味着没有人知道您的问题有效的正确多项式解决方案。

现在有两种方法可以去：

1. 如果顶点的数量非常小（大约20），则可以使用动态编程来获得精确解。状态是（mask，last_vertex）。该值是我们需要访问掩码中的所有顶点并停在 last_vertex 中的最短时间。此解决方案的时间复杂度为 O（2 ^ n * n ^ 2）。




2. 顶点的数量要大得多，你可以找到一个近似的解决方案。有很多方法可以实现它：启发式算法，不同的贪婪算法，使用本地优化的随机抽样等等。

I'm currently investigating a routing problem (finding a subset of places [each with a certain score] I want to visit while not exceeding a maximum travel time) and came up with a variation of the 1/0 knapsack problem that seems to solve my original problem.

According to Wikipedia the 1/0 knapsack is described as:

Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

So for each item there is a fixed weight (mass) that can easily be used when trying to solve the problem, for instance using Dynamic Programming.

But what if the weight of a specific item is dependent on the previous content of the bag? In other words (and in a more general way): Let's consider the following complete graph:

Each node (A,B,C,D,E) represents an item I might want to put into my knapsack. Let's assume each node also has a certain value assigned to it (left out in the graph). I still want to have an optimal knapsack, thus a subset of the nodes with the maximum scores, but this time the weight (or costs of adding a specific node to my current knapsack) is not assigned to the node itself but rather to the edge leading to it.

This means that the costs of adding a node depend on the previous content of the knapsack (for example by using the edge with the lowest cost from any of the already included nodes). For instance, if my current knapsack consisted of {A,C} the costs of adding B were 2 (taking either A->B or C->B). If my current knapsack consisted of {D,E} the costs of adding B were 3 instead.

Unfortunately I can't really come up with a good algorithm to solve this problem. The classical knapsack DP approach doesn't really work here because you can easily construct cases where it does not return the optimal solution. For example if you start building your knapsack with the "wrong" nodes the costs to add a very good node (which should be included in an optimal solution but is tried very late) might exceed the capacity.

Am I taking a completely wrong approach to the problem? Do you think there is a better algorithm to tackle this problem?

解决方案

First of all, this problem is NP-hard. Here is a reduction from the shortest hamiltonian path in a weighted complete graph to this one. Given a graph, we can assign values of all nodes to 1 and then run binary search over the answer. If there was a polynomial solution for this problem, it could tell if there is a path that contains all vertices and is not longer than a given value. Thus, we would be able to solve the shortest hamiltonian path problem in polynomial time. In practice it means that no one knows an efficient correct polynomial solution to your problem.

Now there are two ways to go:

1. If the number of vertices is rather small(around 20), you can use dynamic programming to get an exact solution. The state is (mask, last_vertex). The value is the shortest possible time we need to visit all vertices in the mask and stop in the last_vertex. The time complexity of this solution is O(2^n * n^2).

2. If the number of vertices is much bigger, you can find an approximate solution. There are a lot ways to do it: heuristics, different greedy algorithms, random sampling with local optimizations and so on.

这篇关于1/0具有加权边的背包变化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！