盖尔-沙普利算法
“盖尔-沙普利算法”（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<Male> maleList = (marry.MaleDic.Values.Where(p => !p.Marryed)).ToList<Male>(); //List<Female> femaleList = (marry.FemaleDic.Values.Where(p => !p.Marryed)).ToList<Female>(); //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.##"); } } /// <summary> /// 请求对象 /// </summary> public class RequestObj { /// <summary> /// 对象编号 /// </summary> public int ID { get; private set; } /// <summary> /// 对象在自己心目中的估分 /// </summary> 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; /// <summary> /// 个人编号 /// </summary> public int ID { get; set; } /// <summary> /// 配偶编号 /// </summary> public int PartnerID { get; set; } public bool Marryed { get { return this.PartnerID < 0 ? false : true; } } /// <summary> /// 实际得分 /// </summary> public double Point { get; set; } /// <summary> /// 个人估分 /// </summary> public double MyEstimatePoint { get; set; } /// <summary> /// 配偶得分 /// </summary> public double PartnerEstimatePoint { get; set; } /// <summary> /// 满意度 /// </summary> 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); } /// <summary> /// 估分系统 /// </summary> /// <param>实际得分</param> /// <returns>估分</returns> 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<RequestObj> RequestList { get; set; } public Male(int id) : base(id) { } public void InitRequestList(Dictionary<int, Female> femaleDic) { this.RequestList = new List<RequestObj>(); 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<RequestObj>();//降序 } /// <summary> /// 求婚 /// </summary> /// <param></param> /// <param></param> 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); } /// <summary> /// 离婚 /// </summary> 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 { /// <summary> /// 全局使用的随机数 /// </summary> public static Random Rnd = new Random(); public Dictionary<int, Male> MaleDic { get; set; } public Dictionary<int, Female> FemaleDic { get; set; } /// <summary> /// 结婚数 /// </summary> public int MarriageCount { get { int count = 0; foreach (Male male in this.MaleDic.Values) { if (male.Marryed) { count++; } } return count; } } /// <summary> /// 单身人数 /// </summary> 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; } } /// <summary> /// 需要继续匹配 /// </summary> 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); } } } } }