0
我正在閱讀算法的書,遇到了穩定匹配問題。我想到一個問題,我很好奇,但這本書沒有回答。 在每個SMP中都可能總是有一對,每個最喜歡另一個? 就像在經典婚姻的例子。是否總是有一對女性和一個男性,他們的優先級排在前列?穩定匹配問題
我正在閱讀算法的書,遇到了穩定匹配問題。我想到一個問題,我很好奇,但這本書沒有回答。 在每個SMP中都可能總是有一對,每個最喜歡另一個? 就像在經典婚姻的例子。是否總是有一對女性和一個男性,他們的優先級排在前列?穩定匹配問題
一個反例:
M1 prefers W1.
M2 prefers W2.
W1 prefers M2.
W2 prefers M1.
沒有可能的配對,其中對的兩個成員都得到他們的最高優先。
+1爲什麼如果他們不關心伴侶,他們必須結婚? :) – 2010-10-01 00:04:11
謝謝,我會考慮如何證明它是正確的,而不是隻提出一個反例。 – user299648 2010-10-01 00:14:52
+1,反轉邏輯對於這些邏輯問題總是一個很好的竅門。 – Wrikken 2010-10-01 00:41:22