Saya sedang memecahkan masalah optimisasi pencarian grafik. Saya perlu menemukan jalur terpendek asiklik k terbaik melalui grafik tertimbang yang diarahkan.
Saya tahu ada sejumlah algoritma k-best yang tepat dan perkiraan, tetapi sebagian besar penelitian baru-baru ini tampaknya berorientasi pada grafik yang sangat besar, terhubung sangat jarang (misalnya, rute dan arah jalan), dan grafik saya tidak.
Aspek yang membedakan masalah saya:
Grafik terdiri dari sekitar 160 simpul.
Grafik hampir sepenuhnya terhubung (dua arah, jadi ~ 160 ^ 2 ~ = 25k tepi)
k akan cukup kecil (mungkin kurang dari 10)
Panjang jalur maksimum mungkin akan dibatasi dan sangat kecil juga (mis. 3-5 tepi)
Saya mengatakan 'asiklik' di atas, tetapi hanya untuk mengulangi - solusi tidak harus mencakup siklus. Ini bukan masalah untuk jalur terpendek 1-terbaik, tetapi itu menjadi masalah bagi k-best - misalnya, pertimbangkan rute jalan - jalur terpendek kedua dari A ke B mungkin sama dengan yang terbaik 1, dengan perjalanan cepat di sekitar blok di suatu tempat. Itu mungkin secara matematis optimal, tetapi bukan solusi yang sangat berguna. ;-)
Kita mungkin perlu menimbang ulang tepi on the the fly untuk setiap perhitungan. Biaya tepi terdiri dari jumlah tertimbang dari beberapa faktor, dan persyaratan akhir (setiap kali kami mendapatkannya) dapat memungkinkan pengguna untuk menentukan prioritas mereka sendiri dari faktor-faktor pembobotan, mengubah bobot tepi. Ini adalah grafik yang relatif kecil (kita harus dapat merepresentasikannya dalam beberapa ratus KB), jadi mungkin masuk akal untuk mengkloning grafik dalam memori, menerapkan pembobotan ulang, dan kemudian menjalankan pencarian pada grafik yang dikloning. Tetapi jika ada metode yang lebih efektif untuk melakukan pencarian sambil menghitung bobot saat berjalan, saya tertarik.
Saya melihat algoritma yang dijelaskan dalam Santos (algoritma jalur terpendek K), Eppstein 1997 (Menemukan k Jalur Terpendek), dan lainnya. Algoritma Yen menarik, terutama karena implementasi Java yang ada . Saya tidak takut membaca makalah penelitian, tetapi saya pikir layak membuang rincian masalah saya dan meminta petunjuk untuk menghemat waktu membaca.
Dan jika Anda memiliki petunjuk implementasi Java, bahkan lebih baik.
sumber
Jawaban:
Untuk sebagian menjawab pertanyaan saya sendiri:
Sejak memposting pertanyaan ini, saya menemukan bahwa kita perlu menangani bobot tepi negatif dan juga positif (batasan untuk jalur asiklik / sederhana / tanpa loop berarti bahwa solusi terbaik ditentukan, sedangkan tanpa batasan itu jalur terpendek melalui grafik dengan negatif- siklus biaya tidak ditentukan).
Algoritma Yen, dan sebagian besar yang saya periksa, bergantung pada serangkaian pencarian 1-terbaik; kebanyakan menggunakan Dijkstra untuk pencarian perantara tersebut. Dijkstra tidak mendukung bobot tepi negatif, tetapi kita dapat menggantikan Bellman-Ford sebagai gantinya (setidaknya dalam Yen; mungkin juga di Lawler atau Eppstein juga). Saya telah mengembangkan modifikasi Bellman-Ford dengan batasan lintasan panjang (pada tepian) dan pemeriksaan siklus eksplisit selama pencarian (menggantikan deteksi siklus pasca-pencarian standar). Kompleksitas komputasinya lebih buruk, tetapi masih bisa digunakan untuk kebutuhan saya. Saya akan mengedit respons ini dan menautkan ke laporan teknologi jika saya mendapat izin untuk mempostingnya.
sumber
Saya akan mengatakan pertanyaan ini dapat dengan mudah di-Google-kan dan juga merupakan duplikat:
Yang sedang berkata, saya sudah menggunakan dan mengimplementasikan Eppstein dan merekomendasikannya. Saya merasa cukup elegan. Jika saya ingat benar, mungkin juga optimal, dan makalah berikut menjelaskannya dengan sangat baik:
http://pdf.aminer.org/001/059/121/finding_the_k_shortest_paths.pdf
sumber