Kita tahu bahwa menghitung aliran arus maksimum. potongan minimum jaringan dengan kapasitas setara; lih. yang max-flow min-cut teorema .
Kami memiliki (kurang lebih efisien) algoritma untuk menghitung aliran maksimum, dan menghitung potongan minimum mengingat aliran maksimum juga tidak sulit atau mahal.
Tapi bagaimana dengan yang sebaliknya? Diberikan potongan minimum, bagaimana kita bisa menentukan aliran maksimum? Tanpa menyelesaikan Max-Flow dari awal, tentu saja, dan lebih baik lebih cepat dari itu juga.
Beberapa pemikiran:
Dari potongan minimum, kita tahu nilai aliran maksimum. Saya tidak melihat bagaimana informasi ini membantu pendekatan standar menambah jalur dan push-relabel, meskipun mengadaptasi yang terakhir tampaknya sedikit lebih masuk akal.
Kami tidak dapat menggunakan potongan minimum untuk membagi jaringan menjadi dua bagian dan berulang karena itu tidak akan mengecilkan masalah dalam kasus terburuk (jika satu partisi adalah singleton); juga kami tidak akan memiliki potongan minimum dari contoh yang lebih kecil.
Apakah mengetahui nilai aliran maksimum mempercepat penyelesaian Max-Flow LP, mungkin melalui kondisi kelonggaran yang saling melengkapi?
sumber
Jawaban:
Dalam kasus terburuk, pemotongan minimum itu sendiri tidak menyampaikan banyak informasi tentang aliran maksimum. Pertimbangkan grafik dimana minimum s , t -cut memiliki nilai w . Jika saya memperpanjang G dengan menambahkan simpul baru s ′ dan tepi ( s ′ , s ) dengan bobot w , minimum s ′ , t- potong dalam grafik baru hanya terdiri dari tepi ( s ′ , s )G = ( V, E) s , t w G s′ ( s′, s ) w s′, t ( s′, s ) tapi itu tidak memberikan informasi apa pun tentang cara mendapatkan unit aliran dari s ke tw s t .
Secara efektif, potongan minimum memberi tahu Anda nilai aliran, tetapi tidak bagaimana mencapai aliran itu. Ini berarti mengetahui pemotongan minimum dapat mempercepat menemukan aliran paling banyak oleh faktor logaritmik, karena kita bisa melakukan pencarian biner untuk menemukan nilai pemotongan.
sumber
Tentu saja ada algoritma yang memungkinkan Anda menghitung potongan min sebelum menghitung maxflow. Dua algoritma tersebut adalah push relabel dan algoritma pseudoflow yang terkait erat. Yang terakhir lebih efisien. Kedua algoritma ini menggunakan properti khusus dari grafik residual yang secara iteratif mereka tingkatkan untuk mendapatkan aliran maksimum dari potongan minimum. Untuk lebih jelasnya saya sangat merekomendasikan membaca kode dan makalah.
Untuk menguraikan kasus relabel push, ketika algoritma dapat mendorong tidak ada lagi aliran ke wastafel itu dijamin telah menghitung potongan min. Bagian dari algoritma ini disebut fase 1 karena kurangnya nama yang lebih baik. Fase 2 adalah tahap yang lebih efisien di mana ia mengubah potongan min menjadi maxflow dengan membatalkan siklus berulang dalam grafik residu menggunakan pencarian pertama kedalaman tunggal dan mendorong kelebihan kembali ke sumber. Saya percaya fase 2 dapat dibuktikan secara asimptomatik lebih efisien daripada fase 1.
sumber