ほぼPython

Not技術ブログBut勉強ブログ 内容には誤りがあることが多いです

オタクイベント組合せ問題(集合被覆問題を貪欲法で解く)

さて、あなたはアニメオタクです。

今年の春には、各地でオタクイベントが開催されます。開催されるオタクイベントとそのイベントで開かれるブースは以下の通りです。

events['みんな大好き名作大集合!'] = set(['SAO','シュタゲ','ルルーシュ','進撃'])

events['SFアニメの金字塔'] = set(['攻殻機動隊','シュタゲ','涼宮ハルヒ'])

events['不朽の名作'] = set(['SAO','black lagoon','東のエデン','スピードグラファー'])

events['ゆるいべんと'] = set(['はがない','NEW GAME','いちごましまろ','日常'])

events['つくろうゲーム'] = set(['冴えカノ','NEW GAME','NHKにようこそ'])

events['タイムリープしちゃうぞ'] = set(['シュタゲ','リゼロ','まどマギ'])

events['異世界転生'] = set(['リゼロ','幼女戦記','gate','このすば'])

もちろん、あなたは熱心なアニメオタクなのでこれらのイベントすべてに参加したいです。
しかし、今年、あなたは大学の卒業研究が忙しく、すべてのイベントに参加する時間はありません。

そこで、あなたはどうしても行きたいブースを選ぶことにしました。

あなたが選んだブースは以下の通りです。

booth_needed =set(['SAO','幼女戦記','シュタゲ','冴えカノ','東のエデン','NEW GAME','black lagoon','リゼロ','ルルーシュ'])

これらのブースすべてに行くことが出来れば、あなたは満足します。

あなたは最低いくつのイベントに参加すれば満足することができるでしょうか?


・・・というような問題のことを集合被覆問題と言います。

今回のように数が少ない場合は全通りを考えていけば答えは出ますし、自分で考えても答えが出ますが、もっと複雑になると、現実的な時間で厳密な解を求めることは困難なので、近似的な手法を用いて解を求めます。その方法の一つが貪欲法と呼ばれるものです。貪欲法とは各ステップで局所的な最適解を求める方法のことです。

それでは、今回の問題をpythonで貪欲法のアルゴリズムを実装することにより解きます。今回の貪欲法は簡単に言うと集合に対してもっとも大きな部分集合をどんどん引いていくアルゴリズムとなっています。

while booth_needed:
    best_event = None 
    booth_covered = set() 
    for event, booth in events.items():
        covered = booth_needed & booth
        if len(covered) > len(booth_covered):
            best_event = event
            booth_covered = covered
    booth_needed -= booth_covered 
    best_events.add(best_event) 

print(best_events)

結果は{'異世界転生', '不朽の名作', 'つくろうゲーム', 'みんな大好き名作大集合!'}となりました。

あなたは7つのオタクイベントのうちこの4つに参加すれば満足できるようです。
これで、浮いた時間を卒業研究に充てることもできますね。