Algoritma Push-Relabel
- Diperkenalkan oleh
- Andrew V. Goldberg and Robert E. Tarjan
- Tahun
- 1988
- Jenis
- algorithm
- Keluarga
- Graph Algorithms
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Algoritma Push-Relabel, yang dikembangkan oleh Andrew V. Goldberg dan Robert E. Tarjan pada tahun 1988, adalah metode yang sangat efisien untuk menghitung aliran maksimum dalam jaringan.
Berbeda dengan metode jalur penambah (augmenting path), algoritma ini mempertahankan pra-aliran (preflow) dan menggunakan operasi dorong lokal (push) serta pelabelan ulang global (relabel) untuk menggerakkan aliran menuju sink, sehingga mencapai kompleksitas kasus terburuk yang superior.
Intuisi di balik metode
Algoritma ini mempertahankan 'tinggi' atau 'label jarak' untuk setiap simpul dan menggunakan pra-aliran (di mana simpul dapat sementara melebihi permintaan sink). Algoritma ini berulang kali mendorong kelebihan aliran dari simpul berlabel lebih tinggi ke tetangga berlabel lebih rendah dan memberi label ulang simpul untuk menciptakan jalur ke sink. Wawasan kuncinya adalah dengan mempertahankan invarian tinggi dan menggunakan struktur data yang efisien, algoritma ini menghindari penjelajahan seluruh graf berulang kali, seperti yang harus dilakukan oleh metode jalur penambah. Algoritma berakhir ketika semua kelebihan aliran mencapai sink.
Sejarah
Goldberg dan Tarjan menerbitkan algoritma push-relabel mereka pada tahun 1988, memperkenalkan paradigma yang secara fundamental berbeda untuk komputasi aliran maksimum. Algoritma mereka mencapai kompleksitas kasus terburuk O(V³), sebuah peningkatan dibandingkan O(VE²) dari Edmonds-Karp. Selama dekade berikutnya, banyak varian telah dikembangkan, termasuk heuristik celah (Goldberg dan Tarjan, 1990), aturan label tertinggi (highest-label rules), dan varian terbaru yang mencapai kinerja empiris mendekati linier pada jaringan dunia nyata.
Kapan digunakan
Terapkan algoritma push-relabel untuk menghitung aliran maksimum dalam jaringan padat berskala besar di mana metode jalur penambah menjadi tidak efisien. Algoritma ini sangat efektif untuk jaringan dengan ribuan atau jutaan sisi. Gunakan ketika Anda membutuhkan kinerja waktu polinomial yang terjamin dan ingin memanfaatkan struktur data modern. Untuk jaringan jarang atau tujuan pendidikan, metode jalur penambah mungkin lebih mudah dipahami dan diimplementasikan.
Batasan dan pertimbangan
- Lebih kompleks untuk dipahami dan diimplementasikan daripada metode jalur penambah
- Memerlukan penanganan struktur data yang cermat (daftar pengosongan, heuristik celah) untuk kinerja optimal
- Kompleksitas kasus terburuk masih lebih tinggi daripada beberapa algoritma khusus untuk kelas graf tertentu
- Pemahaman proses solusi yang kurang intuitif dibandingkan dengan jalur penambah
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Kompleksitas waktu kasus terburuk yang superior: O(V³) atau O(V²√E) dengan heuristik celah (gap heuristic)
- Sangat efisien dalam praktik, terutama untuk jaringan besar dan padat
- Lokalitas operasi (dorong/pelabelan ulang) memungkinkan kinerja cache yang baik
- Dapat disesuaikan untuk implementasi paralel dan terdistribusi
- Berbagai varian implementasi untuk struktur masalah yang berbeda
Penerapan
- Perutean jaringan: menghitung throughput maksimum dalam jaringan komunikasi berskala besar
- Pemrosesan gambar: menggunakan max-flow untuk segmentasi gambar dan aplikasi matting
- Optimasi maskapai: menentukan aliran penumpang maksimum melalui jaringan rute yang kompleks
- Analisis jaringan listrik: menghitung kapasitas transmisi daya maksimum dalam jaringan listrik
- Manajemen rantai pasokan: mengoptimalkan aliran produk melalui jaringan distribusi multi-tingkat
- Jaringan biologis: menganalisis aliran maksimum dalam jaringan metabolisme dan interaksi protein
Cara kerjanya
Cara kerjanya
Tetapkan tinggi sumber ke jumlah simpul, semua tinggi lainnya ke nol. Jenuhkan semua sisi yang keluar dari sumber, ciptakan pra-aliran awal (kelebihan pada simpul tetangga).
Berulang kali pilih simpul aktif (dengan kelebihan aliran) dan dorong kelebihan ke tetangga ber-tinggi lebih rendah atau beri label ulang simpul untuk meningkatkan tingginya. Gunakan strategi pemilihan dan operasi pengosongan (discharge) yang efisien untuk meminimalkan iterasi.
Lanjutkan hingga tidak ada simpul aktif yang tersisa, pada saat itu semua pra-aliran telah diselesaikan menjadi aliran maksimum dari sumber ke sink.
Kesalahan umum
- Implementasi pembaruan tinggi atau operasi dorong yang salah yang mengarah pada aliran yang tidak maksimum
- Mengabaikan penggunaan heuristik celah dan pemilihan simpul yang efisien, menghasilkan kinerja praktis yang buruk
- Gagal mempertahankan invarian pra-aliran dengan benar (kelebihan pada simpul dan batasan kapasitas pada sisi)
Pertanyaan yang sering diajukan
Apa perbedaan antara pra-aliran dan aliran?
Pra-aliran sementara memungkinkan simpul menahan kelebihan aliran (aliran masuk dikurangi aliran keluar bisa positif), sedangkan aliran sejati harus dihemat di semua simpul kecuali sumber dan sink. Algoritma berakhir ketika pra-aliran menjadi aliran yang valid.
Apa tujuan fungsi tinggi?
Tinggi menciptakan ukuran kuasi-jarak: aliran hanya dapat didorong ke bawah (dari tinggi ke rendah), mencegah siklus yang tidak perlu dan memastikan penghentian. Tinggi ditingkatkan melalui pelabelan ulang untuk menciptakan jalur baru bila diperlukan.
Apa itu heuristik celah dan mengapa itu penting?
Heuristik celah mendeteksi ketika tidak ada simpul yang memiliki tinggi dalam rentang tertentu, menunjukkan bahwa beberapa simpul tidak dapat mencapai sink. Simpul-simpul ini dan kelebihannya dengan cepat diidentifikasi dan diproses, secara signifikan meningkatkan kinerja praktis.
Bagaimana perbandingan push-relabel dalam praktik dengan Edmonds-Karp?
Push-relabel memiliki kompleksitas kasus terburuk yang lebih baik dan biasanya mengungguli Edmonds-Karp pada jaringan besar, tetapi untuk jaringan kecil atau graf jarang, Edmonds-Karp mungkin lebih mudah diimplementasikan dengan kinerja yang kompetitif.
Metode terkait
Sumber
Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.
Buka referensi DOIDisalin.Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.
Buka referensi publikasiDisalin.