边权预算下的最大简单路径

Question

这是一个自行制定的问题的一部分，因此我无法通过“Google”来解决它，我的尝试到目前为止也都徒劳无功。

给定一个图G(V,E)，每个V节点具有利润wi，每个E边缘具有成本ci。我们现在有一个预算C，需要找到一条单路径，使得路径的成本之和小于C，同时wi之和最大。这里的路径具有正常的定义，即路径不包含重复顶点（简单路径）。

显然，哈密顿路径是这个问题的特例（将成本设置为|N-1|，每个边的成本=1），因此这是一个NP难问题，因此我正在寻找近似解和启发式方法。

数学上：

给定图G(V,E)

对于每个边缘e，ci > = 0

对于每个顶点v，wi >=0

找到一条简单路径P，使得

所有边缘e在P中的和ci <= C

对于所有v在P中，使得wi之和最大。

- Manyu

---

为什么哈密顿路径是一个特例？你的问题没有说明路径只能最多访问每个顶点一次。 - Venge

我认为你想要指定 ci >= 0，并且一个顶点的利润在你访问它后变为零，或者你只能访问一个顶点一次。 - VSOverFlow

@Patrick：对于所有边的成本=0，所有顶点的成本=1——如果这个问题有一个长度为|V|的解，则存在哈密顿路径。 - amit

Answer 1

这被称为选择性旅行推销员问题，或带利润的旅行推销员问题。Google Scholar应该能够给你一些参考文献。通常会使用遗传编程或禁忌搜索等元启发式算法。如果您想要最优解，线性规划技术可能会起作用（不幸的是，您没有说明您正在处理的实例的大小）。如果路径长度较小（比如15个顶点），也可以使用color-coding。

- Falk Hüffner

---

我所关注的大致规模约为50个节点，几乎是完全图，但成本函数通常意味着路径中不会超过15个节点。 - Manyu

Answer 2

有一个简单的启发式方法，它是随机爬山算法和贪心算法的变体。

定义一个价值函数，该函数随着重量的增加而增加，随着成本的减少而减少。例如：

value(u,v) = w(v) / [c(u,v) + epsilon]
(+ epsilon for the case of c(u,v) = 0)

现在的想法是：
从一个顶点u出发，以概率前往顶点v：

P(v|u) = value(u,v) / sum(u,x) [ for all feasible moves (u,x) ]

重复执行，直到无法继续。

这个解决方案将快速给出一个解决方案，但可能不是最优的。然而 - 它是随机的 - 您可以在有时间的情况下一遍又一遍地重新运行它。
这将为您提供一个针对此问题的任何时候算法，这意味着 - 您拥有的时间越多，您的解决方案就越好。

一些优化:

• 您可以尝试学习宏，以加速每次搜索，这将导致更多的搜索，每个时间段内，也可能会得到更好的解决方案。
• 通常，第一次搜索不是随机的，而是纯粹的贪心，遵循max{value(u,v)}

- amit