我正在寻找一个近似算法来解决以下问题 - 我有一个无权、无向的带环图，并想找到从给定节点开始的最长路径。我更注重速度而非性能（因此O(n^5)的算法可能会过度杀伤）。
这不是作业（我发誓！）或与工作相关，但我将感激您提供的任何提示。
这不是作业（我发誓！）或与工作相关，但我将感激您提供的任何提示。
1个回答
7
- P Shved
4
哇，我不知道这个。我以为广义问题有一个常数因子的近似算法。
那如果进一步限制问题，使得最大邻居数量是常数呢？ - r0u1i
1@r0u1i，糟糕的是，我链接的第一篇文章也证明了这样的限制没有帮助。 - P Shved
2请注意，NP完备性结果未必能够告诉你有关你正在处理的图实例的任何信息。例如，SAT问题是NP完备的，但在工业应用中通常可以解决大规模的SAT实例。另外，你的图是否是平面图？你能否限制只能访问每个节点一次的条件？构建图的过程是否能为最长路径的特性提供启示？ - Antti Huima
它是平面的，我能做些什么？ - r0u1i
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接