Algoritma Dijsktra diterapkan untuk masalah salesman keliling

Saya seorang pemula (total pemula untuk teori kompleksitas komputasi) dan saya punya pertanyaan.

Katakanlah kita memiliki 'Traveling Salesman Problem', akankah aplikasi Algoritma Dijkstra berikut ini menyelesaikannya?

Dari titik awal kami menghitung jarak terpendek antara dua titik. Kami langsung ke intinya. Kami menghapus titik sumber. Kemudian kita menghitung titik jarak terpendek berikutnya dari titik saat ini dan seterusnya ...

Setiap langkah kita membuat grafik lebih kecil sementara kita memindahkan titik jarak terpendek berikutnya yang tersedia. Sampai kami mengunjungi semua poin.

Apakah ini akan menyelesaikan masalah penjual keliling.

Algoritma Dijkstra mengembalikan pohon jalur terpendek, yang berisi jalur terpendek dari titik awal ke titik lainnya, tetapi tidak harus jalur terpendek antara titik lainnya, atau rute terpendek yang mengunjungi semua titik.

Berikut ini contoh contoh di mana algoritma serakah yang Anda uraikan tidak akan berfungsi:

Mulai dari , algoritma serakah akan memilih rute , tetapi rute terpendek dimulai dan berakhir pada adalah . Karena rute TSP tidak diperbolehkan untuk mengulang simpul, setelah algoritma serakah memilih , ia terpaksa mengambil ujung terpanjang untuk kembali ke kota awal.$a$$[a,b,c,d,a]$$a$$[a,b,d,c,a]$$a,b,c,d$$d,a$

Seperti yang ternyata di balasan lain, saran Anda tidak secara efektif menyelesaikan Masalah Traveling Salesman, izinkan saya menunjukkan cara terbaik yang dikenal di bidang pencarian heuristik (karena saya melihat algoritma Dijkstra agak terkait dengan bidang Kecerdasan Buatan) .

Algoritma heuristik dapat mengembalikan solusi optimal (meskipun ukuran yang dapat dikelola relatif kecil sebagai fakta) dan metode berikut ini disarankan oleh Richard Korf pada tahun 90-an. Sementara itu bekerja dengan sempurna untuk masalah salesman keliling simetris (di mana biaya edge sama dengan biaya edge yang sama ketika dilintasi pada arah yang berlawanan ), ia dapat dengan mudah disesuaikan dengan alternatif. kasus versi asimetris.$(u,v)$$(v,u)$

Pendekatan terbaik (saya sadar) terdiri dari menjalankan algoritma pencarian heuristik Depth-First Branch-and Bound di mana heuristik adalah biaya Minimum Spanning Tree (MST). Karena MST dapat dihitung dalam waktu polinomial dengan algoritma Prim atau algoritma Kruskal , maka dapat diharapkan untuk mengembalikan solusi dalam jumlah waktu yang wajar. Untuk diskusi yang luar biasa dari kedua algoritma ini, saya sangat menyarankan Anda untuk melihat The Algorithm Design Manual

Sebenarnya, izinkan saya menggarisbawahi bahwa karena pendekatan ini disarankan tidak banyak kemajuan yang terlihat di lapangan untuk mendapatkan batas optimal dari masalah ini sehingga saya menganggapnya sebagai pertanyaan panas di bidang pencarian kombinatorial.

Semoga ini membantu,

Saya tidak tahu bagaimana orang di sini tidak memperhatikan bahwa penerapan algoritma Dijkstra akan sepenuhnya tidak diperlukan dalam kasus ini? Anda bisa menerapkan algoritma serakah ini dengan hanya memilih simpul terdekat, yang dikenal apriori. Algoritma Dijkstra digunakan untuk menemukan jalur, tetapi Anda hanya mengambil satu langkah setiap kali. Ini jelas tidak menemukan solusi optimal untuk TSP, tetapi banyak pendekatan yang sangat baik tidak menemukannya. Semua pencari solusi optimal untuk TSP sangat menuntut komputasi.

Jawabannya adalah tidak, itu bukan cara yang baik untuk menyelesaikan masalah TSP. Contoh penghitung yang baik adalah di mana semua titik berada pada satu garis, seperti berikut ini:

--5 ------------------ 3 ----- 1--0 --- 2 ---------- 4

menggunakan algoritma Dijsktra, akan membuat wiraniaga miskin mulai dari titik 0, pertama pergi ke 1 lalu ke 2 lalu ke 3 dll. mana yang tidak optimal.

Semoga itu bisa membantu. Lihat bab pertama dalam buku hebat Steven S. Skiena berjudul "The Algorithm Design" yang menjelaskan contoh ini secara lebih rinci.

Masalah TSP bukanlah menemukan jalan terpendek antara dua titik, tetapi dalam membuat rute antara semua titik yang optimal. Ketika Anda memiliki rute optimal, Anda dapat menggunakan Dijsktra untuk menemukan jalur terpendek antara setiap titik dalam rute.