c \ # 게 일 - 사 프 리 알고리즘 개선

게 일 - 사 프 리 알고리즘
'게 일 - 샤프 리 알고리즘' (the Gale - Shapley algorithm) 은 '지연 수용 알고리즘' (deferred - acceptance algorithm) 이 라 고도 불 리 며 'GS 알고리즘' 이 라 고도 부른다.게 일과 사 프 리 가 안정 적 인 매 칭 을 찾기 위해 설계 한 시장 메커니즘 이다.시장 한쪽 의 대상 (의료 기구) 은 다른 쪽 의 대상 (의과대학 학생) 에 게 요 구 를 하고 모든 학생 회 는 자신 이 받 은 요 구 를 고려 한 다음 에 자신 이 선 호 하 는 것 (받 아들 일 수 있다 고 생각 하 는 것) 을 잡 아 다른 것 을 거절 했다.이 알고리즘 의 관건 은 합의 한 요약 이 바로 받 아들 여지 지 않 고 '잡 히 기' (hold on to), 즉 '지연 수용' 이라는 점 이다.청 약이 거절당 한 후에 야 의료 기관 은 다른 의 대 학생 에 게 새로운 청 약 을 할 수 있다.전체 절 차 는 새로운 청 약 을 원 하 는 기관 이 없 을 때 까지 계속 되 었 고, 그때 가 되 어서 야 학생 들 은 결국 각자 의 '잡 아 라' 는 청 약 을 받 아 들 였 다.
본 고 는 이 알고리즘 을 바탕 으로 실제 상황 에 적응 하기 위해 다른 요 소 를 추가 했다.
1. 개인 득점 시스템, 평가 시스템 을 추가 합 니 다.결혼 할 때 쌍방의 점수 차 이 는 너무 크 면 안 된다.
2. 이혼 난이도 증가
3. 단체의 접촉 범 위 를 통제한다.한 남성 이 일부 여성 만 접촉 할 수 있다 는 것 이다.
원시 적 인 게 일 사 프 리 알고리즘 에 서 는 남성의 만족 도 는 100 에 가 깝 고 여성의 만족 도 는 50 에 가깝다.알고리즘 조정 후 쌍방의 만족 도 는 비교적 비슷 하 다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//  -   [Gale-Shapley]        
// N   ，M   ，          (      )，    ，             
//         ，         （                      ）。
//      ，                     。
//            
namespace GaleShapley
{
    class Program
    {
        static void Main(string[] args)
        {
            Marry marry = new Marry(200, 200);
            int number = marry.MaleDic.Count;
            marry.Start();
            Console.WriteLine("MaleSatisfaction : " + marry.MaleSatisfaction);
            Console.WriteLine("FeMaleSatisfaction : " + marry.FemaleSatisfaction);
            //Console.WriteLine("  ID\t  \t   \t  ID\t  \t   ");
            //foreach (Male male in marry.MaleDic.Values)
            //{
            //    if (!male.Marryed)
            //    {
            //        continue;
            //    }
            //    Female female = marry.FemaleDic[male.PartnerID];
            //    Console.WriteLine(male.ID + "\t" + male.Point.ToMyString() + "\t" + male.Satisfaction.ToMyString() + "\t" + 
            //        female.ID + "\t" + female.Point.ToMyString() + "\t" + female.Satisfaction.ToMyString());
            //}
            //List maleList = (marry.MaleDic.Values.Where(p => !p.Marryed)).ToList();
            //List femaleList = (marry.FemaleDic.Values.Where(p => !p.Marryed)).ToList();
            //for (int i = 0; i < maleList.Count; i++)
            //{
            //    Male male = maleList[i];
            //    Female female = femaleList[i];
            //    Console.WriteLine(male.ID + "\t" + male.Point.ToMyString() + "\t" + male.Satisfaction.ToMyString() + "\t" +
            //       female.ID + "\t" + female.Point.ToMyString() + "\t" + female.Satisfaction.ToMyString());
            //}
            Console.ReadLine();
        }
    }
    public static class DoubleExtendMethod
    {
        public static string ToMyString(this double num)
        {
            return num.ToString("0.##");
        }
    }
    ///


    ///     
    /// 
    public class RequestObj
    {
        ///


        ///     
        /// 
        public int ID { get; private set; }
        ///


        ///            
        /// 
        public double EstimatePoint { get; private set; }

        public RequestObj(int id, double estimatePoint)
        {
            this.ID = id;
            this.EstimatePoint = estimatePoint;
        }
    }
    public class People
    {
        private static double MaxPoint = 1000;
        private static double MinPoint = 200;
        ///


        ///     
        /// 
        public int ID { get; set; }
        ///


        ///     
        /// 
        public int PartnerID { get; set; }
        public bool Marryed
        {
            get
            {
                return this.PartnerID < 0 ? false : true;
            }
        }
        ///


        ///     
        /// 
        public double Point { get; set; }
        ///


        ///     
        /// 
        public double MyEstimatePoint { get; set; }
        ///


        ///     
        /// 
        public double PartnerEstimatePoint { get; set; }
        /// 
        ///    
        /// 
        public double Satisfaction
        {
            get
            {
                if (!this.Marryed)
                {
                    return 0;
                }
                //               
                double mul = Math.Abs(this.MyEstimatePoint - this.PartnerEstimatePoint) / People.MaxPoint;
                if (this.MyEstimatePoint > this.PartnerEstimatePoint)
                {
                    return 50.0 * (1 - mul);
                }
                else
                {
                    return 50.0 * (1 + mul);
                }
            }
        }
        public People(int id)
        {
            this.PartnerID = -1;
            this.ID = id;
            this.Point = Marry.Rnd.NextDouble() * (People.MaxPoint - People.MinPoint) + People.MinPoint;   //     0-1000  ，    
            this.MyEstimatePoint = People.GetEstimatePoint(this.Point);
        }

        /// 
        ///     
        /// 
        ///     
        ///   
        public static double GetEstimatePoint(double point)
        {
            //return point;
            double mul = 0.8 + Marry.Rnd.NextDouble() * 0.4;    //     80% - 120%   
            return point * mul;
        }
    }
    public class Male : People
    {
        public List RequestList { get; set; }
        public Male(int id)
            : base(id)
        {

        }
        public void InitRequestList(Dictionary<int, Female> femaleDic)
        {
            this.RequestList = new List();
            foreach (Female female in femaleDic.Values)
            {
                if (Marry.Rnd.Next(10) != 1)//              ，           ，            
                {
                    continue;
                }
                double point = People.GetEstimatePoint(female.Point);//     
                if (point > this.MyEstimatePoint)
                {
                    double mul = (point - this.MyEstimatePoint) / this.MyEstimatePoint;
                    if (mul < 0.2)
                    {
                        this.RequestList.Add(new RequestObj(female.ID, point));
                    }
                }
                else
                {
                    double mul = (this.MyEstimatePoint - point) / this.MyEstimatePoint;
                    if (mul < 0.2)
                    {
                        this.RequestList.Add(new RequestObj(female.ID, point));
                    }
                }
            }
            this.RequestList = this.RequestList.OrderByDescending(a => a.EstimatePoint).ToList();//  
        }

        /// 
        ///   
        /// 
        /// 
        /// 
        public void Request(Dictionary<int, Male> maleDic, Dictionary<int, Female> femaleDic)
        {
            if (this.Marryed)
            {
                return;
            }
            if (this.RequestList.Count == 0)
            {
                return;
            }
            Female female = femaleDic[this.RequestList[0].ID];
            if (female.BeRequest(this, maleDic))
            {
                this.PartnerID = female.ID;
                this.PartnerEstimatePoint = this.RequestList[0].EstimatePoint;
            }
            this.RequestList.RemoveAt(0);
        }

        /// 
        ///   
        /// 
        public void Divorce()
        {
            this.PartnerID = -1;
            this.PartnerEstimatePoint = 0;
        }
    }
    public class Female : People
    {
        public Female(int id)
            : base(id)
        {

        }

        public bool BeRequest(Male male, Dictionary<int, Male> maleDic)
        {
            double estimatePoint = People.GetEstimatePoint(male.Point);//   
            if (this.Marryed)//     
            {
                if (this.PartnerEstimatePoint < estimatePoint)
                {
                    double difference = estimatePoint / this.PartnerEstimatePoint;
                    if (difference > 1.5)
                    {
                        maleDic[this.PartnerID].Divorce();
                        this.PartnerID = male.ID;
                        this.PartnerEstimatePoint = estimatePoint;
                        return true;
                    }
                }
                return false;
            }
            else//  
            {
                if (estimatePoint > (this.MyEstimatePoint * 0.8))
                {
                    this.PartnerID = male.ID;
                    this.PartnerEstimatePoint = estimatePoint;
                    return true;
                }
                return false;
            }
        }
    }
    public class Marry
    {
        /// 
        ///         
        /// 
        public static Random Rnd = new Random();
        public Dictionary<int, Male> MaleDic { get; set; }
        public Dictionary<int, Female> FemaleDic { get; set; }
        /// 
        ///    
        /// 
        public int MarriageCount
        {
            get
            {
                int count = 0;
                foreach (Male male in this.MaleDic.Values)
                {
                    if (male.Marryed)
                    {
                        count++;
                    }
                }
                return count;
            }
        }
        /// 
        ///     
        /// 
        public int SingleCount
        {
            get
            {
                return this.MaleDic.Count + this.FemaleDic.Count - this.MarriageCount * 2;
            }
        }
        public double MaleSatisfaction
        {
            get
            {
                double satisfaction = 0;
                foreach (Male male in this.MaleDic.Values)
                {
                    satisfaction += male.Satisfaction;
                }
                return satisfaction / this.MaleDic.Count;
            }
        }
        public double FemaleSatisfaction
        {
            get
            {
                double satisfaction = 0;
                foreach (Female female in this.FemaleDic.Values)
                {
                    satisfaction += female.Satisfaction;
                }
                return satisfaction / this.FemaleDic.Count;
            }
        }
        /// 
        ///       
        /// 
        public bool NeedMatch
        {
            get
            {
                foreach (Male male in this.MaleDic.Values)
                {
                    if (male.RequestList.Count > 0 && !male.Marryed)
                    {
                        return true;
                    }
                }
                return false;
            }
        }
        public Marry(int maleNum, int femaleNum)
        {
            this.MaleDic = new Dictionary<int, Male>();
            this.FemaleDic = new Dictionary<int, Female>();
            for (int i = 0; i < maleNum; i++)
            {
                MaleDic.Add(i, new Male(i));
            }
            for (int i = 0; i < femaleNum; i++)
            {
                FemaleDic.Add(i, new Female(i));
            }
            foreach (Male male in this.MaleDic.Values)
            {
                male.InitRequestList(this.FemaleDic);
            }
        }
        public void Start()
        {
            while (this.NeedMatch)
            {
                foreach (Male male in this.MaleDic.Values)
                {
                    male.Request(this.MaleDic, this.FemaleDic);
                }
            }
        }
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

c \ # 게 일 - 사 프 리 알고리즘 개선

좋은 웹페이지 즐겨찾기