Pertanyaan Apa perbedaan antara Travelling Salesman dan menemukan Shortest Path?


Satu-satunya perbedaan yang bisa saya pikirkan untuk pertanyaannya adalah bahwa dalam Masalah Salesman Perjalanan (TSP) Saya harus mencari permutasi minimum dari semua simpul dalam grafik dan dalam masalah Jalan Terpendek tidak perlu mempertimbangkan semua simpul kita dapat mencari ruang negara untuk rute panjang lintasan minimum yang dapat menyarankan lebih banyak perbedaan.


32
2017-10-14 05:28


asal


Jawaban:


Anda sudah memanggil perbedaan esensial: TSP adalah untuk menemukan jalur yang berisi permutasi setiap node dalam grafik, sementara dalam masalah jalur terpendek, setiap jalur terpendek mungkin, dan sering, mengandung a layak subset dari simpul dalam grafik.

Perbedaan lain termasuk:

  • Solusi TSP membutuhkan jawabannya sebagai siklus.
  • Solusi TSP tentu akan mengulang node di jalurnya, sementara jalur terpendek tidak akan (kecuali seseorang mencari jalur terpendek dari sebuah node ke dirinya sendiri).
  • TSP adalah masalah NP-lengkap dan jalur terpendek dikenal waktu polinomial.

Jika Anda mencari pernyataan yang tepat tentang perbedaan, saya akan mengatakan Anda hanya perlu mengganti ide Anda tentang "permutasi" dengan istilah yang lebih teknis dan tepat "siklus sederhana mengunjungi setiap node dalam grafik", atau lebih baik, "Siklus Hamilton ":

TSP membutuhkan satu untuk menemukan siklus sederhana mencakup setiap node dalam grafik dengan berat terkecil (alternatifnya, siklus Hamilton dengan berat terkecil). Masalah Jalan Terpendek membutuhkan satu untuk menemukan jalur antara dua node yang diberikan dengan berat terkecil. Jalur terpendek tidak harus Hamiltonian, juga tidak perlu siklus.


36
2017-10-14 05:36



Dengan masalah jalur terpendek Anda mempertimbangkan jalur antara dua node. Dengan TSP, Anda mempertimbangkan jalur antara semua node. Ini membuat yang terakhir jauh lebih sulit.

Pertimbangkan dua jalur antara simpul A dan B. Satu di atas D yang lain dari C. Biarkan yang lebih dari C menjadi jalur yang lebih panjang. Dalam masalah Jalan Terpendek jalan ini bisa segera dibuang. Di dalam TSP, sangat mungkin bahwa jalan ini adalah bagian dari solusi menyeluruh, karena Anda harus mengunjungi C dan mengunjunginya nanti mungkin akan lebih mahal.

Oleh karena itu Anda tidak dapat memecah TSP di sub-masalah yang serupa tetapi lebih kecil.


7
2017-10-14 05:48



Di TSP, Anda perlu mengunjungi semua node dan juga kembali ke titik awal Anda. Ini sangat mempersulit masalah.


1
2017-10-14 05:30



Jalur terpendek hanya memiliki sumber dan target. Kita perlu menemukan jalur terpendek di antara mereka jelas output harus pohon dalam waktu polinomial.

Menemukan Jalur Terpendek: -

  • Grafik yang tidak diarahkan: Algoritma Dijkstra dengan daftar O (V ^ 2)

  • Grafik yang disutradarai dengan bobot acak tanpa siklus negatif: Algoritma Bellman – Ford Kompleksitas waktu O (VE)

  • Algoritma Floyd – Warshall digunakan untuk menemukan jalur terpendek di antara semua pasangan

TSP (Masalah Traveling-Salesman) tidak seperti itu kami telah mencakup setiap node dari sumber dan akhirnya kami telah mencapai sumber dengan biaya minimum. Sebenarnya harus ada siklus. TSP adalah masalah NP-lengkap

Ref:

https://en.wikipedia.org/wiki/Shortest_path_problem

https://en.wikipedia.org/wiki/Travelling_salesman_problem

http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/


1
2017-09-03 14:37