Yazan : Şadi Evren ŞEKER
Bu algoritmanın amacı, literatürde azami akış ( maximum flow ) olarak geçen ve düğümler (nodes) arasında akış kapasiteleri belirli bir şekildeki (graph) bir başlangıçtan bir hedefe en fazla akışın sağlandığı problemleri çözmektir.
Azami akış (maximum flow) problemini örneğin şehirler arasında bağlı boru hattına veya tedarik zincirine benzetebiliriz. Örneğin aşağıdaki şekli ele alalım:
Buradaki düğümler, şehirleri ve düğümler arasındaki kenarlar (edges) ise şehirler arasındaki boru hatlarının kapasitesini belirtsin. Amacımız A düğümünden E düğüme azami miktarda akış sağlayabilmek olsun.
Ford-Fulkerson çözüm için yukarıdaki şekilde öncelikle hedef düğüme giden yolu bulur. Algoritma bu arama işlemi sırasında şayet derin öncelikli arama (depth first search ,DFS) kullanıyorsa ford fulkerson olarak isimlendirilir. Şayet aynı algoritma bu arama işlemi sırasında sığ öncelikli arama (breadth first search, BFS) kullanırsa bu durumda da edmonds karp algoritması olarak isimlendirilir.
Biz yazımızın konusu olan ford fulkerson algoritmasını anlamak için derin öncelikli olarak arama işlemini gerçekleştirelim:
İlk bulacağımız yol (path) A-D-E olsun bu durumda algoritma bu yol üzerindeki en küçük kapasiteyi bulmaya çalışır:
min(A-D,D-E) = min(5,7) = 5
bu bulunan sayı aslında bu yol üzerinden akabilecek maksimum değerdir. Dolayısıyla bu yoldan 5 kapasitesinde akış yapılmasına karar verilir ve şekil üzerinde bu durum işaretlenir:
Yukarıdaki şekilde buluna kırmızı sayılar, o yoldaki anlık akış miktarlarıdır.
Ardından derin öncelikli arama işlemi devam eder ve örneğin A-C-D-E yolunu bulur.
min(A-C,C-D,D-E) = min(1,1,2) = 1
Yukarıda dikkat edilecek bir nokta, D-E aralığının şeklin ilk halinde olan 7 olarak alınması yerine 2 olarak alınmasıdır. Bunun sebebi şeklin bu kenarındaki 5 miktarındaki kapasitenin şu anda kullanılıyor olması ve artık geriye 2 miktarında kapasite kalmasıdır.
Bir sonraki derin öncelikli arama yolumuz A-C-F-D-E olsun. Bu durumda yol üzerindeki kapasite hesabı aşağıdaki şekilde olacaktır:
min(A-C,C-F,F-D,D-E) = min (0,2,5,7) =0
Görüldüğü üzere bu yol artık kullanılamaz çünkü bu yoldaki kapasite 0’dır. Bunun sebebi bir önceki adımda bulunan yolun, A-C arasındaki kapasiteyi sonuna kadar kullanmış olmasıdır.
Sıradaki yolumuz A-B-F-D olsun:
min(A-B,B-F,F-D) = min( 4,5,5,1) = 1
Son olarak yolumuz A-B-E olarak verilsin :
min(A-B,B-E) = min (3,2) = 2
Yukarıdaki şekilde bütün düğümler arasındaki akışlar gösterilmiştir. Gerçekten de graftaki E düğümüne (hedef düğüme) gidebilen yollar maksimum kapasite ile doldurulmuştur.
Elinize saağlık güzel olmuş ancak:
^^Sıradaki yolumuz A-B-F-D olsun:
min(A-B,B-F,F-D) = min( 4,5,5,1) = 1^^
satırında sanırım D-E ksımı unutulmuş.
evet haklısınız, ilginiz ve uyarınız için teşekkürler, en kısa sürede yazıdaki bu hatayı düzelteceğim.
elinize sağlık, temiz ve anlaşılır bir çalışma.
benim size bir sorum olacak.
bu algoritma bazen maksimum akışı bulamıyor.
ben basitçe modelledim c# ta, ama herzaman maksimum değeri bulamıyor.
http://www.trteknik.com
Ancak kodunuza bakarak yorum yapabilirim.
Merhaba ,
Öncelikle gerçekten çok yararlı bu site için size teşekkür etmek istiyorum.
Sorum su,
Eger bunlar çift yönlü olsaydı ozaman napıcaktık ?
Bir de videolu anlatımlarınız gerçekten çok yararlı oluyor bunlarla ilgili video koyabilirseniz gerçekten kullanabilirlik ve kalite yükselecektir.
Kolay gelsin
İyi çalışmalar
Yazıdaki şekilde (graph) zaten kenarlar (edges) yönsüz (undirected) kabul edilmiş. Bunun anlamı akış işleminin iki yönede olabileceğidir.
Bu durumda sorunuzun cevabı zaten olmuş oluyor sanırım. Ancak şayet yönlü bir şekilden bahsediyorsak. Yani bir boru hattında tek taraftan akışın mümkün olduğu ancak teri taraftan farklı maliyetli olduğu gibi. Bu durumda hesaplamaların değişeceği kesin.
Basitçe bulunan en kısa yol algoritmalarının düzenlenmesi ve yönlü şekiller (directed graph) üzerinde çalışır hale getirilmesi yeterli olurdu.
başarılar
Selam, gerçekten benim için yararlı oldu bilgiler teşekkür ederim. Ancak kafama birşey takıldı 4. grafta yani A-C-F-D-E yolunda neden D-E yi 7 ve 6 olarak belirtiğimiz halde 6 yerine 7 alıyoruz.
bahsettiğiniz grafikte ne 6 ne de 7 alınmamalı. Orada kalan kapasite 1. Yani 7 kapasitesine sahip yolun zaten 6’sı kullanılıyor, geriye 1 kapasite kalır ve 1 olmalıdır.
Yazıda bu kısımı en kısa sürede düzeltirim, ilginiz için teşekkürler.
Ancak bu durum bir soruna sebep olmaz. Sonuçta bahsedilen yolda A-C aralığı dolu. Dolayısıyla bu yolda akış olmayacak.
başarılar
Merhaba,
Yazınız için çok teşekkür ediyorum. Çok güzel açıklamışsınız gerçektende.
Yalnız, min(A-B,B-F,F-D) = min( 4,5,5,1) = 1 kısmında D-E yi yazmamışsınız. Ufak birşey ama öğrenirken takıldım, sonradan eksik yazıldığını farkettim.
Başarılar
haklısınız aslında o satır min(A-B,B-F,F-D,D-E) = min ( 4,5,5,1) olmalıydı, uyarınız için teşekkürler en kısa sürede yazıda düzeltirim.
Bir de min(A-C,C-F,F-D,D-E) = min (0,2,5,7) =0
satırında 7 yerine 1 olması gerekmiyor mu? yani min(0,2,5,1)=0 şeklini kastediyorum.
iyi çalışmalar
Selamlar,
Çok önemli size bir işim düştü.
ben bu algoritmayı omnet++ deuygulamaya çalışıyorum
siz bunu nasıl yapıcam hakkında bana bilgiverebilri misniz ?
tabi bu programı daha önce kullandı iseniz.
Malesef omnetpp konusunda tecrübem yok.
Bu algoritma arama motorları tarafındada kullanılıyor. Peki bu algoritma ile arama motorları ne bulmaya çalışıyor bir fikriniz varmı bu konuda ?
Merhabalar,
Çok açıklayıcı bir yazı olmuş.
Fakat sorce’tan sink’e giderken sıraladığımız pathleri nasıl yazdığımız hiç bir kaçnakta açık değil. Çoğu kaynakta herhangi bir tanesini seçip başlayın diyor ama. Seçtiğimiz kaynağa göre sonuç çok değişebiliyor.
Siz depth first search ile olduğunu yazmışsınız. Bu kısmı biraz daha detaylandırabilir misiniz?