研究室配属アルゴリズム

このページでは,お茶の水女子大学理学部情報科学科の卒業研究の配属先を決めるために 2013年に導入された,研究室配属アルゴリズムを紹介します.

アルゴリズムと実行手順

  1. 各研究室ごとの順位リストを準備する.
    fig1
    各研究室ごとに,上から下へ順位の良い順に並べている.

  2. 各学生の希望を調べる.(表は,第3希望までとった例.)
    fig2

  3. 各学生の第1希望を調べる. 順位の高いほうから定員までは仮採用. それ以外は落選.
    fig3
    オレンジ:仮採用. 水色:落選. 灰色:リストから除外.

  4. 以降,次の3つのルールで希望者を選定.
    1. 定員を満たすまで無条件に受け入れる. fig4-1
      A研究室落選の「さる」の第2希望はE研究室. E研究室は定員を満たしていない. したがって,E研究室で「さる」を仮採用する.

    2. 定員に達していたら,新規希望者と仮採用の学生と比較. 新規希望者の順位が上なら仮採用.仮採用だった学生の最下位は落選. fig4-2
      A研究室落選の「ひつじ」の第2希望はB研究室. B研究室は定員に達しているが,仮採用中の「いぬ」より 新規希望者の「ひつじ」のほうが順位が上. したがって,B研究室で「ひつじ」を仮採用する. 「いぬ」は落選で,第2希望へ回る.

    3. 仮採用の学生より新規希望者の順位が下なら落選. fig4-3
      B研究室落選の「いのしし」の第2希望はE研究室. E研究室は定員で,「いのしし」の順位は仮採用の学生よりも下. したがって「いのしし」は落選で,第3希望へ回る.

    落選者に関して,これらのルールのもとで選定を繰り返す.

  5. 希望研究室をすべて落選なら 「未決定」状態とする. fig5
    黄色:未決定. 「いのしし」は第3希望も落選なので未決定が確定.

  6. 全員が「仮採用」か「未決定」になったら仮採用の学生を正式に配属決定として終了. fig6
    ピンク:決定. 黄色:未決定 ⇒第2ラウンドへ.
    第2ラウンドでは,定員を満たしていない研究室から選ぶ.

まとめと補足