menu 首页 标签 归档 视频 关于
算法-稳定匹配

一言加载中...

由于学习需要,然后花费将近两天时间研究这个问题,然后用C++描述出来,具体内容看下面:

问题描述(见百度百科):
https://baike.baidu.com/item/%E7%A8%B3%E5%AE%9A%E5%A9%9A%E5%A7%BB%E9%97%AE%E9%A2%98/12760040

为了解决稳定匹配问题(Stable Matching Problem),前辈们提出了GS算法。

下面就是博主使用GS算法完成的本题,同时在研究过程中发现了一个新的匹配思路,将会在下面发出来(不知道前辈们有没有提出过),大家可以积极提出宝贵意见:

问题分析:

1.首先输入男士(女士)人数,这里男士,女士人数相同并且要求最后每个人都有对象。

2.初始化所有男士,女士追求过对象人数better=0,对异性喜欢排名数组rank[],当前是否在约会状态Yuehui,以及现任为-1;

3.既然男的需要主动,那就让所有单身状态的男士向自己最喜欢的女士表白,不管结局成功与否,该男士追求过的人数都加1;

4.如果女士单身,那么两个人就暂时在一起先处着,更改两个人是否约状态为true,设置对方为自己的现任;

5.如果女士不是单身,此时就出现了小三,那么主动权就交给女士了,此时女士比较现任小三,如果更喜欢现任。跳过当前追求者;如果更喜欢小三,抛弃现任,此时小三终于扬眉吐气成功上位,并与当前追求者结合成暂时情侣去约会。

6.判断是否全部找到对象,都找到了结束查找,否则重复步骤:2-5,直到全部由对象;

7.结束,输出;

程序设计
这里使用历史人物,(得到的最终匹配结果可能不与现实相同),男女各5名,对其进行编号。由编号代替其姓名。
pic1

各男士喜欢排名表:
(仅供实验参考,最终数据为自行输入)
pic2

各女士喜欢排名表:
(仅供实验参考,最终数据为自行输入)
pic3

定义人类(是人 ):

//人类
class People
{
    private:
        int better;             //追求过几位女生
        int rank[NUM];          //喜欢排名
        bool Yuehui;            //是否在约会
        int present;            //现任
    public:
        People()
        {
            better = 0;
            Yuehui = false;
            present = -1;
        }
        void setRank(int mRank, int i);
        int getRank(int i) { return rank[i]; };
        void setYuehui(bool mYuehui);
        bool getYuehui() { return Yuehui; };
        void setBetter(int mBetter);
        int getBetter() { return better; };
        void setPresent(int mPressent);
        int getPressent() { return present; };
};

完整代码:

#include<iostream>
#include<cstring>
using namespace std;

const int NUM = 5;
int flag = 0;


//人类
class People
&#123;
    private:
        int better;             //追求过几位女生
        int rank[NUM];          //喜欢排名
        bool Yuehui;            //是否在约会
        int present;            //现任
    public:
        People()
        &#123;
            better = 0;
            Yuehui = false;
            present = -1;
        &#125;
        void setRank(int mRank, int i);
        int getRank(int i) &#123; return rank[i]; &#125;;
        void setYuehui(bool mYuehui);
        bool getYuehui() &#123; return Yuehui; &#125;;
        void setBetter(int mBetter);
        int getBetter() &#123; return better; &#125;;
        void setPresent(int mPressent);
        int getPressent() &#123; return present; &#125;;
&#125;;
void People::setRank(int mRank, int i)
&#123;
    rank[i] = mRank;
&#125;
void People::setYuehui(bool mYuehui)
&#123;
    Yuehui = mYuehui;
&#125;
void People::setBetter(int mBetter) 
&#123;
    better = mBetter;
&#125;
void People::setPresent(int mPressent)
&#123;
    present = mPressent;
&#125;


int main()
&#123;
    People man[NUM];
    People lady[NUM];
    for (int i = 0; i < NUM; i++)
    &#123;
        for (int j = 0; j < NUM; j++)
        &#123;
            int temp;
            cout << "请输入第" << i+1 << "个人喜欢的第" << j+1 << "个人:";
            cin >> temp;
            man[i].setRank(temp, j);
        &#125;
    &#125;
    cout << "男士初始化完毕" << endl;
    for (int i = 0; i < NUM; i++)
    &#123;
        for (int j = 0; j < NUM; j++)
        &#123;
            int temp;
            cout << "请输入第" << i + 1 << "个人喜欢的第" << j + 1 << "个人:";
            cin >> temp;
            lady[i].setRank(temp, j);
        &#125;
    &#125;
    cout << "女士初始化完毕" << endl;


    while (true)
    &#123;
        flag = 1;                                       //设定全部脱单标记
        //所有男士向自己最喜欢的女士表白
        for (int i = 0; i < NUM; i++)
        &#123;
            if (man[i].getYuehui() == false)            //男士单身
            &#123;
                flag = 0;                               //还有单身狗标记
                int num_Y = man[i].getBetter();                 //男士应向第几位喜欢的表白
                int girl = man[i].getRank(num_Y);               //获取喜欢女士的位置
                man[i].setBetter(num_Y + 1);                    //无论表白失败与否,下次表白对象位置
                if (lady[girl].getYuehui() == false)    //喜欢的女士单身
                &#123;
                    man[i].setYuehui(true);                 //男士改为约会状态
                    man[i].setPresent(girl);                //设置现任为该女士
                    lady[girl].setYuehui(true);             //喜欢的女士也更改为约会状态
                    lady[girl].setPresent(i);               //设置现任为该男士
//                  cout << girl<<" ";                      //输出最喜欢的女士
                &#125;
                if (lady[girl].getYuehui() == true) //喜欢的女士不单身
                &#123;
                    //女士通过比较与自己最喜欢的那位男士在一起
                    int before, now;
                    //通过循环判断现任和小三在女士心中的位置
                    for (int j = 0; j < NUM; j++)
                    &#123;
                        if (lady[girl].getRank(j) == i)
                        &#123;
                            now = j;
                        &#125;
                        if (lady[girl].getRank(j) == lady[girl].getPressent())
                        &#123;
                            before = j;
                        &#125;
                    &#125;
                    //如果女士喜欢现任
                    if (before < now)
                    &#123;
                        //小三滚蛋吧~~
                        //man[i].setBetter(man[i].getBetter() + 1);
                    &#125;
                    //女士喜欢
                    else if (before>now)
                    &#123;
                        man[lady[girl].getPressent()].setYuehui(false); //现任变前任
                        man[lady[girl].getPressent()].setPresent(100);  //变单身狗
                        man[i].setYuehui(true);                         //小三上位
                        man[i].setPresent(girl);

                        lady[girl].setPresent(i);
                    &#125;
                &#125;
            &#125;
        &#125;

        if (flag == 1)
        &#123;
            break;
        &#125;   
    &#125;
    //输出
    for (int i = 0; i < NUM; i++)
    &#123;
        cout << i << "和" << man[i].getPressent() << "在一起" << endl;
    &#125;
&#125;

最后,看下结果吧~~
result

最最后,画了张图并结合上面三张表述我的新思路:
think1

think2

think3

think4

Tony-Chen
2017.10.25

心的强大因为鉴定!

写博客不易,请我喝杯咖啡?

评论

arrow_upward