Gale-Shapley uygun evlenme problemine çözüm sağlar. 2 set halinde bulunan elemanları birbiri ile eşleştirir. Uygun evlendirme probleminde bu 2 set eleman kızlar ve erkeklerdir. Ancak Gale-Shapley algoritması başka setler için de uygun çözümdür. Uygulanışı: Setlerimize “Erkek” ve “Bayan” adını verelim. Her setimizde eşit sayıda elaman ve her elemanın karşı setteki elamanları tercih sıralaması var. Bu bir evlilik eşleşmesi olsun.             Sıradan elemanlarımıza bakıyoruz. Xavier 1. olarak Amy’i tercih ediyor. Amy’nin şuanda eşi yok. Xavier – Amy eşleşmesi yapılır. Diğer eleman Yancey’in ilk tercihi Bertha. Bertha’nın şuanda eşi yok. Yancey – Bertha eşleşmesi yapılır. Son eleman Zeus’un ilk tercihi Amy – Xavier eşleşmesi var. Amy, Xavier’i Zeus’a göre daha yüksek öncelikle tercih ediyor. Eş bozulmaz. Eğer daha alçak öncelikle tercih etseydi Xavier – Amy eşleşmesi bozulacak, Zeus – Amy  eşleşmesi kurulacak, işlemlerde geriye gidilip Xavier’e sıradan yeni eşleşme yapılmak durumunda kalınacaktı. Amy’i atlayan Zeus’un sıradaki tercihi Bertha. Bertha – Yancey  eşleşmesi var ve Yancey’in öceliği daha yüksek. Eşlik yine bozulmadı. Zeus’un son tercihi Clare şuanda eşli değil. Zeus – Clare eşlemesi yapıldı.   Yukarıdaki örnekte erkekler kızlara önerdi, kızlar karar verdi. Eğer kızlar erkeklere önerseydi ve kızlar karar verseydi nasıl olurdu ? Bunu da siz bulun. Algoritma: function stableMatching { Initialize all <I>m</I> ∈ M and <I>w</I> ∈ W to <I>free</I> while ∃ <I>free</I> man <I>m</I> who still has a woman w to propose to { w = m's highest ranked such woman who he has not proposed to yet if w is <I>free</I> (m, w) become <I>engaged</I> else some pair (m', w) already exists if w prefers m to m' (m, w) become <I>engaged</I> m' becomes <I>free</I> else (m', w) remain <I>engaged</I> } } Tags: , , | Categories: Algoritma