0

我正在尝试构建一个导航应用程序。我试图想出一种算法来找到包含某个节点并总和为某个权重的循环路径。该算法的输入将是一个节点和一个权重。

示例：algo(a,30) - 该算法将返回一条可以从节点 A 开始并在节点 A 结束的路径，其总和为 30。

额外信息：对于所有 w:weights w>0，图形是有方向的（就像街道一样）。

提前谢谢加尔

4

2 回答 2

1

这个问题比哈密顿循环问题更强（更难） 。因为如果我们已经有这个问题的解决方案algo(a,b)，对于任何哈密顿循环问题P ，我们可以设计一个新图，其中P中的边权重 = 1，边不为 0，然后使用algo(1,n)找到一个哈密顿循环，其中n是图中的节点。所以我们这里有一个NP完全问题。

对于小的应用程序，n具有某些“修剪”的蛮力搜索应该足够快。

于 2012-08-13T14:15:44.887 回答
1

一般问题是 NP-Hard ，并且可以从最长路径问题中约简，因此是NP-Hard，并且没有已知的多项式解决方案可以解决这个问题（并且一般假设是不存在这样的解决方案）。

最长路径问题是：给定一个G具有权重函数w和一对顶点 的图u-找到从到v的最长路径。uv

证明：
假设您的问题有一个多项式算法-可以使用二进制搜索构建最长路径问题的算法（以指数方式增加所需的权重，直到没有解决方案，然后-二进制搜索）。每个步骤都是多项式的，并且有O(log|PATH|)步骤。由于log|PATH|输入中是多项式（假设路径简单），因此该算法是多项式的。

它也与哈密顿路径问题和旅行商问题密切相关

于 2012-08-13T14:16:15.020 回答