この問題はどう解けばいいんだ？
最近作ってるシステムで、どうしてもどう解いていいのかがわからなくて行き詰っていた問題があったのでpostしてみる。
作っているのは心理学実験の参加者募集システムで、問題は参加希望者を最適に実験枠に割り振るためのアルゴリズム。
問題の状況を簡単にまとめると図1のような感じ。
| 実験枠 | A 3-5人 |
B 4-6人 |
C 3-5人 |
D 4-6人 |
E 3-5人 |
… … |
|---|---|---|---|---|---|---|
| 参加希望者 | ||||||
| 1 | ○ | × | ○ | × | ○ | … |
| 2 | × | ○ | ○ | ○ | × | … |
| 3 | ○ | ○ | ○ | × | × | … |
| 4 | × | ○ | ○ | × | ○ | … |
| 5 | ○ | × | × | ○ | ○ | … |
| ： | ： | ： | ： | ： | ： |
いくつかの実験枠と何人かの参加希望者がいて、参加希望者にはどの枠なら参加可能かどうかを答えてもらう。そして、それぞれの枠には最少催行人数と最大収容人数が決まっている。このような状況のときに、適切に参加希望者を割り振って、最少催行人数と最大収容人数を満たす枠の数を最大化するにはどうすればいいのだろうか。全ての枠が条件を満たす必要はないし、全ての参加希望者を使い切る必要もない。
こういう問題を解くアルゴリズムってあるのかな？組み合わせ最適化問題？安定結婚問題？瓶詰め問題？
数学は苦手だしアルゴリズム系の知識もないからわからーん。
追記
ありがたい！
スポンサーサイト
関連記事
トラックバック URL
- http://liosk.blog103.fc2.com/tb.php/102-3adae455
トラックバック
- 前回のエントリの問題を詳述
-
前回のエントリで、僕では解けない問題を書いてみたんだが、書き方が曖昧であまり伝っていないみたいなので、少し正確に書いてみることにし...
- 2008-04-21
- 発信元: 文系大学的IT系の悲哀
- 前回と前々回のエントリーの問題を総当りで
-
前回と前々回のエントリで書いた問題を、Perlで総当りで解こうとしてみた。使ったコードは最後に添付。
実行開始から7時間半経過したけど未だ...
- 2008-04-22
- 発信元: 文系大学的IT系の悲哀
- 昨日の問題を遺伝的アルゴリズムっぽく
-
昨日の問題[1][2][3]を、遺伝的アルゴリズムのようなもので解いてみた。解くのに使ったPerlコードは最後に添付。
一応、前々回のエントリで提示...
- 2008-04-22
- 発信元: 文系大学的IT系の悲哀
