我正在尝试构建一个导航应用程序。我试图想出一种算法来找到包含特定节点并总计达到特定权重的循环路径。 该算法的输入将是一个节点和一个权重。
示例:algo(a,30) - 该算法将返回一条路径，该路径可以从节点 A 开始并在节点 A 结束，并且总和为 30。
额外信息:对于所有 w:weights w>0，图形是有方向的(就像街道一样)。
提前致谢 加仑
最佳答案
这个问题比 Hamiltonian Cycle Problem 更强(更难) .因为如果我们已经有了这个问题的解决方案 algo(a,b)，对于任何哈密顿循环问题 P 我们都可以设计一个新图P 中的边权重 = 1，不在 P 中的边权重为 0，然后使用 algo(1,n) 找到哈密顿循环，在其中 n 是图中的节点数。所以我们这里有一个 NP 完全问题。
对于n 较小的应用程序，带有一定“修剪”的暴力搜索应该足够快。
关于java - 找到具有特定权重的特定节点的循环路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11935855/