algorithm - 带加重边缘的 1/0 背包变体

Question

我目前正在研究一个路线问题(找到我想要访问的地方的子集[每个地方都有一定的分数]，同时不超过最大旅行时间)，并提出了 1/0 背包问题的变体:似乎解决了我原来的问题。

根据维基百科，1/0 背包被描述为:

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.

因此，对于每个项目都有一个固定的重量(质量)，在尝试解决问题时可以轻松使用该重量(例如使用动态规划)。

但是，如果特定元素的重量取决于袋子之前的内容怎么办？换句话说(以更一般的方式):让我们考虑以下完整的图表:

每个节点(A、B、C、D、E)代表我可能想要放入背包中的元素。我们假设每个节点还分配有特定的值(在图中省略)。我仍然想要一个最佳的背包，因此具有最大分数的节点的子集，但是这次权重(或将特定节点添加到当前背包的成本)没有分配给节点本身，而是分配给边缘导致它。

这意味着添加节点的成本取决于背包先前的内容(例如，使用任何已包含节点中成本最低的边)。例如，如果我当前的背包由 {A,C} 组成，则添加 B 的成本为 2(采用 A->B 或 C->B)。如果我当前的背包由 {D,E} 组成，则添加 B 的成本将为 3。

不幸的是我无法真正想出一个好的算法来解决这个问题。 经典的背包 DP 方法在这里并不真正起作用，因为您可以轻松构建它不返回最佳解决方案的情况。例如，如果您开始使用“错误”节点构建背包，则添加一个非常好的节点(应包含在最佳解决方案中但很晚才尝试)的成本可能会超出容量。

我是否采取了完全错误的方法来解决问题？您认为有更好的算法来解决这个问题吗？

Answer 1

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

现在有两条路可走:

1. 如果顶点数量较少(20个左右)，可以使用动态规划来得到精确解。状态是(mask，last_vertex)。该值是我们访问 mask 中的所有顶点并在 last_vertex 处停止所需的最短时间。该解决方案的时间复杂度为O(2^n * n^2)。

2. 如果顶点数量较多，则可以找到近似解。有很多方法可以做到这一点:启发式、不同的贪婪算法、带有局部优化的随机采样等等。