np - 证明最长路径是具有负边权重的 NP-Hard

Question

我知道之前有人问过类似的问题，并且网上有大量的资源，但我有一个稍微不同的问题。我了解从 HAM 路径到最长路径的减少。它依赖于两者都需要使用 n-1 条边。但是，如果在最长路径中给出的图具有负边权重怎么办。那么最长的路径可能有 n-2 条边，但 HAM 仍然有 n-1 条边。

这个问题有不同的减少方式吗？我错过了什么吗？

标签： nplongest-path

Answer 1

这是一个类比。我想说服你超人拥有不可思议的超人力量。要做到这一点，我告诉你，他比超速子弹还快。“比超速子弹还快？”你说。“真是快啊！没有人能做到——这真的很难！”</p>

现在我告诉你更多——他不仅跑得比子弹还快；他可以一次跳越高楼。“哇！”你可能会说，“那也太难了！但话又说回来，我已经知道超人可以做非常困难的事情，因为你告诉我他跑得比子弹还快。” 从这个意义上说，通过说超人可以做一件困难的事情，我已经让你相信他很强大。告诉你他也可以做​​其他困难的事情并不能改变这一点。

现在让我们谈谈最长的路径。最长路径问题是 NP-hard 的原因是，给定任何图，您可以为该图中的每条边分配 1 的长度，然后检查该新图是否具有长度为 n - 1 的简单路径。很难做，因为，正如我们所知，检查一个图是否有哈密顿路径真的很难。（这是“超人跑得比子弹还快”的说法。）

现在想象我们说“嘿，我不仅可以用正权重解决这个问题，而且如果允许权重为负数，我也可以解决这个问题！” 从你的角度来看，我并没有让寻找最长路径的问题变得更容易。我们仍然可以使用与以前相同的归约来找到哈密顿路径。我们也可以做其他事情。（这是“一跳就可以跳过高楼”的意思。）

一般来说，如果你从一个 NP-hard 问题开始，然后对其进行概括，那么你通常会遇到一个 NP-hard 问题，因为该问题仍然具有以前的所有难点，加上一堆需要处理的新案例也是。