HACK TO THE FUTURE 2022 予選に参加しました。
問題はProject Leader。推定とスケジューリングの合体問題です。
提出823人中、暫定テスト14位、システス12位でした。
問題
メンバー20人にタスクを振り分けて、プロジェクトを最速で完了させてね。
タスクに必要な能力値は分かるけど、メンバーの能力値は分からないから完了日数から推測してね。
能力の種類は10～20種類あって、その不足分の総和±3日が完了日数になるよ。
あと、前提タスクを終わらせないと着手できないタスクもあるよ。
考察
やたらたくさんの要素が絡み合っている感。
推測部
複数の値と、確率で出てくる結果から元の値を推測する…これはMM121 SoccerTournamentじゃな？ 可能性を絞り込むという観点では、人狼知能にも通じるものがありそう。
日数の求め方的に、メンバの能力を上回る難易度のタスクをぶつけないと正確な能力値は出せない。簡単なタスクしか与えないと、過小評価している状態が続く。過小評価して簡単なタスクしか与えないと、挽回の機会が与えられない。*1序盤は現評価より難しいものを与えるか、過大評価にする必要がありそう。
SATソルバみたいなものがあればかなり正確な値が出る可能性があるけど、自分の能力的に不可なのと、振れ幅の状態も扱ってみたいので、焼き鈍しかな…。
スケジュール部
クリティカルパスは1つの重要ポイントになりそう。
ただPERT図を書こうにも、能力が分からないと実日数が分からないし、そもそも誰が担当するかで日数も変わるので一筋縄では行かない。
上手く出来るなら、クリティカルパスは優秀なメンバに割り当てて最速で終わらせて、脇で他のメンバがクリティカルじゃないタスクを終わらせる感じかなぁ…。
しかし、そもそも愚直解が強すぎる。ID順に処理すれば、なんとなく深さがある場所から処理できるのでなんとなくクリティカルパスをカバーできるし、優秀なメンバは回転率が高く、多くのタスクを請け負うので、なんとなくクリティカルパスを担当する確率が高い。その特徴を増幅させる方向かな。
実装
推測部
焼き鈍し。
近傍は[skill+1、skill-1]を1～2回変形。
スコアはペナルティとして、日数破綻の合計値。
ただ状態1つだけで持つと、確度が高い状態なのか振れ幅がある状態なのか分からない。
スコアに[過去の必要能力の最高値+3]をターゲットにする補正をかけてみるも、局所解にはまるのかあまり芳しくなく、さらに低能力部分の推測精度が低かった。
そこで初期スキルの異なる4つの能力値候補を用意し、それぞれ焼き鈍して平均値を取った。各能力の上限値はMin(15, 過去の必要能力の最高値+6)として、日数破綻のみを評価値とした。
これで振れ幅部分は破綻しない範囲で自由に上下するので、実能力より多少高く見積もれるようにしつつ、それが破綻する場合は実能力に合わせるという挙動ができた。
また、スキルを測定するためのタスク割り当てを行った。4つの能力値候補でそれぞれ日数計算を行い、日数差が大きいものはより多くの可能性を否定できるもの（＝多くの情報を得られるもの）として優先度を上げた。上の画像の例で言うと、CとC++の必要技能値だけが高いタスクを与えれば、Type3＞Type1・2＞Type4の順で適正が高く日数が短くなる。結果の日数によって各TypeのC,C++の部分だけ推定が進み実際の値に近づき、他の能力はばらついた状態を保てる。*2
1点問題があるとすると、4パラメータをそれぞれ焼きなますので、焼く回数は1/4になる。問題点が出ないよう上手く管理できるなら4つに分ける必要はなく、弱者の戦略という感じ。
スケジュール部
何も分からん。
Rが小さいケースでは前提タスクはあまり気にしなくていいのだが、Rが大きいケースでは気にしないと多数の手が空いてもったいない状態になる。なるべく全員の作業日数を揃えたいが、前提タスクも含めて計算するのは大変。
焼き鈍しなど色々試してみたが最終的には、全タスクを能力値ALL9として子を含めた作業時間を計算し、原則それが多い順に作業することにした。*3
メンバへの割り当ては、タスクを上記の優先順に貪欲に割り当てる。評価値はペナルティで、各メンバの[割り当て済み作業日数^2]の合計とした。*4
割り当て時にタスクの並列化や前提タスクについては一切考慮していない。のだが、実はこの方針もなかなかに強力と考えている。並列にすべきタスクというのは同時に終わらせたいタスクで、何が該当するかといえば、同じ子タスクを持つか、プロジェクト終了間際の2パターンしかない。*5このどちらも並列したいタスク同士で[子を含めた作業時間]が近くなる傾向があり、割り当て順序も近い。なのでその1つを割り当てられたメンバは割り当て済みの作業日数が長くなり、並列したいタスクが割り当てられる確率は減るという寸法。
前提タスクのせいで空きが出るのはもう仕方ないものとして、手が空いた時は、着手できるタスクのうち計画が乱れないもの（自分の次のタスクが遅れない、本来の担当者より早く終わらせる）だけ隙間で行うようにした。
実は一番何も分からないのは序盤～中盤の能力推定と絡めたタスクの決め方で、何回か学習専用に割り当て無視で行うのがいいのか、非効率でもクリティカルパスを崩しながら能力推定するべきなのか、軽いタスクで刻んでいくべきなのか、重めのタスクで振れ幅を確認しに行くのがいいのか…。一切分からなかった。とりあえず試した中では6タスクを割り当てせずに全タスクから選ぶのが良さそうだった。バタフライエフェクト的に終盤まで響くので、本当に何が良いのやら。
感想
愚直解が『上手く行く性質』を持っていて、それを壊さないように新しい指針を入れたり改良する必要がある問題だったと思います。下手をすると既存の性質を壊してスコアが落ちるので、「ぼくのかんがえたさいきょうのほうしん」で気軽にスコアを伸ばして楽しむというタイプではなく、自分含めて苦しんでいる人が多く感じました。
制御するためのパラメータの多さからゲームAIに例えている人もいましたが、個人的には何故それが上手く行くのかを理解しないと前に進めない問題で、謎解きっぽいなーと思いました。
あとビジュアライザが過去HTTF比でもAHC比でも超速で進化してる感があって凄かったです。
