Laluan terpanjang yang dioptimumkan ialah NP-lengkap

Masalah "Naik Taraf Laluan Terpanjang" ialah tugasan yang sukar dari segi pengiraan yang diperintahkan supaya NP-lengkap. Dalam isu ini, diberikan graf dengan tepi berwajaran, matlamatnya adalah untuk mencari laluan terpanjang daripada hab permulaan yang telah ditetapkan kepada hab penutup sambil membesarkan pemuatan tepi. Disebabkan perkembangan ketara kaedah penyelidikan yang mungkin, tiada pengiraan masa polinomial yang diketahui dapat menyelesaikan masalah ini dengan cekap dalam semua kes. Semua perkara yang dipertimbangkan, saintis bergantung pada pengiraan spekulatif dan heuristik untuk mengesan susunan ideal yang paling hampir. Masalah dengan isu ini telah memberi kesan dalam bidang yang berbeza seperti pengangkutan, operasi perancangan dan tempahan tempahan.

Kaedah penggunaan

• Masalah laluan Hamiltonian dipermudahkan

• Gunakan masalah lengkap NP yang diketahui

Memudahkan masalah laluan Hamiltonian

Salah satu cara untuk menyelesaikan masalah "upgrade longest path" yang NP-complete adalah dengan menunjukkan pengurangan berbanding masalah NP-complete yang terkenal (dipanggil Hamiltonian Road Problem). Masalah Jalan Hamiltonian menentukan sama ada graf tertentu mengandungi laluan yang melawati setiap bucu tepat sekali.

Algoritma

• Ambil masalah jalan raya Hamilton sebagai contoh, iaitu graf G.

• Buat satu lagi graf G', tidak boleh dibezakan daripada G, dengan bucu dan tepi yang serupa.

• Berikan berat 1 kepada semua tepi dalam G'.

• Tetapkan pangsi permulaan dan penamat masalah "laluan terpanjang ditambah" kepada mana-mana dua pangsi tidak stabil dalam G'.

• Jika G mempunyai laluan Hamiltonian, "laluan terpanjang yang dinaik taraf" dalam G' akan menjadi laluan Hamiltonian yang serupa dengan beban tepi yang sama dengan bilangan tepi yang sama dengan bilangan bucu yang lebih pendek.

• Jika G tidak mempunyai jalan Hamiltonian, maka "laluan terpanjang yang diperkemas" di G' pada masa ini akan menjadi laluan terus dari hab permulaan ke hab penutup, di mana jumlah muatan tepi adalah sama dengan bilangan tepi, yang tidak lengkap ialah bilangan bucu pendek.

• Penurunan ini menunjukkan bahawa menyelesaikan "laluan terpanjang yang dipertingkatkan" sama sukarnya dengan menyelesaikan masalah Jalan Hamiltonian, menjadikannya masalah lengkap NP.

Contoh

#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;
}

Output

G does not have a Hamiltonian Path.

Gunakan masalah lengkap NP yang diketahui

Pendekatan lain adalah untuk membuktikan bahawa "laluan terpanjang yang dikurangkan" adalah NP-lengkap dengan mengurangkannya daripada masalah lengkap NP yang diketahui seperti masalah laluan terpanjang atau masalah wakil jualan yang bergerak (secara langsung TSP).

Algoritma

• Memandangkan masalah laluan terpanjang timbul, iaitu graf G dan integer k yang menyelesaikan untuk panjang laluan ideal.

• Buat satu lagi graf G', tidak berbeza dengan G, dengan bucu dan tepi yang serupa.

• Berikan berat 1 kepada semua tepi dalam G'.

• Tetapkan pangsi permulaan dan penamat masalah "laluan terpanjang ditambah" kepada mana-mana dua pangsi yang tidak stabil dalam G'.

• Jika G mempunyai laluan terpanjang dengan panjang k, maka "laluan terpanjang yang dipertingkatkan" dalam G' akan menjadi laluan terpanjang yang serupa dengan muatan tepi bersamaan dengan k.

• Jika G tidak mempunyai laluan terpanjang dengan panjang k, maka tidak akan ada laluan dalam G' dengan beban tepi bersamaan dengan k pada masa ini.

• Memandangkan masalah laluan terpanjang diketahui telah selesai NP, pengurangan ini mewujudkan puncak NP "laluan terpanjang yang dipermudahkan".

• Kedua-dua kaedah menggariskan bahawa "laluan terpanjang peringkat tinggi" adalah NP-lengkap dan oleh itu, tiada pengiraan cekap diketahui yang boleh mengendalikannya dalam semua kes, yang menunjukkan kerumitan pengiraannya.

Contoh

#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;
}

Output

false

Kesimpulan

Bergerak ke pendekatan pertama melibatkan mengurangkan masalah kaedah Hamiltonian yang terkenal. Dengan mengubah kes Masalah Jalan Hamiltonian kepada kes "Jalan Terpanjang Termaju", kami menunjukkan bahawa menyelesaikan masalah terakhir entah bagaimana sukar seperti menyelesaikan masalah sebelumnya dan menghuraikan pelaksanaan NPnya.

Kaedah 2 menerangkan secara langsung bagaimana untuk mengurangkan masalah daripada satu lagi masalah lengkap NP yang diketahui, Masalah Laluan Terpanjang, atau Masalah Wakil Jualan Bergerak (TSP). Dengan menunjukkan cara "laluan terpanjang yang dipertingkatkan" boleh diubah menjadi masalah NP-lengkap ini, kami menunjukkan bahawa ia mempunyai kerumitan pengiraan yang serupa dan NP-lengkap dengan cara ini.

Atas ialah kandungan terperinci Laluan terpanjang yang dioptimumkan ialah NP-lengkap. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!