menu Home Tags Archives Video About
算法-稳定匹配

一言加载中...

由于学习需要,然后花费将近两天时间研究这个问题,然后用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

定义人类(是人 ):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//人类
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; };
};

完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<iostream>
#include<cstring>
using namespace std;

const int NUM = 5;
int flag = 0;


//人类
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; };
};
void People::setRank(int mRank, int i)
{
rank[i] = mRank;
}
void People::setYuehui(bool mYuehui)
{
Yuehui = mYuehui;
}
void People::setBetter(int mBetter)
{
better = mBetter;
}
void People::setPresent(int mPressent)
{
present = mPressent;
}


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


while (true)
{
flag = 1; //设定全部脱单标记
//所有男士向自己最喜欢的女士表白
for (int i = 0; i < NUM; i++)
{
if (man[i].getYuehui() == false) //男士单身
{
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) //喜欢的女士单身
{
man[i].setYuehui(true); //男士改为约会状态
man[i].setPresent(girl); //设置现任为该女士
lady[girl].setYuehui(true); //喜欢的女士也更改为约会状态
lady[girl].setPresent(i); //设置现任为该男士
// cout << girl<<" "; //输出最喜欢的女士
}
if (lady[girl].getYuehui() == true) //喜欢的女士不单身
{
//女士通过比较与自己最喜欢的那位男士在一起
int before, now;
//通过循环判断现任和小三在女士心中的位置
for (int j = 0; j < NUM; j++)
{
if (lady[girl].getRank(j) == i)
{
now = j;
}
if (lady[girl].getRank(j) == lady[girl].getPressent())
{
before = j;
}
}
//如果女士喜欢现任
if (before < now)
{
//小三滚蛋吧~~
//man[i].setBetter(man[i].getBetter() + 1);
}
//女士喜欢
else if (before>now)
{
man[lady[girl].getPressent()].setYuehui(false); //现任变前任
man[lady[girl].getPressent()].setPresent(100); //变单身狗
man[i].setYuehui(true); //小三上位
man[i].setPresent(girl);

lady[girl].setPresent(i);
}
}
}
}

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

最后,看下结果吧~~
result

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

think2

think3

think4

Tony-Chen
2017.10.25

心的强大因为鉴定!

评论