图表中的最佳路径以最大化值

Question

我正在尝试为这个问题提出一个合理的算法:

假设我们有很多地方.我们知道每对位置之间的距离.每个位置也有一个点.目标是在从起始位置行进到目的地位置时最大化点的总和而不超过给定的距离量.

这是一个简单的例子:起始位置:C,目的地:B,给定距离量:45

解决方案:CAB路线有9分

我只是好奇是否存在某种针对此类问题的动态算法.对于那个问题,什么是最好的,或者最简单的方法？

任何帮助是极大的赞赏.

编辑:您不能多次访问同一位置.

Answer 1

编辑:在新添加的限制下,每个节点只能被访问一次,问题绝对是NP-hard通过缩减到Hamilton路径:对于一般的无向,未加权图,将所有边权重设置为零,每个顶点权重为1然后,如果原始图中存在Hamilton路径,则最大可达分数为n.

因此,研究整数线性编程求解器可能是一个好主意,例如系列并非专门构造为难.

下面的解决方案假设可以多次访问顶点,并利用节点权重受常量限制的事实.

令p(x)为顶点x的点值,并且如果x和y不相邻,则w(x,y)为边缘{x,y}或w(x,y)=∞的距离权重.

如果我们被允许多次访问一个顶点并且如果我们可以假设p(x)<= C对于某个常数C,我们可能会得到以下重复:让f(x,y,P)成为最小距离我们需要在收集P点时从x到y.我们有

对于所有P <0,f(x,y,P)=∞

对于所有x,f(x,x,p(x))= 0

f(x,y,P)= MIN(z,w(x,z)+ f(z,y,P - p(x)))

我们可以使用动态编程来计算f.现在,我们只需要找到最大的P,使得

f(开始,结束,P)<=距离上限

这个P是解决方案.

具有简单实现的该算法的复杂性是O(n ^ 4*C).如果图是稀疏的,我们可以通过使用MIN聚合的邻接列表来获得O(n ^ 2*m*C).