优化的最长路径是NP完全的

“升级最长路”问题是一项计算困难的任务，被排序为 NP 完全问题。在本期中，给定一个带有加权边的图，目标是找到从预定的起始枢纽到闭合枢纽的最长路径，同时扩大边缘负载量。由于可能的研究方法取得了显着的发展，没有任何已知的多项式时间计算可以在所有情况下有效地解决这个问题。考虑到所有因素，科学家们依靠推测计算和启发法来追踪最接近的理想排列。此问题的麻烦在运输、计划运营和预订预订等不同领域产生了一定的影响。

使用的方法

• 简化哈密顿路径问题

• 使用已知的 NP 完全问题

哈密顿路径问题的简化

解决“升级最长路”是 NP 完成问题的一种方法是显示与著名的 NP 完全问题（称为哈密顿路问题）相比的减少。哈密​​顿路问题确定给定的图是否包含精确访问每个顶点一次的路径。

算法

• 以哈密顿路问题为例，它是一个图 G。

• 制作另一个图表 G'，与 G 没有区别，具有相似的顶点和边。

• 将权重 1 分配给 G' 中的所有边。

• 将“增强型最长路径”问题的起始和结束枢纽设置为 G' 中的任意两个不稳定枢纽。

• 如果 G 具有哈密顿路，G' 中的“升级最长路”将是类似的哈密顿路，其边负载量等于边的数量，边的数量等于边的数量顶点数短一。

• 如果 G 没有哈密顿路，那么此时 G' 中的“流线型最长路”将是从起始枢纽到闭合枢纽的一条直接路径，其中边载荷的量等于边的数量，这并不完全是短顶点的数量。

• 这种下降表明解决“改进的最长路”与解决哈密顿路问题一样困难，使其成为 NP 完全问题。

示例

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

bool hasHamiltonianPath(const vector<vector<int>>& graph, int 
start, int finish) {
   int n = graph.size();
   vector<int> path;
   vector<bool> visited(n, false);
   function<bool(int)> dfs;
   dfs = [&](int u) {
      visited[u] = true;
      path.push_back(u);
      if (u == finish && path.size() == n)
         return true;
      for (int v = 0; v < n; ++v) {
         if (!visited[v] && graph[u][v]) {
            if (dfs(v))
               return true;
         }
      }
      visited[u] = false;
      path.pop_back();
      return false;
   };
   return dfs(start);
}

int main() {
   int n = 5;
   vector<vector<int>> graph(n, vector<int>(n, 0));
   graph[0][1] = graph[1][0] = 1;
   graph[1][2] = graph[2][1] = 1;
   graph[2][3] = graph[3][2] = 1;
   graph[3][4] = graph[4][3] = 1;
   vector<vector<int>> graph_prime = graph;
   int start = 0, finish = 3;
   if (hasHamiltonianPath(graph, start, finish))
      cout << "G has a Hamiltonian Path.\n";
   else
      cout << "G does not have a Hamiltonian Path.\n";
   return 0;
}

输出

G does not have a Hamiltonian Path.

使用已知的 NP 完全问题

另一种方法是通过从已知的 NP 完全问题（例如最长的路问题或移动销售代表问题（直接是 TSP））中减少它来证明“简化的最长路”是 NP 完成的。

算法

• 给定最长路径问题的出现，这是一个图 G 和一个解决理想路径长度的整数 k。

• 制作另一个图 G'，与 G 没有区别，具有相似的顶点和边。

• 将权重 1 分配给 G' 中的所有边。

• 将“增强型最长路径”问题的起始和结束枢纽设置为 G' 中的任意两个不稳定枢纽。

• 如果 G 具有长度为 k 的最长路径，则 G' 中的“改进最长路径”将是边缘负载量等于 k ​​的类似最长路径。

• 如果 G 没有长度为 k 的最长路径，则此时 G' 中将不存在边缘负载量等于 k ​​的路径。

• 由于最长的路问题已知是 NP 完成的，因此这种减少奠定了“简化的最长路”的 NP 顶峰。

• 这两种方法都概述了“高级最长路”是 NP 完成的，因此，没有已知的有效计算可以在所有情况下处理它，这显示了其计算的复杂性。

示例

#include <iostream>
#include <vector>

class Graph {
public:
   int V; // Number of vertices
   std::vector<std::vector<int>> adj;

   Graph(int V) : V(V) {
      adj.resize(V, std::vector<int>(V, 0));
   }

   void addEdge(int u, int v) {
      adj[u][v] = 1;
      adj[v][u] = 1;
   }

   bool hasEnhancedLongestWay(int k, int start, int end) {
      return false;
   }
};

int main() {
   int V = 5; // Number of vertices
   Graph G(V);
   G.addEdge(0, 1);
   G.addEdge(1, 2);
   G.addEdge(2, 3);
   G.addEdge(3, 4);

   int k = 3;
   int start = 0;
   int end = 4;
   bool hasEnhancedLongestWay = G.hasEnhancedLongestWay(k, start, end);
   std::cout << std::boolalpha << hasEnhancedLongestWay << 
std::endl;

   return 0;
}

输出

false

结论

转向第一种方法包括减少著名的哈密顿方法问题。通过将哈密顿路问题的案例转变为“高级最长路”的情况，我们表明解决最后一个问题在某种程度上与解决前一个问题一样困难，并阐述了其 NP 实现。

方法 2 直接解释了如何从另一个已知的 NP 完全问题、最长路问题或移动销售代表问题 (TSP) 中减少问题。通过演示“改进的最长路”可以转化为这些 NP 完全问题的方式，我们表明它具有类似的计算复杂性，并且以这种方式是 NP 完全的。

以上是优化的最长路径是NP完全的的详细内容。更多信息请关注PHP中文网其他相关文章！