Algoritma waktu linier untuk menemukan

8

Definisi. Diberikan grafikG=(V,E) dan dua simpul s dan t, itu kmasalah -shortest-paths adalah menemukan k jalur sederhana terpendek antara s dan t di G.

Perhatikan bahwa panjang jalur ini tidak harus sama, dan simpul s dan t tentu saja k-terhubungan Saya bertanya-tanya apakah ada waktu linier (dalam haln dan m) algoritma untuk masalah ini.

Saya telah melihat beberapa makalah dalam literatur, seperti " Implementasi Baru Algoritma Loopless Ranking Ranking Yen " tetapi kompleksitas waktu sangat tinggiO(Kn(m+nlogn)). Juga, makalah lain oleh Epstein " Menemukan jalur terpendek k " menyajikan algoritma yang menemukank jalur terpendek yang tidak harus jalur sederhana dengan waktu berjalan O(n+m+k).

Apakah ada algoritma linear-waktu untuk k-simple-shortest-paths problem?

orezvani
sumber
Algoritma @DW Eppstein menemukan jalur yang tidak selalu sederhana. OP menginginkan algoritma yang serupa, mungkin dalam waktu berjalan yang sama, yang menemukankjalur sederhana terpendek . Algoritme peringkat Yen terlalu lambat untuk itu.
Yuval Filmus

Jawaban:

7

Pertama-tama, jawaban yang berlaku di sini sudah diberikan oleh Raphael dalam komentar untuk pertanyaan: " Mengingat bahwa kita bahkan tidak tahu bagaimana menemukan satu jalur terpendek sederhana dalam waktu linear, saya ragu. " Berikut ini, dengan demikian, saya akan menganggap Anda tertarik mengetahui tentang algoritma terbaik yang tersedia dalam keadaan saat ini. Berikut ini, saya menggambarkan ikatan kasus terburuk terbaik (sesuai pengetahuan saya) tetapi juga algoritma yang mungkin berjalan dalam waktu linier dalam beberapa kasus tertentu.

Tetapi sebelum menggambarkan perkembangan terbaru dalam keadaan seni, saya ingin menekankan pentingnya jalur sederhana dalam masalah khusus ini. Faktanya, banyak orang mengabaikan pentingnya persyaratan ini dan beberapa bahkan tidak memahaminya pada pandangan pertama.

Ketika menghitung jalur terpendek dari mulai titik ke titik tujuan, jalur optimal tentu sederhana , yaitu, tidak mengulangi simpul apa pun. Namun, saat komputasikjalur optimal, jalur kedua, ketiga, ... jalur terbaik mungkin tidak sederhana. Untuk membuktikannya, saya berikan di sini sebuah contoh yang telah sedikit diadaptasi dari Hershberger, Maxel & Suri, 2007:

masukkan deskripsi gambar di sini

Gambar ini menunjukkan digraf yang solusi optimalnya (dari titik sumber s ke titik tujuan t) adalah path π1:s,SEBUAH,B,C,D,t dengan biaya sama dengan 5. Jika jalur tidak harus sederhana, maka jalur optimal kedua dan ketiga adalah π2:s,SEBUAH,B,C,D,C,D,t dan π3:s,SEBUAH,B,SEBUAH,B,C,D,t keduanya dengan biaya sama dengan 7. Namun, jika jalur harus sederhana, maka jalur optimal kedua dan ketiga akan menjadi π2:s,F,t dan π3:s,G,t dengan biaya 10 dan 11, masing-masing.

Diberikan grafik G(V,E) dimana V adalah himpunan simpul dan kamu,vE,kamu,vV jika ada tepi antara simpul kamu dan v, keadaan terkini untuk masalah ini sejauh yang saya ketahui dijelaskan di bawah ini:

Peningkatan signifikan pertama untuk menyelesaikan k masalah jalur optimal adalah algoritma Eppstein (Eppstein, 1998) yang berjalan di HAI(|E|+|V|catatan|V|+k). Namun, algoritma ini membutuhkan grafik untuk diberikan secara eksplisit.Kmeringankan persyaratan ini dengan tetap mempertahankan kompleksitas yang rendah (Aljazzar & Leue, 2011) dan, di samping itu, memungkinkan penerapan heuristik yang dapat diterima. Dalam kedua kasus, output yang dihitung oleh algoritma ini tidak selalu merupakan jalur yang sederhana.

Dalam hal jalur diperlukan untuk menjadi sederhana, hasil terbaik adalah karena Yen (Yen, 1971, 1972), digeneralisasi kemudian oleh Lawler (Lawler, 1972), yang menggunakan struktur data modern dapat diimplementasikan dalam HAI(k|V|(|E|+|V|catatan|V|))waktu terburuk. Dalam kasus grafik tidak terarah, Katoh, Ibaraki dan Mine (Katoh, Ibaraki & Mine, 1982) meningkatkan algoritma Yen untukHAI(k(|E|+|V|catatan|V|))waktu. Sementara kasus terburuk asimptotik Yen terikat untuk pencacahank jalur terpendek sederhana dalam grafik terarah tetap tak terkalahkan (sekali lagi, sepengetahuan saya!), beberapa upaya telah dilakukan untuk mengungguli itu dalam praktik.

Salah satu karya tersebut adalah karena John Hershberger et al., Yang memperkenalkan algoritma jalur penggantian yang dikenal gagal hampir tidak ada. Alhasil, algoritma mereka memberikan kecepatan yang tumbuh secara linear dengan jumlah rata-rata tepi dik jalur terpendek tetapi, untuk beberapa kasus (sebagai grafik acak), peningkatan ini diminimalkan.

Semoga ini membantu,

Bibliografi

Aljazzar, H. & Leue, S. (2011). K: Algoritma pencarian heuristik untuk menemukan kjalur terpendek. Kecerdasan Buatan, 175 (18), 2129-2154.

Eppstein, D. (1998). Menemukankjalur terpendek. Jurnal SIAM tentang Komputer, 28 (2), 652-673.

Hershberger, J., Maxel, M. & Suri, S. (2007). Menemukankjalur sederhana terpendek: Algoritma baru dan implementasinya. Transaksi ACM pada Algoritma, 3 (4), 45-46

Katoh, N., Ibaraki, T. & Mine, H. (1982). Algoritma yang efisien untukkjalur sederhana terpendek. Jaringan, 12, 411-427.

Lawler, EL (1972). Prosedur untuk menghitungksolusi terbaik untuk masalah optimasi diskrit dan penerapannya ke masalah jalur terpendek. Ilmu Manajemen, 18, 401-405.

Yen, JY (1971). Menemukankjalur loopless terpendek dalam jaringan. Ilmu Manajemen, 17, 712-716.

Yen, JY (1972). Algoritma lain untuk menemukankjalur jaringan tanpa loop terpendek. Prosiding Masyarakat Manajemen Operasi Riset ke-41 Amerika, 20.

Carlos Linares López
sumber
Terima kasih, ini benar-benar berfungsi HAI(n+m)dalam grafik tidak tertimbang. Bahkan, makalah yang lebih baru (disebutkan dalam pertanyaan) membuat saya berpikir bahwa waktu tayangnya harus lebih baik daripada Kotah; itu memberi saya kesan yang salah.
orezvani
Senang mendengarmu menyukainya @kezzos
Carlos Linares López