書き込み対象の日記
Permanent Link: http://www.misho-web.com/diary/200804.html#Diary21
LiosK問題に対する試案
ハチロク世代のSkype chatで話題になっていたLiosK問題について考えてみた。
Algorithmとしては，
- その時点で参加可能な実験が少ない人から順番に，その人が許容する実験の中でその時点での不足人数が最も少ない実験に割り振る。
- 全員（または全実験）の割り振りが終了したら，その時点で人が割り振られている実験のうち最も不足人数が大きいものを，実施取りやめにする。どの実験を実施取りやめにするかについてはあまり考えていない。要検討。
- 充足していない実験に割り振られている人を解放し，再び最初から繰り返す。全員を解放してもいいかもしれないが，落とし穴がある気がする。
という構成である。
これが本当に最小なのかはものすごぉぉぉぉく自信がない。最初のstepについては問題ないが，実施取りやめにするものの選び方が微妙である。 とりあえずsample codeを以下に掲載しておく。
あ……program間違えてた……。
ってわけで修正しましたｗｗ。
が，上述のalgorithmをただしく実装しています。
liosk_pl_20080421b.txtの方では，sample code中のUser 0..8だけをExp 0..9に割り振った時に，「実験数は2」と返されますが，最新版ではちゃんと正しい値「3」を返します。そのほか色々なtest caseを検証しました。
【 Commentを書き込む 】 ／ [ Trackback URL : http://www.misho-web.com/diary/Trackback/20080421 ]
