Bagaimana saya bisa memverifikasi solusi untuk Traveling Salesman Problem dalam waktu polinomial?

31

Jadi, masalah keputusan TSP (Traveling salesman) adalah masalah NP yang lengkap .

Tetapi saya tidak mengerti bagaimana saya dapat memverifikasi bahwa solusi yang diberikan untuk TSP sebenarnya optimal dalam waktu polinomial, mengingat bahwa tidak ada cara untuk menemukan solusi optimal dalam waktu polinomial (yang karena masalahnya bukan pada P)?

Adakah yang bisa membantu saya melihat bahwa verifikasi sebenarnya dapat dilakukan dalam waktu polinomial?

complexity-theory np-complete traveling-salesman Lazer
sumber

20

Untuk lebih tepat, kita tidak tahu apakah TSP dalam . Ada kemungkinan bahwa hal itu dapat diatasi dalam waktu polinomial, meskipun mungkin kepercayaan umum adalah bahwa . Sekarang, ingat apa artinya menjadi -hard dan -complete, lihat misalnya jawaban saya di sini . Saya percaya sumber kebingungan berasal dari definisi: sebuah masalah -Hard tidak harus dalam . $\mathsf{P}$ $\mathsf{P} \neq \mathsf{NP}$ $\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{NP}$

Saat Anda dan halaman Wikipedia yang Anda tautkan menyatakan, masalah keputusannya adalah -complete: mengingat biaya dan bilangan bulat , putuskan apakah ada tur yang lebih murah daripada . Salah satu cara untuk melihat masalah dalam adalah untuk melihat bahwa diberikan solusi, mudah untuk memverifikasi dalam waktu polinomial apakah solusi lebih murah daripada . Bagaimana Anda bisa melakukan ini? Ikuti saja tur yang diberikan, catat total biaya dan akhirnya bandingkan total biaya dengan . $\mathsf{NP}$ $x$ $x$ $\mathsf{NP}$ $x$ $x$

Juho
sumber

"Ikuti saja tur yang diberikan, catat total biaya dan akhirnya bandingkan total biaya dengan x." -> Ya, tetapi ada sejumlah tur eksponensial untuk diperiksa!

Lazer

2

Sepertinya saya agak lambat, sepertinya. ;-)

Niel de Beaudrap

3

@ Lazer Tidak, hanya ada satu tur untuk diperiksa. Anda diberi tur dan Anda mencatat panjangnya. Jika kurang dari

, output ya , jika tidak , tidak .

x

$x$

Juho

"putuskan apakah ada tur" ini jelas berarti bahwa kita tidak diberikan tur. Apa yang saya lewatkan?

Lazer

3

@ Lazer Tidak, dalam masalah Anda diberi grafik berbobot dan biaya target. Sertifikat itu adalah tur. Untuk penjelasan alternatif, lihat jawaban Niel. Sama seperti pada contoh di Wiki dalam kasus SUBSET-SUM, kita tidak diberikan nol, tetapi sebaliknya kita diberi subset tertentu sebagai sertifikat.

Juho

34

Intinya adalah Anda harus mempertimbangkan masalah keputusan :

Traveling Salesman Problem (Versi Keputusan). Dengan diberi grafik G tertimbang dan target biaya C , apakah ada siklus Hamiltonian dalam G yang beratnya paling banyak C ?

Untuk 'ya' Misalnya, sertifikat hanya beberapa siklus Hamiltonian yang berat badannya paling C . Jika Anda dapat memecahkan masalah ini secara efisien, Anda dapat menemukan biaya tur minimum dengan pencarian biner, dimulai dengan bobot seluruh jaringan sebagai batas atas.

Niel de Beaudrap
sumber

3

Anda mungkin berpikir tentang masalah menentukan apakah solusi yang diberikan untuk TSP adalah solusi terbaik . Namun, tidak ada solusi polinomial yang diketahui untuk ini, yang berarti bahwa masalah ini adalah NP-hard, tetapi tidak harus NP-Complete.

Masalah Keputusan TSP sebenarnya adalah tentang menentukan apakah bobot suatu solusi dalam grafik Gpaling mahal C(seperti yang dijelaskan lebih baik dalam jawaban Niel), yang tentunya dapat diverifikasi dalam waktu polinomial.

Casey Kuball
sumber

5

O (n!)

$O(n!)$

n!

$n!$

n_{0} <= n_{1} <= . . .

$n_0 <= n_1 <= ...$

4

Tidak, Anda dapat memperoleh yang optimal bahkan tanpa menghitung panjang semua tur lainnya. Dan ya, dimungkinkan untuk membuktikan bahwa ini adalah yang optimal tanpa menghitung semua tur lainnya. Sebagai contoh pertimbangkan cabang & terikat.

Juho

7

Yang saya katakan adalah ruang pencarian yang besar tidak selalu berarti masalahnya sulit. Bahkan ketika kita misalnya tidak mengetahui algoritma yang lebih baik daripada brute-force yang menyebutkan semua kemungkinan, itu tidak berarti itu satu-satunya algoritma di luar sana. Pemrograman dinamis adalah contoh yang baik bahkan di sini: algoritma Held-Karp adalah algoritma yang tepat untuk TSP berjalan di

O (n^{2} 2^{n})

$O(n^22^n)$

@ Juho poin bagus. Saya telah memperbarui jawaban untuk tidak lagi menunjukkan kekerasan sebagai satu-satunya pilihan (hanya saja tidak ada solusi polinomial).

Casey Kuball

2

$M$ $M$

Secara rekursif kronis
sumber

Bagaimana saya bisa memverifikasi solusi untuk Traveling Salesman Problem dalam waktu polinomial?

Jawaban: