我有一个无向图。现在，假设图表是完整的。每个节点都有一个与之关联的特定值。所有边都具有正权重。 我想找到任意 2 个给定节点之间的路径，使得与路径节点关联的值的总和最大，同时路径长度在给定阈值内。 解决方案应该是“全局的”，这意味着获得的路径应该是所有可能路径中的最优路径。我尝试了一种线性规划方法，但无法正确表述。 任何建议或不同的解决方法都会有很大帮助。
谢谢!
最佳答案
如果您在一般图中寻找算法，您的问题是 NP-Complete，假设路径长度阈值为 n-1，并且每个顶点的值为 1，如果您找到适合您的解决方案问题，你可以说给定的图是否有哈密顿路径。事实上，如果您的最大化顶点大小路径的值为 n，那么您就有了哈密顿路径。我认为您可以使用类似 Held-Karp 松弛的方法来找到好的解决方案。
关于algorithm - 同时考虑节点和边的图寻路算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9767525/