Giriş
İnternette bu kadar çok bilgi varken, programlamanın temel kavramlarına hâkim olmak oldukça önemlidir. Özellikle algoritma ve veri yapıları, yazılım geliştirme sürecinin belkemiğini oluşturur. Bu yazıda, Stable Marriage Problem (Sabit Evlilik Problemi) üzerinde duracağız. Yani, bir grup erkek ve bir grup kadının, birbirine en uygun şekilde eşleşmesini sağlamaya yönelik bir problemi ele alacağız. Hedefimiz, Python kullanarak bu problemi nasıl çözeceğimizi anlamak ve adım adım bir algoritma geliştirerek okuyucularımızı bu süreçte bilgilendirmektir.
Stable Marriage Problem, 1962 yılında David Gale ve Lloyd Shapley tarafından formüle edilen bir problem olup, iki grup arasındaki eşleşmelerin büyük bir kısmının istikrarlı olmasını sağlar. Burada ‘istikrarlı’ demek, herhangi bir çiftin birbirini tercih etmesine rağmen mevcut eşlerinin değiştirilmesini istemeyecekleri anlamına gelir. Bu probleme çözüm bulmak, birçok alanda yararlı olabileceği gibi, algoritmalara dair düşünme becerimizi de geliştirebilecektir.
Yazının ilerleyen bölümlerinde, önce problemi daha derinlemesine anlayacağız. Ardından, Python kullanarak çözümümüzü adım adım geliştirecek ve örneklerle destekleyeceğiz. Kısacası, bu yazı yalnızca Stable Marriage Problem’ı anlamanızı sağlamayacak; aynı zamanda Python ile algoritma geliştirmenin temellerini de öğrenmenize yardımcı olacaktır.
Stable Marriage Problem Nedir?
Stable Marriage Problem, iki farklı grup (örneğin, erkekler ve kadınlar) arasında en uygun eşleşmeyi bulmaya yönelik bir matematiksel problemdir. Her birey, karşı cinsin tüm bireylerine bir tercih sıralaması atar. Problem, bu tercihlere göre bireyleri eşleştirirken, istikrarlı bir çözüm bulmayı amaçlar. Yani, bireylerin, mevcut eşlerinden daha fazlasını aramadıkları bir durum ortaya çıkmalıdır.
Problemde, bir grup erkek ve bir grup kadın arasında eşleşme yapılırken, her bireyin diğer gruptaki bireyleri tercih sırasına göre sıraladığı bir durum çiziyoruz. Tek bir istikrarlı eşleşme bulmak yerine, mevcut olan en iyi eşleşmeleri bulmak istiyoruz. Örneğin, A kızı, B oğlunu A oğluna tercih ederse, bu durumda ilişkilerde dengesizlik oluşur. Bu gibi durumların önüne geçmek chide mücadele edeceğiz.
Eşleşmenin istikrarlı olup olmadığını kontrol etmek için, bireylerin birbirine karşı olan tercih sıralamalarını göz önünde bulundurmak gereklidir. Gale-Shapley algoritması, bu durumda kayda değer bir çözüm sunarak her işlem sonunda ‘kendi’ eşlerine sadık kalmalarını sağlar. Artık algoritmanın uygulamasına geçebiliriz.
Gale-Shapley Algoritması
Gale-Shapley algoritması, Stable Marriage Problem’ı çözmek için yaygın olarak kullanılan bir yöntemdir. Algoritmanın temel mantığı, her erkeğin sırasıyla kadına teklif vermesi ve kadınların en yüksek önceliğe göre teklifleri kabul etmesidir. Her teklif sonrasında kadınlar, uygun olmadıkça evlenmeyeceklerdir. Bu döngü, tüm bireylerin eşleşmesini sağlamak için tekrarlanır.
Algoritmanın temel adımları şu şekildedir: İlk olarak, tüm erkekler boşta kalır. Her erkek, kendi tercih sırasına göre kadınlara teklif yapar. Kadınlar, aldıkları teklifleri değerlendirir ve en uygun olanı kabul eder. Eğer kadın daha önce başka bir erkekle eşleşmişse, yeni teklife göre tekrar değerlendirme yapar. Bu işlem, herkes eşleşene kadar devam eder.
Bu aşamayı daha iyi anlamak için basit bir örnek üzerinden ilerleyelim. Farz edelim ki, 3 erkek (A, B, C) ve 3 kadın (X, Y, Z) olsun. Her birey, karşı cinsten olanlar arasında bir tercihe sahiptir. Algoritmanın işleyişi sırasında erkekler ve kadınlar arasında bir döngü oluşacak ve en nihayetinde her birey, kendi tercihlerine göre en uygun eşleşmeyi bulacaklardır.
Python ile Uygulama Geliştirmek
Şimdi, yukarıda tanımladığımız Gale-Shapley algoritmasını Python dilinde nasıl uygulayabileceğimizi görelim. İlk olarak, erkekler ve kadınlar için tercih sıralarını belirleyelim. Ardından, algoritmanın adımlarını kodlayarak eşleşmeyi sağlamaya çalışacağız.
Aşağıda, bu problemi çözmek için bir Python kodu sunulmaktadır. İlk adım olarak, erkeklerin ve kadınların kendi tercih sıralamalarını aynı şartlarda ayarlayalım.
def stable_marriage(men_preferences, women_preferences):
free_men = list(men_preferences.keys()) # Tüm erkekler boşta
engagements = {} # Evlilikleri tutmak için bir sözlük
men_proposals = {man: 0 for man in men_preferences} # Erkeklerin teklif sayısını sıfırla
while free_men:
man = free_men[0] # Boşta olan ilk erkeği al
man_pref = men_preferences[man]
woman_idx = men_proposals[man] # Bu erkeğin sıradaki kadını al
woman = man_pref[woman_idx]
# Kadının mevcut durumu kontrol et
if woman not in engagements:
# Kadın boşsa, teklifi kabul et
engagements[woman] = man
free_men.remove(man) # Erkeği boş erkekler listesinden çıkar
else:
current_man = engagements[woman] # Kadının mevcut eşini al
woman_pref = women_preferences[woman]
# Eğer yeni teklif mevcut evliliğinden daha iyiyse,
if woman_pref.index(man) < woman_pref.index(current_man):
engagements[woman] = man # Evliliği güncelle
free_men.remove(man)
free_men.append(current_man) # Eski eşi tekrar boş bırak
else:
men_proposals[man] += 1 # Teklifi reddedildi, bir sonrakine geç
return engagements
Yukarıdaki kod parçasında, erkek ve kadınların tercih sıralarını ve ilişkilerini temsil eden bir algoritma tanımladık. Şimdi, bu fonksiyonun nasıl çalıştığını ayrı bir bölümde görselleştireceğiz. Elde ettiğimiz sonuçları da değerlendirerek, istikrarlı bir eşleşmenin nasıl meydana geldiğini inceleyeceğiz.
Örnek Uygulama
Bize verilen erkekler ve kadınlar için tercih listelerini belirledikten sonra, algoritmamızı çağırabiliriz. Aşağıdaki gibi bir örnek listesini kullanacağız:
men_preferences = {
'A': ['Y', 'Z', 'X'],
'B': ['Z', 'Y', 'X'],
'C': ['X', 'Y', 'Z']
}
women_preferences = {
'X': ['B', 'A', 'C'],
'Y': ['C', 'A', 'B'],
'Z': ['A', 'B', 'C']
}
result = stable_marriage(men_preferences, women_preferences)
print(result)
Bu kodu çalıştırdığınızda, her bireyin hangi diğeriyle eşleştiğini görebileceksiniz. Algoritmanın sonucu, her erkeğin ve kadının en uygun eşleşmeleriyle birlikte istikrarlı bir ilişki geliştirmesidir. Örneğin sonuç şu şekilde olabilir:
{
'Y': 'A',
'Z': 'B',
'X': 'C'
}
Sonuç, her bireyin karşısında yazılan isimlerle tam anlamıyla bir ‘evlilik’ gerçekleştirdiğinin kanıtı olacaktır. Bu noktada, algoritmanın sabit evlilik problemini çözme kabiliyetini görmüş oluyoruz. Her bir birey kendi tercihlerine göre eşini bulmuş durumda.
Sonuç
Stable Marriage Problem, programlama ve algoritmalar üzerine çok önemli bir çalışmadır. Gale-Shapley algoritması sayesinde, iki farklı grup arasındaki uyumlu eşleşmeleri etkili bir şekilde bulmayı başardık. Python programlama dilini kullanarak bu algoritmanın temelini anlamış olduk ve kendi uygulamalarımızı geliştirebildik.
Uygulamalarınızı geliştirmek ya da daha karmaşık yapılar kurmak için bu algoritmayı daha da geliştirebilir ve optimize edebilirsiniz. Örneğin, farklı tercih sıralamaları ve büyük veri setleri üzerinde denemeler yaparak sonuçları her seferinde değerlendirmek oldukça öğretici olacaktır.
Son olarak, bu tür algoritmalar üzerinde çalışmak, programlama becerilerinizi geliştirmek ve analitik düşünme yeteneğinizi güçlendirmek için harika bir yoldur. Kendi projelerinizde bu yaklaşımı deneyerek, algoritmaların işleyişine dair daha fazla bilgi edinebilir ve Python’un gücünden yararlanabilirsiniz. Şimdi, öğrendiklerinizi test etmek ve kendi örneklerinizi yaratmak için harekete geçme zamanı!