Apakah ada yang mutakhir algoritma Aliran Maksimal praktis?

30

Untuk masalah aliran maksimum , tampaknya ada sejumlah algoritma yang sangat canggih, dengan setidaknya satu dikembangkan baru-baru ini tahun lalu. Max Orlin mengalir dalam waktu O (mn) atau lebih baik memberikan algoritma yang berjalan dalam O (VE).

Di sisi lain, algoritma yang paling sering saya lihat diimplementasikan adalah (Saya tidak mengklaim telah melakukan pencarian lengkap; ini hanya dari pengamatan biasa):

  • Edmonds-Karp: O(VE2) ,
  • Push-relabel: O(V2E) atau menggunakan pilihan vertex FIFO,O(V3)
  • Algoritma Dinic: .O(V2E)

Apakah algoritma dengan waktu berjalan asimptotik yang lebih baik tidak praktis untuk ukuran masalah di dunia nyata? Juga, saya melihat "Dynamic Trees" terlibat dalam beberapa algoritma; apakah ini pernah digunakan dalam praktek?

Catatan: pertanyaan ini awalnya ditanyakan pada stack overflow, di sini , tapi saya diberitahu akan lebih cocok di sini.

EDIT : Saya mengajukan pertanyaan terkait pada cs.stackexchange , khususnya tentang algoritme yang menggunakan pohon dinamis (alias pohon potongan tautan), yang mungkin menarik bagi orang yang mengikuti pertanyaan ini.

ds.algorithms graph-algorithms application-of-theory max-flow Rob Lachlan
sumber
1
berbicara dalam pengertian umum, apakah suatu algoritma "praktis" vs apakah itu "diterapkan" agak berbeda. idealnya penulis akan merilis implementasi algoritma mereka sendiri dalam hal ini biasanya akan "praktis" untuk menggunakannya. unf, ini lebih merupakan pengecualian dalam literatur TCS. tetapi seringkali tidak "praktis" untuk "mengimplementasikan" algoritma penulis lain hanya memberikan deskripsi dalam makalah yang ditulis dalam pseudocode, yang kadang-kadang secara signifikan atau sangat kompleks ... implementasi yang sukses mencakup pengujian yang baik untuk kebenaran, proses yang kadang-kadang menakutkan ...
vzn
3
Andrew Goldberg dulunya memiliki basis kode yang sangat bagus untuk berbagai varian aliran maks berdasarkan kerja push relabel-nya. Saya telah menggunakan kode di masa lalu, dan itu sangat bersih. Sayangnya, situs tersebut tampaknya tidak berfungsi.
Suresh Venkat
3
@ vzn Saya tertarik pada apakah algoritma cocok untuk implementasi praktis sama sekali. Ada algoritma yang tidak, dan beberapa orang telah memanggil ini "algoritma galaksi", karena mereka memiliki perilaku asimtotik yang sangat baik tetapi begitu banyak overhead sehingga saat ini tidak ada keuntungan praktis untuk mengimplementasikannya. (Bagaimanapun juga, istilah urutan yang lebih rendah). Penggandaan matriks adalah contoh terbaik yang dapat saya pikirkan, di mana solusi asimptotik terbaik tidak pernah melihat penggunaan praktis. Saya ingin tahu apakah aliran Max adalah situasi yang sama.
Rob Lachlan
5
apakah suatu algoritma "praktis" vs apakah itu "diterapkan" agak berbeda. - Itu betul. Algoritma dapat diimplementasikan tanpa praktis, tetapi tidak sebaliknya.
Jeffε
2
Berikut kode dari studi Eksperimental algoritma pemotongan minimum .
Austin Buchanan

Jawaban:

22

Saya adalah salah satu penulis makalah yang ditautkan di atas.

Hanya ingin menyebutkan bahwa kami menggunakan `` state-of-the-art '' untuk mengartikan algoritme (dengan implementasi yang tersedia untuk umum) yang berkinerja baik pada instance aliran-max yang muncul dalam visi komputer.

Saya juga ingin menambahkan bahwa dalam konteks yang sempit (namun praktis), seringkali algoritma yang berkinerja baik adalah yang dengan jaminan teoritis yang buruk. Misalnya, ref [5] dari makalah kami (algoritma Boykov-Kolmogorov) banyak digunakan dalam komunitas visi komputer, tetapi tidak memiliki batas runtime polytime yang kuat.

Akhirnya, jika ada yang tertarik, data dari eksperimen kami tersedia di sini: http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

Kode juga akan segera tersedia.

Dhruv Batra
sumber
sangat rapi bahwa Anda bergabung dengan grup! Selamat datang! satu pertanyaan tentang kertas [sejak 1 menemukannya]. akan sangat menarik untuk mendengar lebih banyak tentang proses pemilihan algoritma yang digunakan dalam makalah ini — sepertinya tidak sepenuhnya menguraikan hal itu. mungkin Anda dapat berbagi beberapa catatan latar belakang "di belakang layar" di suatu tempat [misalnya halaman web?] tentang algoritma mana yang dipilih, yang dihilangkan, mengapa, tantangan apa yang ada dalam mendapatkan / menjalankan implementasi, apa yang Anda pikirkan tentang eksotik yang lebih algoritma seperti Orlins yang terbaru & prospek mereka untuk implementasi akhirnya, dan sebagainya!
vzn
7

ada beberapa cara untuk menjawab pertanyaan ini tetapi belum tentu jawaban konsensus. umumnya algoritma yang telah diterapkan dan dirilis untuk distribusi publik adalah "praktis". namun, beberapa algoritme yang telah dirancang tetapi belum diimplementasikan mungkin praktis tetapi "juri sudah keluar" untuk berbicara. **

strategi yang baik untuk tujuan praktis adalah mencari survei. juga bagi mereka yang tertarik pada algoritma praktis, tolok ukur terhadap data dunia nyata dapat menjadi pedoman yang sangat baik untuk perilaku "dunia nyata" yang mereka harapkan.

survei pembandingan bisa mencukupi tetapi akan keliru di sisi algoritma yang layak. ini adalah, analisis empiris baru-baru ini menyeluruh dari 14 algoritma aliran "state-of-the-art" yang diperbandingkan secara empiris versus contoh pemrosesan penglihatan, di mana aliran max memiliki banyak aplikasi. "state of the art" diambil untuk merujuk ke algoritma "diimplementasikan".

[1] MaxFlow Revisited: Perbandingan Empiris Algoritma Maxflow untuk Masalah Penglihatan Padat oleh Verma dan Batra, 2012

** beberapa algoritma teoretis berada dalam kategori yang semakin meningkat di komunitas TCS yang secara informal disebut sebagai "galactic" tetapi sayangnya, penulis TCS saat ini tidak secara langsung melabeli algoritma mereka sendiri dalam kategori ini, dan tidak ada kriteria yang dipublikasikan atau diterima secara umum untuk Algoritma "galactic", meskipun ada referensi di blog .

kepraktisan dalam pengertian ini mungkin merupakan dimensi baru yang muncul untuk studi teoritis. idealnya akan ada survei algoritma aliran maks khusus pada sumbu / kriteria "praktis" ini, tetapi kemungkinan itu tidak ada pada saat penulisan. ini adalah konsep yang lebih baru diakui / diakui dalam TCS yang belum diformalkan secara menyeluruh (tidak seperti misalnya penerimaan luas algoritma P sebagai "efisien").

ay
sumber
3
+1. Saya tidak yakin mengapa ini diturunkan; Saya membaca makalah yang Anda tautkan, dan sangat membantu dalam melihat apa pendekatan praktisnya, setidaknya dalam domain masalah itu.
Rob Lachlan
3
Robert Sedgewick mengatakan dalam sebuah pembicaraan yang cukup baru bahwa perancang algoritma yang tidak menjalankan eksperimen berisiko hilang dalam abstraksi. Pembicaraannya adalah tentang menemukan jalur dalam grafik, dan agak terkait dengan maxflow juga. Itu tidak menjawab pertanyaan, tetapi mungkin menarik bagi seseorang.
Juho
5
@Rob, satu-satunya bagian yang relevan dalam jawaban ini adalah tautan ke kertas dan tidak ada banyak jawaban yang menjelaskan mengapa kertas itu terhubung sama sekali. Saya kira OP menemukan tautannya oleh Google dan belum membacanya. Sisa dari jawabannya adalah beberapa komentar dan komentar umum yang menyatakan perspektif pribadi OP tentang isu-isu bahwa ia bukan ahli dan tidak benar-benar relevan di sini. Jawabannya bukan posting blog. Tautan ke makalah yang relevan mungkin baik sebagai komentar tetapi tidak memberikan jawaban. Ini adalah jawaban yang buruk jika itu salah. Itu sebabnya saya memilihnya.
Kaveh
2
@ Kaveh cukup adil. Saya menemukan kertas menjadi indikator yang berguna dari apa yang orang anggap sebagai algoritma yang praktis berguna. Saya setuju bahwa banyak yang tidak terjawab.
Rob Lachlan
3
Saya juga tidak mengerti downvotes. Tidak ada alasan untuk percaya bahwa poster TIDAK membaca artikel yang ditautkan, dan itu tampaknya relevan. Saya bisa melihat keinginan untuk tidak menang, tetapi bukan downvote.
Suresh Venkat