Stable Marriage Problem (Kararlı Eşleşme Problemi)

Kararlı eşleşme problemi; elaman sayıları eşit olan iki küme arasında, tüm elamanları içeren en optimal eşleşmeyi bulmayı hedefler. Sonuç olarak tüm elemanlar eşleşeceği için bu problem kararlı olacaktır. Her ne kadar problemin çıkışı bir evlilik-eşleşme- sorunu olsa da, bunu öğrenci-üniversite, doktor-hastane, öğretmen-okul eşleşmesiyle ilgili bir problem olarak da yorumlayabilirsiniz. Bu durumların hepsine kararlı eşleşme problemi denmektedir.

Kararlı eşleme sorunu olarak adlandırılan  eşleşmenin bir sürümü. N erkeklerin y = {m1,…,mn} kümesi ve N kadınların x = {w1,…,wn} kümesi vardır. Her erkeğin kadınların bir sıralama listesi vardır ve her kadının erkeklerin bir sıralama listesi vardır (bu listelerde hiçbir bağı yoktur).

 Bir evlilik eşleştirme M n çiftleri (mi, wj) kümesidir. Bir çift (m, w) erkek m ve kadın w M eşleşti ama M onların arkadaşları birbirlerini tercih değilse m eşleştirme için bir engelleme çifti olduğu söylenir. Bunun için hiçbir engelleme çifti varsa bir evlilik eşleştirme m kararlı denir; aksi takdirde, kararsız denir. İstikrarlı evlilik sorunu erkek ve kadın verilen tercihleri için istikrarlı bir evlilik eşleştirme bulmaktır.

Kararlı evlilik sorununun bir örneği, aşağıdaki örnekte olduğu gibi, iki set tercih listesi veya bir sıralama matrisi ile belirtilebilir.

Kararlı evlilik sorununun örneği

           Erkeklerin Tercihleri        Kadınların Tercihleri

                      1.      2.      3.                        1.       2.       3.

           Bob: Lea  Ann  Sue               Ann: Jim  Tom  Bob

           Jim:  Lea  Sue  Ann               Lea:  Tom  Bob  Jim

          Tom:  Sue Lea  Ann                Sue:  Jim  Tom  Bob

Sıralama Matriksi

             Ann  Lea  Sue

    Bob  2,3   1,2   3,3

    Jim  3,1  1,3   2,1

   Tom  3,2   2,1   1,2

{(Bob, Ann) (Jim, Lea) (Tom, Sue)} kararsız durumda.

{(Bob, Ann) (Jim, Sue) (Tom, Lea)} kararlı durumda.

Kararlı Evlilik Algoritması (Gale-Shapley)

Adım 1: Tüm erkekleri ve kadınları özgür olarak başlatın.

Adım 2: Erkekleri seçime başatın. İlk sıradaki erkek, kendi istek listesindeki ilk kişiye çıkma teklifi eder. İlk seçim olduğu için çıkmaya başlarlar. Daha sonra 2. erkeğe sıra gelir. İstek listesindeki ilk kişiye çıkma teklifi eder. Eğer tercihin sevgilisi yoksa çıkmaya başlarlar ve sıra sonraki kişiye geçer. Eğer tercihin sevgilisi var ise, tercihin kendi listesi kontrol edilir. Teklif yapan kişi, tercihin listesinde, şu an çıktığı kişiden daha öncelikli ise kişiler çıkmaya başlar. Eğer daha öncelikli değilse sıra sonraki kişiye geçer. 

Adım 3: Herkes eşleşene kadar bu işlem devam eder.

Kararlı eşleşme problemini adım adım inceleyelim.

Gale-Shapley Algoritmasının Analizi

Algoritma, istikrarlı bir evlilik çıkışı ile n2(n kare) yinelemelerinden daha fazla sonra sona erer.

İstikrarlı evlilik sorunu, tıp-okul mezunlarını ikamet eğitimi için hastanelerle eşleştirme gibi pratik uygulamalara sahiptir.

Bir erkek (kadın) optimal eşleştirme, belirli bir katılımcı tercihleri kümesi için benzersizdir.

Algoritma tarafından üretilen istikrarlı eşleştirme her zaman erkek optimaldir. Her erkek herhangi istikrarlı evlilik altında kendi listesinde en yüksek rütbe kadını alır. Bir kadın erkeklere teklif yaparak, kadın optimal eşleştirme elde edilebilir.

Warshall algoritmasını öğrenmek için bu yazımızı okumalısınız.