알고리즘) 게일- 섀플리 알고리즘(Gale-Shapley Algorithm)

게일- 섀플리 알고리즘(Gale-Shapley Algorithm)

 서로에 대해 선호를 가진 지단 간 안정적 매칭을 찾아내는 알고리즘이다. 안정적 매칭은 두 집단에 속하는 사람들이 빠짐없이 모두 매칭에 성공하였으며, 매칭된 결과에 모든 사람이 만족하고 있는 상태를 말한다.

 

반응형

절차는 다음과 같다.

 

<알고리즘 절차>

1. 초기화

2. 제안단계

3 수락 단계

4 반복

5 종료

 

간단하게 결혼상대를 찾는 매칭을 게일 -섀플리 알고리즘을 통해서 구현한다고 치면 다음과 같다.

 

< 예시 >

간단하게 남성4명과 여성4명을 매칭시키는 알고리즘을 구현하면 다음과 같다.

using System;
using System.Collections.Generic;

class Man
{
    public string Name { get; set; }
    public List<string> Preferences { get; set; }
    public string MatchedWoman { get; set; }

    public Man(string name, List<string> preferences)
    {
        Name = name;
        Preferences = preferences;
        MatchedWoman = null;
    }
}

class Woman
{
    public string Name { get; set; }
    public List<string> Preferences { get; set; }
    public string MatchedMan { get; set; }

    public Woman(string name, List<string> preferences)
    {
        Name = name;
        Preferences = preferences;
        MatchedMan = null;
    }
}

 

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<Man> men = new List<Man>
        {
            new Man("M1", new List<string> { "W3", "W2", "W1", "W4" }),
            new Man("M2", new List<string> { "W2", "W3", "W1", "W4" }),
            new Man("M3", new List<string> { "W1", "W2", "W3", "W4" }),
            new Man("M4", new List<string> { "W4", "W2", "W3", "W1" })
        };

        List<Woman> women = new List<Woman>
        {
            new Woman("W1", new List<string> { "M4", "M2", "M1", "M3" }),
            new Woman("W2", new List<string> { "M3", "M1", "M4", "M2" }),
            new Woman("W3", new List<string> { "M1", "M3", "M2", "M4" }),
            new Woman("W4", new List<string> { "M2", "M3", "M1", "M4" })
        };

        Dictionary<string, bool> menStatus = new Dictionary<string, bool>();
        foreach (var man in men)
        {
            menStatus.Add(man.Name, false);
        }

        while (menStatus.ContainsValue(false))
        {
            foreach (var man in men)
            {
                if (!menStatus[man.Name])
                {
                    string topWoman = man.Preferences.Find(w => women.FindIndex(m => m.Name == w) != -1);

                    if (women.Find(w => w.Name == topWoman).MatchedMan == null)
                    {
                        women.Find(w => w.Name == topWoman).MatchedMan = man.Name;
                        man.MatchedWoman = topWoman;
                        menStatus[man.Name] = true;
                    }
                    else
                    {
                        var currentMan = men.Find(m => m.Name == women.Find(w => w.Name == topWoman).MatchedMan);
                        int currentIndex = currentMan.Preferences.IndexOf(topWoman);
                        int proposedIndex = currentMan.Preferences.IndexOf(man.MatchedWoman);

                        if (currentIndex > proposedIndex)
                        {
                            currentMan.MatchedWoman = null;
                            menStatus[currentMan.Name] = false;
                            women.Find(w => w.Name == topWoman).MatchedMan = man.Name;
                            man.MatchedWoman = topWoman;
                            menStatus[man.Name] = true;
                        }
                    }
                }
            }
        }

        // Print the stable matches
        Console.WriteLine("Stable Matches:");
        foreach (var man in men)
        {
            Console.WriteLine($"{man.Name} is matched with {man.MatchedWoman}");
        }
    }
}

 

간단하게 작성된 알고리즘으로

결과적으로는 모든 남성과 여성이 매칭을 하는것을 목표로 진행했다.

실질적으로는 모두다 공평하게 매칭이 될순없기 때문에 추가적인 선호에 대한 가중치라던지, 옵션들이 포함되어야 한다.

 

 

 

참고 링크 위키 : [Gale-Shapley 알고리즘]

Gale–Shapley algorithm - Wikipedia

 

 

★☆☆☆☆