C++ 优化的最长路径是NP完全问题

“升级的最长路径”问题是一个计算上困难的任务，被定义为NP完全问题。在这个问题中，给定带有加权边的图表，目标是找到从预定的起始节点到终止节点的最长路径，同时增加边的负载。由于对于所有情况，已知的多项式时间算法无法高效地解决这个问题，因此科学家们常常使用近似算法和启发式算法来寻找接近最优解的解决方案。这个问题的困难性在不同领域都有明显的影响，如交通运输、计划操作和项目安排。

使用的方法

从汉密尔顿路径问题中简化
使用已知的NP完全问题

从汉密尔顿路径问题中简化

解决“升级的最长路径”是NP完全问题的一种方法是通过将其简化为著名的NP完全问题，即汉密尔顿路径问题。汉密尔顿路径问题确定给定图表中是否存在一个路径，该路径恰好访问每个顶点一次。

步骤

取汉密尔顿路径问题的一个案例，记为图表G。
创建一个与G相同的图表G’，具有相同的顶点和边。
在G’中的所有边上分配权重1。
将“优化的最长路径”问题的起始和终止节点设置为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完全问题

另一种方法是通过将“Streamlined Longest Way”从已知的NP完全问题（如Longest Way问题或Mobile Sales rep问题）中减少来证明其为NP完成问题。

步骤

给定一个Longest Way问题的实例，其中包括一个图G和一个表示最佳路径长度的整数k。
创建一个新的图G’，与G相同，具有相同的顶点和边。
为G’中的所有边分配权重1。
将“优化的最长路径”问题的起始和结束节点设置为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;
}