Push-Relabel Algoritması
- Ortaya koyan
- Andrew V. Goldberg and Robert E. Tarjan
- Yıl
- 1988
- Tür
- algorithm
- Aile
- Graph Algorithms
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
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.
Yöntemin mantığı
Algoritma, her düğüm için bir 'yükseklik' veya 'mesafe etiketi' tutar ve ön akışı (düğümlerin geçici olarak hedef talebini aşabileceği durum) kullanır. Aşırı akışı tekrarlı olarak daha yüksek etiketli düğümlerden daha düşük etiketli komşularına iter ve hedefe giden yolları oluşturmak için düğümleri yeniden etiketler. Temel fikir, yükseklik değişmezlerini koruyarak ve verimli veri yapıları kullanarak, algoritmanın artıran yol yöntemlerinin yapmak zorunda olduğu gibi tüm grafiği tekrar tekrar keşfetmekten kaçınmasıdır. Algoritma, tüm ön akış hedefe ulaştığında sonlanır.
Tarih
Goldberg ve Tarjan, 1988'de push-relabel algoritmalarını yayınlayarak maksimum akış hesaplaması için temelde farklı bir paradigma tanıttılar. Algoritmaları, Edmonds-Karp'ın O(VE²) karmaşıklığına göre bir iyileştirme olan O(V³) en kötü durum karmaşıklığına ulaştı. Sonraki on yıllar boyunca, boşluk sezgileri (Goldberg ve Tarjan, 1990), en yüksek etiket kuralları ve gerçek dünya ağlarında doğrusal yakın performans elde eden en son varyantlar dahil olmak üzere çok sayıda varyant geliştirildi.
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.
Sınırlar ve dikkat edilmesi gerekenler
- 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ı
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Ü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
Uygulama alanları
- Ağ yönlendirme: büyük ölçekli iletişim ağlarında maksimum verim hesaplama
- Görüntü işleme: görüntü segmentasyonu ve matting uygulamaları için maksimum akış kullanma
- Havayolu optimizasyonu: karmaşık yönlendirme ağları üzerinden maksimum yolcu akışını belirleme
- Güç şebekesi analizi: elektrik ağlarında maksimum güç iletim kapasitesini hesaplama
- Tedarik zinciri yönetimi: çok katmanlı dağıtım ağları üzerinden ürün akışını optimize etme
- Biyolojik ağlar: metabolik ve protein etkileşim ağlarında maksimum akışı analiz etme
Nasıl çalışır?
Nasıl çalışır?
Kaynağın yüksekliğini köşe sayısına, diğer tüm yükseklikleri sıfıra ayarlayın. Kaynaktan çıkan tüm kenarları doyurun, komşu düğümlerde ön akış (fazlalık) oluşturun.
Aşırı akışı olan aktif bir düğümü tekrarlı olarak seçin ve ya aşırılığı daha düşük yüksekliklikli bir komşuya itin ya da düğümü yüksekliğini artırmak için yeniden etiketleyin. İterasyonları en aza indirmek için verimli seçim stratejileri ve boşaltma (discharge) işlemleri kullanın.
Aktif düğüm kalmayana kadar devam edin, bu noktada tüm ön akış kaynaktan hedefe maksimum akışa dönüşmüş olur.
Sık yapılan hatalar
- Yükseklik güncellemelerinin veya itme işlemlerinin yanlış uygulanması, maksimum olmayan akışlara yol açar
- Boşluk sezgilerini ve verimli düğüm seçimini ihmal etmek, kötü pratik performansa neden olur
- Ön akış değişmezini (düğümlerdeki fazlalık ve kenarlardaki kapasite kısıtlamaları) doğru bir şekilde koruyamamak
Sık sorulan sorular
Ö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.
İlgili yöntemler
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 kaynağını açKopyalandı.Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.
Yayın kaynağını açKopyalandı.