简单的稳定婚姻匹配 _匹配

一、相关的定义
1.有一个男士集合和一个女士集合。每个男士都有一个优先级列表，把女士按潜在结婚对象进行优先级排序。
同样的，女士也有一个对潜在结婚对象的优先级列表。
【简单的稳定婚姻匹配】婚姻匹配：
一个婚姻匹配Ｍ是一个包含ｎ个（ｍ，ｗ）对的集合，每一对的成员都按照一对一的模式从两个不相交的ｎ元素集合Ｙ和Ｘ中选出。也就是说，Ｙ中的每个男士ｍ都只和Ｘ中的一位女士ｗ配对，反正亦然。相当于一个二分图中，边来连接可能结婚的对象，两边的顶点代表Ｘ和Ｙ，婚姻匹配也是图中的一个完美匹配。
婚姻的稳定：如果在匹配Ｍ中，，男士ｍ和女士ｗ没有匹配，但他们都更倾向对方，而不是Ｍ中彼此的伴侣，那么（ｍ，ｗ）称为受阻对，如果婚姻匹配存在受阻对，那么我们说婚姻是不稳定的，如果不存在，则婚姻是稳定的。
二、稳定婚姻算法
输入：含有一个ｎ个男士的集合和一个ｎ个女士的集合，以及各自选择结婚对象的优先级。
输出：一个稳定的婚姻匹配关系
１.开始所有的男生和女士都是自由的。
２.如果存在自由男生，任选一个男生，执行下面步骤：
（１）求婚：选中的男士ｍ向ｗ求婚。ｗ是优先级最高的，而且没有拒绝过他。
（２）回应：如果ｗ是自由的，她接受求婚，如果ｗ不是自由的，她把ｍ和当前的配偶作比较，如果更喜欢ｍ接受求婚，否则拒绝。
３.返回ｎ个配对的集合。
三、代码的实现
因为这次的实现比较简单，所以用了matlab来编写函数
//dequeue函数
function[Q]=dequeue(Q)
n=size(Q,2);
fori=1:n-1
Q(i)=Q(i+1);
end
Q(n)=[];
end
//enqueue函数
function[Q]=enqueue(Q,x)
n=size(Q,2);
Q(n+1)=x;
end
//判断队列否为空
function[flag]=empty(Q)
flag=false;
ifsize(Q,2)==0
flag=true;
end
end
//判断男生和女士现有配偶的优先级顺序，如果排在该配偶前面
function[j]=shunxu(B,x,y)

%%输入一个矩阵的第x行,判断输入的值y在这行的位置
n=size(B,2);
j=1;
fori=1:n
j=j+1;
if(B(x,i)==y)
break;
end
end
end
//婚姻匹配函数
function[D]=Match(A,B)
%A,B分别是男女的优先选择矩阵
%返回稳定的匹配
n=size(A,2);
B1=zeros(1,n);%B1女士是否已经匹配，储存匹配的男士编号
fori=1:n
Q(i)=i;
end%Q为待匹配的男士的队列，初始化为全部男士
while(~empty(Q))
m=Q(1);Q=dequeue(Q);
fori=1:n
k=A(m,i);%m男士第i喜欢的是k女士
if(B1(k)~=0)%如果k女士已经匹配了
if(shunxu(B,k,B1(k))>(shunxu(B,k,m)))%且如果第m个男士的优先级比现有配偶要高
Q=enqueue(Q,B1(k));
B1(k)=m;
break;
end
else%如果没匹配
B1(k)=m;
break;
end
end
end
a=1:n;

以上关于本文的内容，仅作参考！温馨提示：如遇专业性较强的问题（如：疾病、健康、理财等），还请咨询专业人士给予相关指导!

「辽宁龙网」www.liaoninglong.com小编还为您精选了以下内容，希望对您有所帮助：