Gale-Shapley算法

算法设计

MATLAB实现

clear;

men_rank = [1,2,3;1,3,2;3,2,1]; %men对women的排名，如men1为[1,2,3]，则men1最喜欢women1，其次women2，最后women3
women_rank = [1,2,3;3,1,2;3,2,1]; %同理
[relation] = Gale_Shapley_Funcmen_rank,women_rank);%稳定解

function [relation] = Gale_Shapley_Funcmen_rank,women_rank)
[men_num,women_num] = sizemen_rank); %个数
men_free = onesmen_num,1); %当前men状态
women_free = oneswomen_num,1); %当前women状态
visited= zerosmen_num,women_num); %是否选择过
relation = zerosmen_num,women_num); %关系矩阵

while 1
    for m = findmen_free==1)' %行向量
        for w = men_rankm,:) %行向量
            if visitedm,w) == 0 && women_freew) == 1  %没有选择过，且women free
                men_freem) = 0;women_freew) = 0;relationm,w) = 1; visitedm,w) = 1;
                break;
            elseif visitedm,w) == 0 && women_freew) == 0  %没有选择过，但women not free
                m_now = findrelation:,w)==1);
                if findwomen_rankw,:) == m_now) > findwomen_rankw,:) == m) %判断m是否排名靠前
                    relationm_now,w) = 0;men_freem_now)=1;men_freem) = 0;women_freew) = 0;relationm,w) = 1; visitedm,w) = 1;
                    break;
                end
            end
        end
    end
    if isemptyfindmen_free==1,1)) || isemptyfindwomen_free==1,1))%men or women 全部 not free
        break;
    end
end
end

参考

维基百科Gale-Shapley算法