dsal 优化最长路径为 NP 完全

优化最长路径为 NP 完全

原文:https://www . geesforgeks . org/optimized-最长路径-is-np-complete/

优化最长路径问题 : 优化最长路径问题指出，给定一组顶点 V 和边 E 的图 G ，任务是证明在一组节点 V _s 和 V _e 之间存在长度至少为 K的路径。

问题陈述 : 给定一个图 G(V，E，K) 和一组节点 V _s 和 V _e 以及节点序列，长度 ≥ K 。

解释 : 问题的一个实例是指定给问题的输入。优化最长路径问题的一个例子是 G(V，E，V _s ，V _e ，K) 。由于 NP-complete 问题是同时存在于 NP 和 NP-Hard 中的问题，因此证明问题是 NP-complete 的陈述由两部分组成:

The problem itself lies in NP class.

All other problems in NP class can be reduced to that by polynomial time. (b can be reduced to c by polynomial time and expressed as b ≤ p ^c )

如果仅满足第二个条件，则问题称为 NP-Hard 。

但是不可能把每一个 NP 问题都化为另一个 NP 问题来一直展示它的 NP 完全性。这就是为什么如果我们想证明一个问题是 NP-Complete，我们只需要证明这个问题是在 NP 中，并且任何 NP-Complete 问题都可以简化为这个问题，那么我们就完成了，即如果 B 是 NP-Complete 并且 B ≤ P ^C 对于 NP 中的 C，那么 C 就是 NP-Complete。因此，我们可以使用以下两个命题来验证优化最长路径问题是 NP 完全的:

优化-最长路径问题在 NP 中 : 如果有任何问题在 NP 中，给定一个‘证书’，这是问题的解决方案和问题的实例，那么可以在多项式时间内验证(检查给定的解决方案是否正确)该证书。这可以通过路径 P 来完成，路径由一组顶点< V ₁ 、V ₂ 、V ₃ 、…。V _n >。验证路径是否完全连接 V ₁ ，V _n ，路径长度最多为K。
优化-最长路径问题是 NP-Hard: 为了证明最长路径是 NP-Hard，推导出从一个已知的 NP-Hard 到问题的约简。进行一个约简，其中无向哈密顿路径问题可以被约简为最长路径问题。无向哈密顿路径使用输入 a 图 G(V ₁ 、V _n ) ，其中图 G 有节点 V ₁ 和 V _n 。无向哈密尔顿路径是沿着图的无向路径，从一个顶点开始，到另一个顶点结束，遍历所有节点。

现在，让 K 成为 G 中的节点数。无向哈密顿路径的每个实例都可以通过以下方式转换为最长路径: 对于输入 G(V ₁ ，V _n ，输出 G(V ₁ ，V _n ，k)。通过简单地计算 g 中的顶点数，这种约简需要多项式时间。约简可以通过以下两个命题来证明:
1. 假设原图 G(V，E) 有节点 V ₁ 和 V _n 有一条无向哈密顿路径，该路径遍历所有顶点，因此 G(V，E，K) 为真，因为 G 中的任意两个节点将由一条长度与其节点相等的路径连接，即 K 因此最长路径问题成立。
2. Let us assume the graph G'(V, E, V_s, V_e, K) has a Lpath of length K from V_s to V_e, which implies G’ contains a simple path of length K from V_s to V_e. But, G contains K vertices, hence traverses all vertices starting at V_s and ending at V_e forming a hamiltonian path, G'(V_s, V_e).
  
  让 V₁B 和 V_nD 现在， G 有一个 K = 4 的无向哈密顿路径≡ BCAD。因此，G 包含 B 和 d 之间长度= 4 的优化路径。