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

Haziran 1006

Bipartite Graph

Bipartite graph veya bigraph olarak bilinen bu graf, kendi aralarında bağımsız (bağlantı olmayan) sadece karşısındaki kümedeki düğümlerle bağlantısı olan 2 düğüm kümesinden oluşur. Graflar genelde karşımıza bu şekilde çıkmazlar. Daha karmaşıklardır. Onları bu hale getirmek uğraştırır. Bir grafın bipartite olup olmadığını öğrenmek için başka bir yöntem vardır: Kendimize bir kök (başlangıç) noktası seçeriz ve bu düğümü Mavi boyarız. Bu düğümden çıkan her kenarında sonunda yer alan düğümleri Kırmızı boyarız. Kırmızı düğümlerden ıkan her kenarın sonundaki düğümü de Mavi boyarız. Tüm renklendirme işlemi bittiğinde her kenarın her iki tarafındaki düğümlerin renkleri farklı ise graf Bipartite graph özelliğini taşır. Ancak bir tane bile uçları aynı renkte kenar olması durumunda graf bipartite değildir. En çok kullanıldığı alan eşleme problemleridir (Matching Problems). Aynı zamanda şifreli şekilde gelen verilerin çözülmesinde de kullanılabilir. Tags: , , , | Categories: Algoritma