線形割当問題

2025年4月28日 (月) 投稿者: メディア技術コース

メディア学部の大淵です。

私の研究室では、卒業研究を行う4年生全員に、個人用の机を割り当てています。4月からは新しい4年生が来るので、それぞれどの席に座ってもらうかを決めなければなりません。それぞれの希望を聞いても、最適な割り当てを決めるのはそんなに簡単ではありません。

そこで、席決めの前に、新4年生の皆さんにアンケートを取ります。人数分の机に番号を振って、それぞれ第1希望から順位を付けてもらうのです。そのうえで、全員が割り当てられた席の「順位の和」が最小になるようにすれば、みんなの満足度も高まるだろうと思われます。

では、そんな割り当てはどうやって求めればよいでしょうか。N人の人の座席の割り当て方はNの階乗通りあるので、しらみつぶしに当たるのはちょっと大変です。でも、この問題は「線形割当問題」という名前で古くから研究されていて、しらみつぶしよりずっと効率の良いアルゴリズムも知られています。そして、そんなアルゴリズムを自分で実装するまでもなく、世の中には線形割当問題を解いてくれるライブラリも存在します。なので、やるべきことは、アンケート結果を整理して、ライブラリ関数を呼び出すプログラムを書くだけです。

Assign1

試しにやってみました。図の上側はアンケート結果です。aからjの10人が、AからJの10個の座席に希望順位を付けています。図の下側は、scipy.optimize.linear_sum_assignmentという関数を使ってこれを解いてみた結果です。順位の和は19で、これより小さい解はありません。

ただ、この解を見ると、bさんだけが第8希望に割り当てられてしまって、ちょっとかわいそうですね。こういうときは、最小化の対象をちょっと変えてあげます。順位の和の代わりに、「順位の2乗の和」を最小化することにすると、どうなるでしょうか?

Assign2

こちらがその結果です。第2希望以下に割り当てられる人は増えましたが、第8希望なんていうかわいそうな人はいなくなりました。

それでもまだ第5希望の人がいてかわいそう、と思うかもしれませんが、残念ながらこのアンケート結果では、全員を第4希望以内に割り当てることはできません。なぜそうなるかの証明は皆さんへのクイズとしますので、興味がある人は考えてみてください。

AltStyle によって変換されたページ (->オリジナル) /