Push-Relabel Algoritması
Push-Relabel Algorithm for Maximum Flow · Ayrıca şöyle bilinir: preflow-push algorithm, Goldberg-Tarjan algorithm
Andrew V. Goldberg ve Robert E. Tarjan tarafından 1988'de geliştirilen Push-Relabel Algoritması, ağlarda maksimum akışı hesaplamak için oldukça verimli bir yöntemdir. Artıran yol yöntemlerinin aksine, bir ön akışı (preflow) korur ve akışı hedefe doğru yönlendirmek için yerel itme (push) ve küresel yeniden etiketleme (relabel) işlemleri kullanır, bu da üstün bir en kötü durum karmaşıklığına ulaşmasını sağlar.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Artıran yol yöntemlerinin verimsiz hale geldiği büyük yoğun ağlarda maksimum akışı hesaplamak için push-relabel algoritmasını uygulayın. Özellikle binlerce veya milyonlarca kenarı olan ağlar için etkilidir. Garantili polinom zaman performansı istediğinizde ve modern veri yapılarından yararlanmak istediğinizde kullanın. Seyrek ağlar veya eğitim amaçlı, artıran yol yöntemleri anlamak ve uygulamak daha basit olabilir.
Güçlü yönler & sınırlılıklar
- Üstün en kötü durum zaman karmaşıklığı: O(V³) veya O(V²√E) (boşluk sezgisi ile)
- Uygulamada oldukça verimli, özellikle büyük ve yoğun ağlar için
- İşlemlerin yerelliği (itme/yeniden etiketleme) iyi önbellek performansı sağlar
- Paralelleştirme ve dağıtık uygulamalara uygun
- Farklı problem yapıları için birden fazla uygulama çeşidi
- Artıran yol yöntemlerinden daha karmaşık anlaşılması ve uygulanması
- Optimal performans için veri yapılarının (boşaltma listeleri, boşluk sezgileri) dikkatli bir şekilde yönetilmesini gerektirir
- En kötü durum karmaşıklığı hala bazı özel graf sınıfları için bazı özel algoritmalardan daha yüksektir
- Artıran yollara kıyasla çözüm sürecinin daha az sezgisel anlaşılması
SSS
Ön akış (preflow) ile akış (flow) arasındaki fark nedir?
Ön akış, düğümlerin geçici olarak fazla akış tutmasına izin verir (giren akış eksi çıkan akış pozitif olabilir), oysa gerçek akış kaynak ve hedef dışındaki tüm düğümlerde korunmalıdır. Algoritma, ön akış geçerli bir akış haline geldiğinde sonlanır.
Yükseklik fonksiyonunun amacı nedir?
Yükseklikler yarı-mesafe ölçüsü oluşturur: akış yalnızca yokuş aşağı (daha yüksekten daha düşüğe) itilebilir, gereksiz döngüleri önler ve sonlanmayı sağlar. Gerektiğinde yeni yollar oluşturmak için yeniden etiketleme yoluyla yükseklikler artırılır.
Boşluk sezgisi (gap heuristic) nedir ve neden önemlidir?
Boşluk sezgisi, belirli bir yükseklik aralığında hiçbir düğümün olmadığı zamanı tespit eder, bu da bazı düğümlerin hedefe ulaşamayacağını gösterir. Bu düğümler ve fazlalıkları hızla belirlenir ve işlenir, bu da pratik performansı önemli ölçüde artırır.
Pratikte push-relabel, Edmonds-Karp ile nasıl karşılaştırılır?
Push-relabel, daha iyi en kötü durum karmaşıklığına sahiptir ve genellikle büyük ağlarda Edmonds-Karp'tan daha iyi performans gösterir, ancak küçük ağlar veya seyrek graflar için Edmonds-Karp, rekabetçi performansla uygulaması daha basit olabilir.
Kaynaklar
- Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940. DOI: 10.1145/48014.61051 ↗
- Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin. link ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Push-Relabel Algorithm for Maximum Flow. ScholarGate. https://scholargate.app/tr/operations-research/push-relabel-algorithm
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Bellman-Ford AlgoritmasıYöneylem araştırması↔ karşılaştır
- Dijkstra AlgoritmasıYöneylem araştırması↔ karşılaştır
- Ford-Fulkerson AlgoritmasıYöneylem araştırması↔ karşılaştır