超穩定配對和強穩定配對

Abstract

穩定結婚問題就是有n個男人和n個女人,他們每個人都將異性的n個 人依照想成為配偶的喜惡程度建立一個嚴格次序的配對志願,從中找出一 個配對,若沒有配在一起的任一對男女,他們都不會同時比已配對中的對象 較喜歡彼此,那麼它是一個穩定的配對.這個問題的每個實例都至少存在一 個穩定配對的解,且有已知的演算法可以求解.穩定室友問題就是將n個人 分成n/2對,其中每個人依照想成為室友的喜惡程度建立一個嚴格次序的志 願.要符合穩定配對的條件就是任何兩個沒有配在一起的人,他們都不會比 同時已配對中的室友較喜歡彼此.雖然這個問題不一定每個實例都存在一 個穩定配對的解,但也有已知的演算法可以解決.在上面兩個問題中,若不 限制配對志願要是嚴格次序地而容許無差別之志願,那麼穩定性可衍生成 三種方式:弱穩定,強穩定和超穩定.允許無差別喜惡次序的室友問題,已經 有文獻證明出弱穩定配對問題為NP-complete的,至於超穩定配對和強穩定 配對的室友問題則仍未解決.在本篇文章中,就針對這兩個問題提出了研究 結果和演算法. An instaance of the classical stable marriage problem is that of matching n mem and n women, each of whom has ranked the members of the opposite sex in strict order of preference, so that no unmatched couple both prefer each otherto their partners under the matching. For every stable marriage instance, thereexists at least one stable matching, and there is an efficient algorithms forfinding such a matching. The stable roommates problem is that of matching a setof n persons into n/2 disjoint pairs, each member of them ranks all the others in strict order of preference. A stable matching is one that no two unmatchedmembers both prefer each other to their partners under the matching. There is no guarantee that stable matchings exist in this case. In the classical versionof these two problems, each person must rank the members of the others in strict order of preference. If preference list allows indifferent, so that aperson may have ties in his/her preference list, the definition of stablity may be generalized in three ways, namely weakly stablity, strong stablity andsuper stablity. The question of finding weakly stable matching for roommatesproblem is NP- complete. In this paper, we describe algirithms to find whether astable matching exists in strong stablity and super stablity cases for roomates problem, and if so, it will find such a matching.