Ford-Fulkerson Algoritması
- Ortaya koyan
- Lester R. Ford and Delbert R. Fulkerson
- Yıl
- 1956
- Tür
- algorithm
- Aile
- Graph Algorithms
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Lester R. Ford ve Delbert R. Fulkerson tarafından 1956'da geliştirilen Ford-Fulkerson Algoritması, bir akış ağındaki maksimum akışı hesaplamak için temel bir yöntemdir.
Kapasite kısıtlamalarına sahip yönlü bir graf üzerinden bir kaynaktan bir hedefe gönderilebilecek maksimum akış miktarını bulur.
Yöntemin mantığı
Algoritma, her kenarın kalan kapasiteye sahip olduğu artık ağda kaynaktan hedefe artırıcı yolları tekrarlı olarak bularak çalışır. Her yol, darboğaz kapasitesine (yoldaki minimum kalan kapasiteye sahip kenar) eşit ek bir akış katkıda bulunur. Süreç, artık artırıcı yollar bulunamayana kadar devam eder; bu noktada maksimum akışa ulaşılır. Temel içgörü, maksimum akış-minimum kesim teoremidir: maksimum akış, ağdaki minimum kesim kapasitesine eşittir.
Tarih
Ford ve Fulkerson, maksimum akış problemini ve seminal algoritmalarını 1956'da tanıttı. Çalışma devrim niteliğindeydi, hem algoritmik bir yöntem hem de ünlü maksimum akış-minimum kesim teoremini kurdu. Edmonds ve Karp (1972), yol seçimi için genişlik öncelikli arama kullanarak en kötü durum karmaşıklığını iyileştirdi. Dinic, Karzanov ve diğerlerinin sonraki gelişmeleri daha da hızlı algoritmalara yol açtı, ancak Ford-Fulkerson yöntemi bilgisayar biliminde klasik ve pedagojik olarak değerli bir algoritma olmaya devam ediyor.
Ne zaman kullanılır?
Yönlü veya yönsüz akış ağlarında pozitif tamsayı kapasiteleri ile maksimum akışı bulmak için Ford-Fulkerson algoritmasını uygulayın. Küçük ve orta ölçekli ağlar için iyi çalışır ve ağ akışı kavramlarının sezgisel anlaşılmasını sağlar. Çok büyük ağlar için veya tamsayı akışlarının gerekli olduğu durumlarda, daha iyi en kötü durum performansı için Edmonds-Karp (BFS kullanarak) veya Dinic algoritmasını düşünün. Algoritma davranışını anlamanın hız kadar önemli olduğu durumlarda kullanın.
Sınırlar ve dikkat edilmesi gerekenler
- Zaman karmaşıklığı kapasite değerlerine bağlıdır (genel olarak polinom değil; irrasyonel kapasitelerle üssel olabilir)
- Kapasiteler irrasyonel ise sonlanmayabilir (rasyonel aritmetik ile dikkatli uygulama gerektirir)
- Büyük ağlarda Edmonds-Karp veya Dinic gibi özel algoritmalardan daha az verimli
- Artırıcı yol seçim sırasına duyarlı
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Artırıcı yollara dayanan basit ve sezgisel yaklaşım
- Kapasiteler rasyonel veya tamsayı olduğunda optimal çözüm garantisi
- Küçük tamsayı kapasiteli ağlar için verimli
- Maksimum akış-minimum kesim ikiliğini anlamak için teorik temeli oluşturur
- Hem yönlü hem de yönsüz graflarla çalışır
Uygulama alanları
- Ağ yönlendirme: iletişim ağlarında kaynaktan hedefe veri verimini en üst düzeye çıkarma
- Taşımacılık ağları: yol ve demiryolu kısıtlamalarını göz önünde bulundurarak şehirler arasındaki maksimum kargo kapasitesini belirleme
- İkili eşleştirme: akış ağları oluşturarak ikili graflarda maksimum eşleştirmeleri bulma
- Görüntü bölütleme: görüntüleri ön plan ve arka plana ayırmak için maksimum akış algoritmalarını kullanma
- Havayolu planlaması: merkez ve konuşma ağları aracılığıyla yolcu akışını en üst düzeye çıkarmak için uçak rotalarını optimize etme
- Protein analizi: etkileşim yollarını anlamak için biyolojik ağlarda maksimum akışı hesaplama
Nasıl çalışır?
Nasıl çalışır?
Artık ağı, orijinal kenar kapasitelerine eşit kapasiteler ve tüm kenarlarda sıfır akış ile başlatın.
Derinlik öncelikli veya genişlik öncelikli arama kullanarak artık ağda kaynaktan hedefe bir artırıcı yol bulun, yol boyunca minimum kapasiteyi hesaplayın ve bu akışı yoldaki tüm kenarlara ekleyerek artık kapasitelerini azaltın.
Artık ağda artırıcı yol kalmayana kadar tekrarlayın; toplam birikmiş akış maksimum akıştır.
Sık yapılan hatalar
- Yavaş yakınsamaya veya yanlış sonuçlara yol açan kötü artırıcı yolların seçilmesi
- Artık kapasiteleri doğru şekilde güncellemeyi veya akışı geri almak için ters kenarlar eklemeyi başaramama
- Doğruluk için kesin aritmetiğin gerekli olduğu durumlarda tamsayı bölmesi veya kayan nokta aritmetiği kullanma
Sık sorulan sorular
Maksimum akış-minimum kesim teoremi nedir?
Teorem, kaynaktan hedefe olan maksimum akışın, kaynaktan hedefe ayıran herhangi bir kesimin minimum kapasitesine eşit olduğunu belirtir. Bu, hem teorik bir içgörü hem de akış algoritmaları için bir doğrulama yöntemi sağlar.
Algoritma neden bazen yavaş yakınsar?
Talihsiz yol seçimleriyle, algoritma daha büyük artışlar mümkünken bile iterasyon başına yalnızca bir birim akış artırabilir. Genişlik öncelikli arama (Edmonds-Karp) kullanmak polinom zamanlı yakınsamayı garanti eder.
Algoritma yönsüz kenarları nasıl ele alır?
Her yönsüz kenarı, her ikisi de aynı kapasiteye sahip iki yönlü kenarla değiştirin. Algoritma daha sonra yönlü ağda akışı bulur.
Bir kenardaki akış ile artık kapasite arasındaki fark nedir?
Bir kenardaki akış, boyunca gönderilen malzeme miktarını temsil ederken, artık kapasite mevcut kalan kapasitedir. Akış arttıkça artık kapasite azalır ve ters kenarlar akışı geri alma yeteneğini izler.
İlgili yöntemler
Kaynaklar
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
DOI kaynağını açKopyalandı.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8Kopyalandı.