簡單的穩定婚姻匹配
一、相關的定義
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;
D=[a;B1];%%這裏輸出的是1到n編號女士對應的配偶的編號
End
輸入說明：這裏的A，B存儲的是編號，而不是第一喜歡的人
Matlab的文件輸入輸出問題：
四、案例的測試
用書上那個例子：見算法設計與分析基礎293頁
性別
編號
1
2
3
男士
Bob
Jim
Tom
女士
Ann
Lea
Sue
那麼男士的優先級順序為：女士的優先級順序為：
A= [2,1,3 B= [2,3,1
2,3,1 3,1,2
3,2,1] 2,3,1]
A的每一行分別是Bob,Jim和Tom心中對理想對象的優先級順序
同理，B的每一行分別是Ann,Lea和Sue心中對理想對象的優先級順序。
>>Match(A,B)
ans=
123
132
可以從結果分析，女士Ann和Bob結婚，女士Lea和Tom結婚，女士Sue和Jim結婚
和書上的結果是一樣的。
五、算法的局限性
1.輸出的局限性：該算法顯然會輸出一個穩定的匹配，在這個匹配中，所有的男生和他們的第一選擇相配，但是對女生並不如此。例如上面的從B中知道Ann最喜歡的是2號男生Jim，第三喜歡才是BOb,然後Bob第二喜歡的是Ann,，男生可以不斷去表白，選擇自己比較喜歡的男生，女生就只能比較男友和更換男友，這樣，女生可能等不到最喜歡的男友的表白，遊戲就結束了。
如果想要女生占優勢，那麼需要把女士和男生的輸入順序對換過來。
2.時間的效率性改進：為了快速求出所有的穩定匹配結果,提出了基於先序遍歷森林的快速枚舉算法。由Gale-Shapley算法的性質得到一個定理及其推論,利用得到的推論對算法做了進一步改進和優化。在滿足推論的特定條件下,提高了算法的執行效率
六、具體的應用
應用於測試資源匹配的婚姻穩定算法改進
下一代自動測試系統中將實現測試資源的動態分配,我們使用婚姻穩定(StableMarriage)算法來解決測試過程中測試資源與被測設備的匹配問題,使用擇偶傾向隊列縮減模型對求解典型"婚姻穩定"問題的Gale-Shapley(G-S)算法進行優化.該模型中使用擇偶傾向隊列描述婚姻穩定問題中匹配優先順序,該隊列會隨著算法進行逐漸縮短,在簡化數據規模的同時優化了處理婚姻穩定問題的G-S算法處理流程,改進後算法實現無效匹配請求的預先清除,從而使用後來請求優先的原則對匹配請求進行處理機制,對原有算法的時間空間成本實現了優化,適應了測試資源匹配任務的需求.
參考文獻：孫昱付少波張天培李長安《應用於測試匹配婚姻算法的優化改進》
