Incremental Maximum Flow dalam grafik Dinamis

Saya mencari algoritma cepat untuk menghitung aliran maksimum dalam grafik dinamis. yaitu diberi grafik dan s , t ∈ V kita memiliki aliran maksimum F dalam G dari s ke t . Kemudian simpul baru / lama u ditambahkan / dihapus dengan tepi yang sesuai untuk membentuk grafik G 1 . Berapakah aliran maksimum dalam grafik yang baru dibuat? Apakah ada cara untuk mencegah penghitungan ulang aliran maksimum?$G=(V,E)$$s,t\in V$$F$$G$$s$$t$$u$$G^1$

Setiap preprocessing yang tidak terlalu memakan waktu / memori dihargai.

Ide paling sederhana adalah menghitung ulang alurnya.

Gagasan sederhana lainnya adalah karena ini, simpan semua jalur penambahan yang digunakan dalam perhitungan aliran maksimum sebelumnya, untuk menambahkan vertex , kita dapat menemukan jalur sederhana (dalam grafik kapasitas yang diperbarui dengan langkah sebelumnya) yang dimulai dari sumber, pergi ke v kemudian pergi ke tujuan, tetapi masalahnya adalah, jalan ini harus sederhana, saya tidak dapat menemukan lebih baik daripada O ( n ⋅ m ) untuk kasus ini, untuk m = | E | . (Perhatikan juga bahwa jika hanya satu jalur, ini bisa dilakukan dalam O ( n + m ) tetapi tidak demikian.)$v$$v$$O(n\cdot m)$$m=|E|$$O(n+m)$

Juga untuk menghapus simpul di atas ide tidak berfungsi.

Saya juga sudah melihat makalah seperti pendekatan inkremental untuk edge , tetapi tampaknya mereka tidak cukup baik dalam hal ini, lebih dari untuk setiap edge dan sepertinya tidak cocok untuk kasus ini (kami hanya menghitung ulang aliran). Juga saat ini saya menggunakan algoritma aliran maksimum Ford-Fulkerson. Jika ada pilihan yang lebih baik untuk algoritma online, ada baiknya mengetahuinya.$O(m)$

Pendekatan yang dijelaskan mungkin tidak optimal secara teoritis. Ini hanyalah solusi praktis sederhana yang dapat bekerja untuk penulis. Saya tidak dapat memberikan referensi apa pun karena saya selalu berpikir itu adalah cerita rakyat yang dikenal luas, tetapi anehnya tidak ada yang mempostingnya dalam jawaban. Jadi saya melakukannya.

Asumsikan kita memiliki jaringan tidak diarahkan . Asumsikan disimpan dalam struktur data yang memungkinkan penyisipan / penghapusan vertex / arc dengan mudah. Kadang-kadang kita akan menggunakan sisa jaringan G f (yaitu dengan kapasitas diperbarui c f = c - f ).$G=(V,E,c)$$G_f$$c_f = c - f$

Bagian pertama adalah bagaimana memproses penyisipan / penghapusan titik. Ini lebih atau kurang mudah untuk dimasukkan:

1. Tambahkan simpul baru dengan tepi yang sesuai ke jaringan residual.
2. Temukan aliran maksimum di jaringan residu yang diperbarui menggunakan algoritma maxflow pilihan Anda.

Untuk penghapusan hal menjadi lebih rumit. Bayangkan kita membagi simpul kita akan menghapus menjadi 2 bagian v i n dan v o u t sehingga semua di-busur poin ke v i n , semua keluar-busur pergi dari v o u t dan simpul baru ini terhubung oleh busur kapasitas tak terbatas. Kemudian penghapusan v setara dengan penghapusan busur antara v i n dan v o u t . Apa yang akan terjadi dalam kasus ini? Masing menunjukkan Let oleh f $v$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$v$$v_{in}$$v_{out}$$f^v$aliran melewati titik . Kemudian v i n akan mengalami kelebihan f v unit aliran dan v o u t akan mengalami kekurangan f v unit aliran tepat setelah penghapusan (kendala aliran akan jelas rusak). Untuk membuat kendala aliran ditahan lagi, kita harus mengatur ulang aliran, tetapi juga kita ingin menjaga nilai aliran asli setinggi mungkin. Mari kita lihat dulu apakah kita bisa melakukan penataan ulang tanpa mengurangi total aliran. Untuk memeriksa yang menemukan maxflow ~ f v dari v i n ke v o $v$$v_{in}$$f^v$$v_{out}$$f^v$$\tilde{f^v}$$v_{in}$ di "dipotong" jaringan residual (yaitu tanpa busur yang menghubungkan v i n dan v o u t ). Kita harus terikat dengan f v jelas. Jika hal itu terjadi untuk menjadi sama dengan f v maka kita beruntung: kami telah ditugaskan kembali aliran yang melewativsedemikian rupa bahwa total aliran tidak berubah. Dalam kasus lain aliran total harus dikurangi oleh kelebihan "tidak berguna" dariΔ= f v - ~ f v unit. Untuk melakukan itu, sementara connectsdan$v_{out}$$v_{in}$$v_{out}$$f^v$$f^v$$v$$\Delta = f^v - \tilde{f^v}$$s$$t$oleh busur kapasitas tak terbatas dan menjalankan algoritma Maxflow lagi dari ke v o u t (kita harus terikat aliran oleh Δ ). Itu akan memperbaiki jaringan sisa dan membuat kendala aliran ditahan lagi, secara otomatis mengurangi aliran total sebesar Δ .$v_{in}$$v_{out}$$\Delta$$\Delta$

Kompleksitas waktu dari pembaruan tersebut mungkin tergantung pada algoritma maxflow yang kami gunakan. Namun, kasus terburuk mungkin sangat buruk, tetapi masih lebih baik daripada penghitungan ulang total.

$O(|V|^2|E|)$$O(|E|^2 \log C_{max})$

ok dengan mempertimbangkan info baru & menghindari beberapa referensi awal yang salah / arahan herring merah yang rumit (mea culpa), berikut adalah beberapa referensi baru tentang hal ini.

Memecahkan Urutan Online dari Masalah Aliran Maksimum dengan Ekstensi untuk Menghitung Pemotongan Minimum yang Kuat Doug Altner dan Özlem Ergun

referensi ini mempertimbangkan urutan online MFP dan "pemanasan awal" yaitu membangun pada chgs tambahan ke MFP sebelumnya. "Kami mendemonstrasikan bahwa algoritme kami mengurangi waktu berjalan dengan urutan besarnya bila dibandingkan dengan kode serupa yang menggunakan pemecah MFP kotak hitam. Secara khusus, kami menunjukkan bahwa algoritme kami untuk pemotongan minimum yang kuat dapat menyelesaikan contoh dalam detik yang akan membutuhkan lebih dari empat jam menggunakan pemecah aliran maksimum kotak hitam. "

kemajuan pada masalah yang melibatkan arus maksimum Altner, Douglas S., teknologi georgia

dalam tesis Phd 2008 ini (pdf dapat diunduh) penulis mempertimbangkan masalah penambahan busur yang tampaknya "cukup dekat" dengan masalah menambahkan simpul baru (dengan beberapa busur baru).

banyak dari referensi ini berkaitan dengan penghapusan bagian-bagian jaringan (pemotongan / "larangan") sebagaimana dinyatakan dalam bagian pertama dari abstrak

lihat esp "IV MEMECAHKAN URUTAN ONLINE DARI ALIRAN MAKSIMUM.... p63".

p 63 "Namun, tujuan bab ini adalah untuk meyakinkan pembaca bahwa secara iteratif menggunakan pemecah aliran maksimum kotak-hitam untuk menyelesaikan urutan besar MFP dapat menyebabkan sejumlah besar perhitungan yang tidak perlu."

p66 "Dalam aplikasi yang disebutkan di atas, MFP biasanya secara topologi serupa. Yaitu, MFP berikutnya dalam urutan berbeda dari yang sebelumnya dengan menambahkan atau menghapus sejumlah kecil busur atau dengan cara mengubah kapasitas set busur yang dilokalkan. Selain itu , ketika memecahkan contoh ini, waktu dan ruang yang dibutuhkan untuk menyimpan apa pun di luar solusi untuk masalah sebelumnya biasanya tidak beralasan. "

p67 penulis juga menggunakan pendekatan "mulai hangat" di sini. "Strategi yang efektif untuk menyelesaikan secara cepat seluruh rangkaian masalah optimisasi online adalah mengembangkan heuristik reoptimisasi yang efisien. Untuk itu, kami mengembangkan algoritma aliran maksimum yang dimodifikasi yang dirancang untuk pemanasan awal yang efisien." "

lihat esp p71 yang memiliki masalah arc baru tambahan:

Masalah Optimalisasi Aliran Maksimum Bus Baru (NAMFRP)

penulis menganggap masalah yang lebih umum hal

Masalah Optimalisasi Aliran Maksimum (MFROP) Masalah
Maksimalisasi Arc Tunggal Aliran Maksimal (MFSAROP)

dari beberapa pencarian cepat sepertinya versi online adalah area penelitian aktif. Anda tidak menyebutkan area aplikasi yang mungkin membantu mempersempit pencarian literatur. satu pilihan adalah mencari area aplikasi di mana ada inovasi terbaru atau paling. karenanya ada beberapa aplikasi aliran maks tambahan dalam sistem visi & beberapa algoritma untuknya di sana; coba Arus Maksimum dengan Pencarian Pertama yang Luasnya Tambahan di laboratorium riset microsoft. parafrase pengantar untuk makalah ini, tampaknya untuk contoh visi algoritma Boykov dan Kolmogorov bekerja dengan baik & tidak ada contoh tandingan waktu eksponensial yang diketahui meskipun di luar aplikasi penglihatan, kinerjanya buruk. jadi mungkin ada baiknya mencoba algoritma B&K pada data Anda & melihat bagaimana kinerjanya &

Anda tampaknya mengatakan bahwa algoritma inkremental yang linier dalam jumlah tepi grafik tidak cukup? tetapi bukankah itu efisiensi yang cukup tinggi? berapa banyak sisi yang Anda hadapi? mungkin pendekatannya mungkin untuk mengurangi biaya melintasi grafik jika itu mahal atau faktor yang signifikan (misalnya grafik yang disimpan dalam db vs grafik yang disimpan dalam memori)

di sini adalah makalah yang menarik yang berpendapat bahwa sementara algoritma nonincremental untuk aliran max dalam P versi incremental adalah NP lengkap. "Sejauh pengetahuan kami, hasil kami adalah yang pertama menemukan masalah waktu-P yang versi tambahannya adalah NP lengkap."

Aliran tambahan oleh Hartline, Sharp

kemungkinan / arah lain adalah algoritma aliran maksimum push-relabel yang merupakan "salah satu algoritma paling efisien untuk aliran maksimum" dan dapat memiliki profil kompleksitas yang lebih baik tergantung pada data Anda. mis. sebagai status halaman wikipedia

$O(V^3)$$O(V^2 \sqrt E$$O(V \cdot E \cdot log(V^2 / E))$