algorithm - 边缘有预算的最大简单路径

Question

这是一个 self 制定的问题的一部分，因此我无法“谷歌”它，直到现在我自己的尝试都是徒劳的。

给你一个图表G(V,E) V 的每个节点 都有利润wi ，E 的每个Edge 的成本为ci。我们现在有一个预算 C，需要找到的是一条路径，使得成本总和小于 C，其中 wi 是最大值。路径在这里具有正常定义，即路径将不包含重复顶点(简单路径)。

很明显，哈密顿路径是这个的特例(设置成本= |N-1|，每条边的成本=1)，因此这是一个NP Hard问题，所以我正在寻找近似解决方案, 和启发式。

数学上的

给定图 G(V,E)

ci >=0 每条边 e

wi >=0 对于每个顶点 v

找到一个简单的路径P使得

ci 在 P <= C

中的所有边 e 上求和

最大化 Sum wi 对于 P

中的所有 v

Answer 1

这被称为选择性旅行商问题，或有利润的旅行商问题。谷歌学术应该可以给你一些引用。经常使用遗传编程或禁忌搜索等元启发式方法。如果你想以最佳方式解决问题，线性规划技术可能会起作用(不幸的是，你没有说明你正在处理的实例的大小)。如果路径的长度很小(比如说 15 个顶点)，也是 color-coding可能有用。