Other Python

最佳CP算法

由光棍节想到的算法问题。假设一个学校里有100个少年和100个少女,少年和少女心中都有一个好感度数值排列表,现在我们来做CP(coterie partner),按照正常的剧情展开,勇敢的少年们去向少女们告白,大致流程是这样:

第一天,所有少年都去找排在他们好感度列表第1位的少女表白。告白结束后,少女如果只收到一个少年的告白,那么就和这个少年交往。如果收到多于一个少年的告白,就和其中她最喜欢的少年交往,把其他少年都拒绝掉。

第二天,所有在第一天被发好人卡的少年们,接着发起告白行动,去向排在自己好感度列表第2位的少女告白。告白结束后,如果某个少女已经在交往中,但是又有一个她更喜欢的少年来向她告白,那少女就把原来那个少年甩掉,再和这个她更喜欢的少年交往。

第三天,少年们继续发起告白运动,包括第一天告白成功,但第二天被挖了墙角的,接着向还没有拒绝过他的女生中他最喜欢的那个告白。

如此直到CP结束,我们可以得到一个稳定的CP,稳定的概念是,对于任何一对恋爱关系——比如少年A和少女A——都不存在少年A对少女B的好感度大于少女A,或是少女B对于少年A的好感度大于她现任的男朋友少年B的情况。以上就是1962年美国数学家戴维·戈尔(David Gale)和劳埃德·夏普利(Lloyd Shapley)对稳定婚姻问题研究出的Gale & Shapley算法了。经过计算发现,这种情况看似少女们拥有自主选择权,真正收益的其实是勇往直前的少年们,他们总能追到自己好感度列表中相当靠前的少女。当然,这个算法最主要是解决诸如学生对于其意向学校的选择,座位的安排,这类问题的实际可行性。

Algorithm[Python]

前面的描述有点复杂,先将其简化,假设有三男三女,互相好感度如下:

guyprefers = {
 'kyou':    ['haruhi', 'yuki', 'mikuru'],
 'itsukl':  ['haruhi', 'mikuru', 'yuki'],
 'shamisen':['mikuru', 'yuki', 'haruhi']}
galprefers = {
 'haruhi': ['kyou', 'itsukl', 'shamisen'],
 'yuki':   ['shamisen', 'kyou', 'itsukl'],
 'mikuru': ['kyou', 'itsukl', 'shamisen']}
#顺手从dict中先取得少年和少女的名字列表,之后会用到
guys = sorted(guyprefers.keys())
gals = sorted(galprefers.keys())

接下来按照前面的流程,开始CP

guyprefers2 = copy.deepcopy(guyprefers)
galprefers2 = copy.deepcopy(galprefers)
engaged = {}

guysfree = guys #少年们还没有告白,都是单身
while guysfree:
    guy = guysfree.pop(0)#取出第一个少年
    guyslist = guyprefers2[guy]#取得少年的好感度list
    gal = guyslist.pop(0)#取出第一个少女
    fiance = engaged.get(gal)
    if not fiance:#如果取不到值,则是单身
        engaged[gal] = guy #接受少年的告白 
        print("  %s and %s" % (guy, gal))
    else:
        # 算法的核心,比较少年在少女们心中的好感度排名
        galslist = galprefers2[gal]
# 如果来告白的少年好感度高于现任男友,则抛弃掉现任男友
        if galslist.index(fiance) > galslist.index(guy):
            engaged[gal] = guy
            print("  %s dumped %s for %s" % (gal, fiance, guy))
            if guyprefers2[fiance]:
                guysfree.append(fiance)#被抛弃的少年进入单身列表
# 如果来告白的少年好感度低于现任男友,则发卡拒绝
        else:
            guysfree.append(guy)#被发卡的少年进入单身列表
    guysfree.append(guy)

Coding & Run Result

import copy

guyprefers = {
 'kyou':    ['haruhi', 'yuki', 'mikuru'],
 'itsukl':  ['haruhi', 'mikuru', 'yuki'],
 'shamisen':['mikuru', 'yuki', 'haruhi']}
galprefers = {
 'haruhi': ['kyou', 'itsukl', 'shamisen'],
 'yuki':   ['shamisen', 'kyou', 'itsukl'],
 'mikuru': ['kyou', 'itsukl', 'shamisen']}

guys = guyprefers.keys()
gals = galprefers.keys()

 
def cp():
    guysfree = guys
    engaged  = {}
    guyprefers2 = copy.deepcopy(guyprefers)
    galprefers2 = copy.deepcopy(galprefers)
    while guysfree:
        guy = guysfree.pop(0)
        guyslist = guyprefers2[guy]
        gal = guyslist.pop(0)
        fiance = engaged.get(gal)
        if not fiance:
            engaged[gal] = guy
            print("  %s and %s" % (guy, gal))
        else:
            galslist = galprefers2[gal]
            if galslist.index(fiance) > galslist.index(guy):
                engaged[gal] = guy
                print("  %s dumped %s for %s" % (gal, fiance, guy))
                if guyprefers2[fiance]:
                    guysfree.append(fiance)
            else:
                guysfree.append(guy)
    return engaged

print('\nEngagements:')
engaged = cp()

print('\nCouples:')
print('  ' + ',\n  '.join('%s is engaged to %s' % couple
                          for couple in sorted(engaged.items())))

运行结果:

Engagements:
itsukl and haruhi
shamisen and mikuru
haruhi dumped itsukl for kyou
mikuru dumped shamisen for itsukl
shamisen and yuki
Couples:
haruhi is engaged to kyou,
mikuru is engaged to itsukl,
yuki is engaged to shamise
avatar

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

  Subscribe  
最新 最旧 得票最多
提醒
动画
游客

很不错

血衫非弧
游客

太疼了~~~~~~~

血衫非弧
游客

长门还是和了三味线~~~~话说只有后宫才是正道~~~~