我正试图为这个问题想出一个合理的算法:
假设我们有很多地点。我们知道每对位置之间的距离。每个位置也有一个点。目标是在不超过给定距离的情况下从起始位置行进到目的地位置时最大化点的总和。
这是一个简单的例子:
起始位置:C，目的地:B，给定距离:45
解法:C-A-B路线，有9个点
我很好奇是否有针对此类问题的某种动态算法。什么是解决该问题的最佳或更简单的方法？
非常感谢任何帮助。
编辑:您不得多次访问同一地点。
最佳答案
编辑: 在新添加的每个节点只能访问一次的限制下，通过归约到汉密尔顿路径，问题绝对是 NP-hard 问题:对于一般无向、未加权的图，设置所有边权重为零，每个顶点权重为 1。如果原始图中存在汉密尔顿路径，则最大可达分数为 n。
所以研究一下 integer linear programming 可能是个好主意求解器，例如并非专门构造为困难的族。
下面的解决方案假设一个顶点可以被多次访问，并利用了节点权重受常数限制的事实。
设p(x)为顶点x的点值，w(x,y)为边的距离权重{x,y} 或 w(x,y) = ∞ 如果 x 和 y 不相邻。
如果我们被允许多次访问一个顶点，并且如果我们可以假设 p(x) <= C 对于某个常量 C，我们可能会逃脱以下循环:让 f(x,y,P) 是我们在收集 x 到 y 所需的最小距离>P 点。我们有
f(x,y,P) = ∞ for all P < 0
f(x,x,p(x)) = 0 for all x
f(x,y,P) = MIN(z, w(x, z) + f(z, y, P - p(x)))
我们可以使用动态规划计算f。现在我们只需要找到最大的 P 使得
f(start, end, P) <= distance upper bound
这个 P 就是解决方案。
此算法的简单实现复杂度为 O(n^4 * C)。如果图是稀疏的，我们可以通过对 MIN 聚合使用邻接表来得到 O(n^2 * m * C)。
关于algorithm - 图中最大化值的最佳路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23319097/