稳定婚配问题的uml建模和编程实现

文件:	StableMarriage.rar
大小:	59KB
下载:	下载

稳定婚配问题的uml建模实现以及python的实现代码。

稳定婚配问题：
    假设有N个男人和N个女人，每个人都希望从N个异性中选择自己的配偶。假定每个人都对N个异性以自己的喜好进行了排序，以此作为选择配偶的基础。当给定一种婚配方案，即为每人指定一个配偶后，若存在一个男人和一个女人不是配偶，但该男人喜欢该女人胜过其配偶，同时该女人喜欢该男人也胜过其配偶，则该婚配方案为不稳定的。安排稳定的婚配方案称为稳定婚配问题。
    进一步，在每个人对N个异性的喜好排序中增加喜好权重Ai{i=1..n; 0 < ai < a; a1+a2+...+an=1}，定义“个人满意度”为配偶相互喜好权重之和，“整体满意度”为婚配方案中全部个人满意度之和，若存在不同的稳定婚配方案时，则存在整体满意度最高的稳定婚配方案。

    设计算法，找出所有稳定婚配方案，并找出整体满意度最高的一种方案。


附部分python程序代码片段：
main.py

#!/usr/bin/env python
# -*- coding: gb2312 -*-

import random

import Person
import StableMarriage

def main():
    random.seed()

    f = lambda sex : map( lambda x: Person.Person( sex ), range(0, 3) )
    males = f( Person.Person.Sex.male )
    females = f( Person.Person.Sex.female )

    def gen_pre_ratio(group, opp_group):
        for member in group:
            map( lambda x: member.appendPreRatio( x.getSelfID(), random.randint( 1, 10 ) ), opp_group )
            
    gen_pre_ratio( males, females )
    gen_pre_ratio( females, males )

    aStableMarriage = StableMarriage.StableMarriage( males, females )
    aStableMarriage.Compute()

    aStableMarriage.PrintHighestSchemes()
    aStableMarriage.PrintAllSchemes()

if __name__ == '__main__':
    main()