Algoritma analizi konusunda geçen meşhur problemlerden eşleşme problemini çözmek için (matching problem, bazı kaynaklarda atama problemi (assignment problem) olarak da geçmektedir) macar araştırmacıların etkisi ile gelişen algoritmanın ismidir.

Algoritmanın ulaşmak istediği amaç, azami eşleşmeye ulaşmaktır. Bu adımda azami eşeleşmeyi tanımlayalım. Eşleşme problemleri (matching) iki grup altında incelenebilir:

  • ikili eşleşme (binary matching)

  • Azami eşleşme (maximum matching)

ilk gruptaki problemlerde iki üyenin eşleşmesi yeterlidir. Örneğin evlilik problemi gibi, en fazla kişinin evlendiği eşleşmeler veya bir arz / talep eşleşmesi gibi. Örneğin nehri geçmek isteyen kişilerin sallara atanması gibi en az kişinin açıkta kaldığı en fazla kişinin eşleştiği problemlerdir.

İkinci grup olan azami eşeleşme (maximum matching) problemleri ise bu yazının da konusu olan macar algoritması tarafından çözülmesi hedeflenen ve klasik eşleşmenin ötesinde, her eşleşmenin değer sahibi olduğu problemlerdir. Örneğin kişilerin iş bulması ama her işin ve kişinin farklı maaşlar alması halinde azami maaş (maximum maaş) değerine ulaşmak gibi. Yani sadece eşlemek yetmiyor bir de her eşlemeye bir skor verip bu değerin en fazla olmasını istiyoruz. Bu problemin tersten okunuşu ise asgari maliyettir. Yani aynı problemi bir şirket yöneticisi ele aldığında örneğin çalışanlarına en az maliyetle iş yaptırmak isteyecektir.

Problem ve macar algoritması (hungarian algorithm) daha iyi anlaşılsın diye bir örnek üzerinden anlatmaya çalışalım. Örneğin elimizde N adet çalışan ve N adet iş olsun ve her kişinin her işe atanması durumunda alacağı maaşları bir masfufta (matrix) göstermeye çalışalım:

 

  İşler
Çalışanlar   A B C
S 5 2 3
Ş 6 1 4
T 4 4 6

 

Yukarıdaki masfufta görüldüğü üzere 4 adet iş ve bu 4 iş için 4 adet çalışan atanmış, her hücrede ise ilgili çalışanın ilgili iş için alacağı ücret gösterilmiştir. Örneğin Ş çalışanının C işini yapması halinde 4 lira alacağını anlıyoruz.

Artık problem daha rahat anlaşılabilir. Amacımız yukarıdaki ücret değerlerine göre en düşük maaşlı işe atama olacaktır.

Problem masfuf olarak gösterilebileceği gibi bir şekil (graph) olarak da tasviri mümkündür:

Problem daha iyi anlaşılsın diye örnek bir çözümü ele alalım:

Yukarıdaki eşleşmede A-S , B-T ve C-Ş ataması yapılmıştır. Bunun maliyeti 5+4+4 = 13 olarak hesaplanabilir.

Elbette bu çözüm ihtimal havuzundakilerden sadece bir tanesidir. Basit bir olasılık hesabı ile 3×3 boyutundaki bir masfuf için 3! ihtimal olduğu görülebilir. Örneğin A için 3 ihtimal B için kalan 2 ihtimal ve C için tek ihtimal bulunmaktadır. Aynı şekilde nxn boyutundaki bir eşleşme (matching) problemi için de n! ihtimal bulunacaktır.

Klasik bir algoritma kodlanması durumunda n! ihtimalin incelenmesi gerekeceğinden problemi np-zor (np-hard) olarak görebiliriz. Ancak macar algoritması bu problemi çok terimli zamana (polinom, polynomial) indirgeyebilmektedir. Bu anlamda problem np-tam (np-complete) olarak görülebilir.

Gelelim problemin çözümüne. Problem, yukarıdaki şekilden den görüleceği gibi iki parçalı grafiğin (bipartite graph) doğru oluşturulması ile çözülebilmektedir.

Algoritma 3 adımdan oluşmaktadır.

  1. adımda 0-ağırlıkta kenarlar oluşturuyoruz (0-weighted edges) bunun için işler kısmında bakarak en düşük değerdeki kenarın ağırlığını diğer kenarlardan çıkarıyoruz ve benzer şekilde kişiler tarafından bakıp en düşük değerdeki kenarın ağırlığını diğer kenarlardan çıkarıyoruz.

    Bu aşama aslında problemin yapısını değiştirmemektedir. Örnek problemimize bu adımı uygulayarak durumu görelim:

 

  İşler
Çalışanlar   A B C
S 5-4 2-1 3-3
Ş 6-4 1-1 4-3
T 4-4 4-1 6-3

Yukarıdaki masfufta görüldüğü üzere A için en düşük değer olan 4, B için en düşük değer olan 1 ve C için en düşük değer olan 3 bütün değerlerden çıkarılmış ve aşağıdaki masfuf elde edilmiştir:

 

  İşler
Çalışanlar   A B C
S 1 1 0
Ş 2 0 1
T 0 3 3

Şimdi çalışanlar açısından olaya bakıp en düşük değerleri çıkaralım:

  İşler
Çalışanlar   A B C
S 1 1 0
Ş 2 0 1
T 0 3 3

Masfufta bir değişiklik olmadı çünkü her çalışan için en düşük değer 0 idi. Ancak bu durum farklı örneklerde değişebilir. Şayet çalışanların ücretlerinde 0’dan büyük değer bulunursa bu değerlerin en küçüğü satır bazlı olarak bütün satırdan çıkarılacaktır.

Daha iyi anlaşılması için yukarıdaki masfufun şekil halini aşağıda verelim:

  1. Yukarıdaki yeni şekilde 0-ağırlığındaki düğümleri kullanarak eşleme yapıyoruz. Bu adımda azami akış (max-flow) veya dalgalı yol bulma (augmented path) algoritmaları gibi algoritmalardan istifade edebiliriz.

    Eşleşme sonucu şayet mükemmel eşleşme ise (perfect matching) problem çözülmüştür. Şayet mükemmel eşleşme sağlanamazsa, sadece 0-ağırlığındaki kenarları kullanarak en düşük toplam değere sahip alt şekli (subgraph) buluyoruz.

  2. Adımdan, problem çözülene kadar 2. adıma dönüyoruz.

Problemimize dönüp 2. adımı uygulayalım. 0-ağırlığına sahip kenarların değerleri aşağıda verilmiştir:

Yukarıdaki şekilde bulunan en düşük maliyetli atamadır. Bu atama A-T , S-C ve Ş-B şeklindedir ve Orijinal değerleri hatırlanacak olursa, 4+3+1 = 8 olarak hesaplanabilir. İddiamız, bu şekilde daha düşük maliyetli bir atama yapılamayacağıdır.

Yorumlar

  1. Saü BM

    Merhaba hocam!
    Güzel ve basit bir anlatım olmuş ama şu aklıma takıldı. Çıkarma yaparak yeni masfuflar elde ederken satırlarda veya sütunlarda birden fazla 0 olduğu durumlarda nasıl bir yol izlemeliyiz?
    Bir de ilk olarak satırların en küçük elemanlarını çıkarsak oluşan masfufla aynı optimum sonuçları elde eder miyiz?

    Örneğin:
    3 6 3 5
    7 3 5 8
    5 2 8 6
    8 3 6 4
    Matrisinde optimum durumu nasıl elde edeceğiz? Teşekkürler…

  2. Şadi Evren ŞEKER Article Author

    Verdiğiniz örnek masfufu (matrisi) beraber çözelim.

    ilk adımda, her sütundaki en küçük değeri sütundaki bütün elemanlardan çıkarıyoruz:

    3-3 6-2 3-3 5-4
    7-3 3-2 5-3 8-4
    5-3 2-2 8-3 6-4
    8-3 3-2 6-3 4-4

    çıkarma işlemi sonucunda masfuf aşağıdaki haldedir:
    0 4 0 1
    4 1 2 4
    2 0 5 2
    5 1 3 0

    ikinci adımda, her satırdaki en küçük değeri satırdaki bütün değerlerden çıkarıyoruz:

    0-0 4-0 0-0 1-0
    4-1 1-1 2-1 4-1
    2-0 0-0 5-0 2-0
    5-0 1-0 3-0 0-0

    masfufun heni hali aşağıdaki şekildedir:

    0 4 0 1
    3 0 1 3
    2 0 5 2
    4 1 3 0

    yukarıdaki yeni masfuf için soru çözülmüştür. Şöyleki :

    0-ağırlıklı yollar her satır ve sütun kesişiminde bulunur. Daha net anlaşılsın diye yazıdakine benzer şekilde satırlara S,Ş,T,U ve sütunlara A,B,C,D isimlerini vererek anlatmaya çalışalım:

      A B C D
    S 0 4 0 1
    Ş 3 0 1 3
    T 2 0 5 2
    U 4 1 3 0 
    

    Buna göre U-D bağlantısı tek ihtimaldir. S-A yine tek ihtimaldir. Her ne kadar S için A ve C bağlantıları 0-ağırlıklı olsa da C için 1 değeri en küçük değerken A için 2 değeri en küçük değerdir (sütundaki en küçük değerler) dolayısıyla doğru tercih, S-A ve Ş-C bağlantıları olacaktır. Geriye T-B bağlantısı kalmaktadır. Buna göre en iyi çözüm:

    U-D, S-A, Ş-C ve T-B bağlantıları seçilmelidir. Bu seçimlerin maliyetlerini hesaplayalım:

    4 + 3 + 5 + 2 = 14 olarak hesaplanır.

    Yukarıdaki soru için özel olarak şunu söyleyebilirim. Algoritmanın dışında olduğu için detayını çok açıklamadım ama dikkat ettiğiniz üzere S-A ve Ş-C bağlantıları sırasında bira dım ileriye giderek fikir yürüttük, dimağ oyunu yaptık. Bunun yerine König’in kuramı da kullanılabilir. Programlama açısından çok daha net sonuç alınabilir. Ancak Macar algoritması açısından olaya bakıldığında, algoritma yukarıdaki şekilde çalışmaktadır.

    Başarılar

  3. burak

    merhaba hocam benim aklıma bir şey takıldı bu soruyu nasıl çözeriz

    Aracınıza bakım yaptırmak istiyorsunuz. Bakımda filtre değişimi, yağ değişimi ve genel bakım yapılmakta. Aşağıdaki listede çeşitli servislerden aldığınız fiyatlar görünmekte yazacağınız program Macar algoritmasını kullanarak en iyisini seçmelidir. Listedeki fiyatlar ve servisler girdi olarak alınacak.
    Örnek:
    Filtre Değişimi Yağ Değişimi Genel Bakım
    A Servisi 150 TL 50 TL 50 TL
    B Servisi 90 TL 75 TL 25 TL
    C Servisi 75 TL 115 TL 18 TL
    …. ….. ….. …..

  4. Şadi Evren ŞEKER Article Author

    Bu soru macar algoritması ile ilgili değil. Yani soruda eksik birşeyler var. Şimdi bütün hizmetler için tek bir servis seçmemiz gerekiyorsa, satırların toplamlarına bakılır:

    A Servisi : 250
    B Servisi : 190
    C Servisi : 198

    O halde B servisi seçilir. Şayet her işlem için farklı bir servis seçilebiliyorsa o zaman işlem olarak satır taranır:

    Filtre Değişimi : 75 TL C Servisi
    Yap Değişimi : 50 TL A Servisi
    Genel Bakım : 18 TL C Servisi

    Toplam : 75 + 50 + 18 = 143 TL

    Şeklinde çözümüş olur. Görüldüğü üzere macar algoritması ile sorunun alakası yoktur. Muhtemelen soruda birşeyleri kaçırıyorsunuz.

    Başarılar

  5. can

    macar algoritması kullanarak bir program yazmam gerekiyor acaba bu tarz bir örnek elinizde mevcut mu? İnternetten ve elimdeki kaynaklardan araştırdım fakat örnek alabileceğim herhangi bir şeye rastlayamadım

  6. mustafa

    Hocam size bahsettiğim tez konusundada bunu deniyebiliriz zannedersem.
    öğrenci1 öğr2 öğr3 öğr4
    öğretmen1 10 15 20 25
    öğrm2 5 10 15 20
    öğrm3 20 25 30 35
    öğrm4 15 20 25 30

    sayılar mesafeyi gösteriyo. hangi öğrencinin hangi öğretmene atanacağını bulabilirmiyiz.

  7. Erkan

    Merhaba hocam macar algoritmasını farklı kaynaklardan araştırdım tümünde önce satırdaki en küçük eleman o satırdaki diğer elemanlardan çıkarılıyor , sonra ise sütundaki en küçük eleman için aynı işlem yapılıp , bütün sıfırların üzerini kapatacak minimum çizgi çiziliyor. Siz ise tam tersi önce satırlardan başlamışsınız. en küçük eleman seçilip diğer elemanlardan çıkarılırken satır , sütun önceliği var mı ? Böyle bir öncelik varsa neye göre belirleniyor ?

    1. Zeynep

      Merhaba Hocam,

      Soru:
      Aşağıdaki problemi macar metodu ile çözünüz. Belirli bir nxn maliyet matrisi için, Macar algoritması kullanılarak bir optimal tahsis edilir.
      Problem: Oyuncak üreticisi firma için satış müdürü olarak çalışıyorsunuz. Şu anda Austin, Boston ve Chicago’ da bulunarak müşterilerle görüşen üç satış elemanınız var. Siz elemanlarınızın Denver, Edmonton ve Fargo’ ya uçmasını istiyorsunuz. Aşağıdaki tablo bu şehirler arasındaki uçak biletlerinin fiyatlarını dolar cinsinden gösteriyor.
      Firmanızın uçak bileti masraflarını minimize edebilmek için satış elemanlarınızın her birini hangi şehre gönderirsiniz?

      Denver Edmonton Fargo
      Austin 250 400 350
      Boston 400 600 350
      Chicago 200 400 250

  8. Şadi Evren ŞEKER

    Soruyu adım adım çözelim. İlk adımda bütün kolonlardan o kolondaki en düşük değeri çıkarıyoruz (şehirlerin baş harflerini aldım):

    d e f
    a 250-200 400-400 350-250
    b 400-200 600-200 350-250
    c 200-200 400-400 250-250

    sonuç:

    d e f
    a 50 0 100
    b 200 200 100
    c 0 0 0

    Burada ufak bir yorum yapılabilir. C satırındaki bütün değerler 0 olduğu için C her yere gidebilir dolayısıyla en ucuz uçuşları belirlerken a ve b’nin nereye gideceği belirleyici olacaktır.

    ikinci adımda henüz 0 içermeyen satır olduğu için (b satırında hiç 0 değeri yok) satırlardan da en küçük değerleri çıkarıyoruz

    d e f
    a 50-0 0-0 100-0
    b 200-100 200-100 100-100
    c 0-0 0-0 0-0

    sonuç:
    d e f
    a 50 0 100
    b 100 100 0
    c 0 0 0

    görüldüğü üzere a->e , b->f ve c->d uçuş seçimleri en düşük maliyet olarak çıktı.

    Gerçekten bu değerleri topladığımızda (sorudaki fiyatlarla) A->E uçuşu 400 + B->F uçuşu 350 ve C->D uçuşu da 200 dolar ise toplamda 950 dolarlık bir maliyetle uçuşlar gerçekleştirilmiş olur.

  9. Alperay

    Şadi Bey, Saü’nün sorduğu örnekte aslında algoritma devam ediyor. Bir adımı daha var ve çıkan son matris;

    0 5 0 2
    2 0 0 3
    1 0 4 2
    3 1 2 0

    şeklinde ve sonuç da sizin verdiğiniz cevap gibi U-D, S-A, Ş-C ve T-B şeklinde çıkıyor. Arkadaşlara Macar Algoritmasını araştırmasını öneririm. Bilgilendirme ve örnek için teşekkürler. İyi çalışmalar.

  10. Yasin

    Hocam verdiğiniz bilgiler için teşekkürler Macar algoritmasını kitapta resmen çorba yapmışlar ama burada kolay bir şekilde anladım .

Zeynep için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir