優化的最長路徑是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中文網其他相關文章！