Stable Matching 稳定匹配 婚姻算法 shapley 算法
作者:jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4051286.html
稳定匹配问题:有N男N女,每个人对于异性都一个排名,先需要得到一种稳定的匹配,即不会出现一个匹配中的人与另一个匹配中的异性对对方的排名均高于目前配对的人的排名。
shapley算法:
每次取出一个单身男生,让他向没有拒绝过她的女生中其排名最高人表白,若该女生没有对象则配对成功,否则与其当前的对象排名进行对比,如果当前对象排名较高,则拒绝表白男生,否则dump掉目前对象。直到没有单身男子为止。
伪代码如下:
for m = 1 to M do
partner[m] = NULL
end for
for w = 1 to W do
partner[w] = NULL
end for
while TRUE do
if there is no man m such that partner[m] = NULL then
return;
end if
select such a man m arbitrarily;
w = the first woman on m′ s list to whom m have not yet proposed;
if partner[w] == NULL then
partner[w] = m; partner[m] = w;
else if w prefers m to state[w] then
partner[partner[w]] = NULL; partner[w] = m; partner[m] = w;
else
; //do nothing means simply rejecting m;
end if
end while
实现时,可以把单身男生放入一个队列中,每次取出一个进行配对。另外为了在O(1)时间内找到第i个男生的第j喜欢的女生,令排名矩阵ManMat[i][j]表示男生i的第j喜欢的女生为ManMat[i][j]。为了在O(1)的时间内找到第i个女生对第i个男生的排名,令排名矩阵WomanMat[i][j]表示第i个女生对与第j个男生的排名为WomanMat[i][j]。这两个矩阵并不对称。
代码如下:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <map>
#include <fstream>
#include <queue>
#define MAXNUM 1000
using namespace std;
int ManMat[MAXNUM][MAXNUM];//man i's jth favourate woman is ManMat[i][j]
int WomanMat[MAXNUM][MAXNUM];//woman i's to the man j's rank is WomanMat[i][j]
int ManPartner[MAXNUM];//man i's partner woman is ManPartner[i]
int WomanPartner[MAXNUM];//woman i's partner man is WomanPartner[i]
int ManPropose[MAXNUM];//ManPropose[i] means the number of man i's propose
void shapley(int n)
{
memset(ManPartner, -, sizeof(ManPartner));
memset(WomanPartner, -, sizeof(WomanPartner));
queue<int> manqueue;
for( int i = ; i < n ; i++ )
{
manqueue.push(i);
}
int i = ;
while()
{
if( manqueue.size() == )
{
return;
}
i = manqueue.front();
int like = ManMat[i][ManPropose[i]];
ManPropose[i]++;
if( WomanPartner[like] == - )
{
WomanPartner[like] = i;
ManPartner[i] = like;
manqueue.pop();
}
else if( WomanMat[like][WomanPartner[like]] > WomanMat[like][i] )
{
ManPartner[WomanPartner[like]] = -;
manqueue.push(WomanPartner[like]);
WomanPartner[like] = i;
ManPartner[i] = like;
manqueue.pop();
}
}
}
最新文章
- sqlalchemy入门记录
- maven2 com.jhlabs.imaging 01012005 maven安装jar包imaging命令
- Date和Calendar时间操作常用方法及示例
- ensure LANG and/or LC_* environment variables are set correctly
- [游戏学习29] Win32 图像处理1
- java框架篇---spring IOC依赖注入
- 对象创建型模式------Singleton(单例模式)
- Node.js RESTful API
- tomcat加载时报The web application [/dmscs] created a ThreadLocal with key of type
- ASP.NET MVC C#知识点提要
- 方法的标签_With携带
- mui开发app之webview是什么
- codeforces 558 E A Simple Task
- 使用Axure做验证码之获取验证码(一)
- VS2017+mysql5.7 连接数据库生成实体
- java监控工具VisualVM
- maven中经常使用的插件
- 20155301 2016-2017-2 《Java程序设计》第7周学习总结
- BZOJ.4031.[HEOI2015]小Z的房间(Matrix Tree定理 辗转相除)
- OpenCV 学习笔记 04 深度估计与分割——GrabCut算法与分水岭算法