Document

クラス編成問題
•
•
•
•
•
•
総合講義のシステム
定式化：和の最大費用流
一番を100点に固定
やっぱり 7：3 に固定
情報科学演習第3
前期後期の組み分け
事の始まり：総合科目のクラス分け
・総合科目では、東工大の1年生全員をいくつかのクラス
に分ける
・学生がどの講義を受けたいか、という希望を取る
（第3希望まで調べる）
・それぞれの講義には定員がある
なるべく学生の希望が多くかなうようにクラス編成したい
歴史的な方法
1. 各学生の第1,2,3希望、を取り、それを札に書く
2. 各講義の紙を用意する
3. 定員の条件を満たすよに、エイヤと札を講義の紙に貼る
4. （うまく）希望どおりに分かれていたら終了
5. うんうんと考えて、札を入れ替え、 4 に戻る
手馴れた教授でも1日以上かかったそうな．．．
マッチング問題として見ると
・まずは簡単のため、3つの希望のうち1つがかなえば良い、
として考えて、希望がかなう学生の数を最大にする
 たんなる最大マッチング問題
・最大マッチングを求めるアルゴリズムを使うと、講義×定員
講義数を m、学生の人数を n として
O(n5/2/m) の時間で解ける
・学生数が n=2000 、講義数が m =10 でも、
n5/2/m ≒ 200,000,000 (2億)
最近のパソコンなら、1,2分で解けそう
学生
最適マッチング
・グラフ G = (V,E) と、枝の重み w：E →R が与えられたとき、
互いに隣接しない枝集合で、枝重み和が最大（最小）なもの
を求めよ
という問題が最適マッチング問題
・最適マッチングは、O(|V||E|) 時間で求められる
最大マッチング（枝数が最も多いマッチング）は、
O(|V|1/2|E|) 時間で求められる
最大重みマッチングとして見る
・まずは簡単のため、それぞれの枝に、学生の第1,2,3希望
に応じて重みをつけて、最大重みのマッチングを求める
 第1希望が優先されるようになる
・講義数を m、学生の人数を n とすると、
O(n3/m) の時間で解ける
・学生数が n=2000 、講義数が m =10 でも、
n3/m ≒ 10000,000,000 (100億)
・それでも、最近のパソコンなら、1,2時間で解けるでしょう。
割当問題として見る
・１つの講義に対応する頂点がたくさんあって、これがなんと
も無駄が多いので、割当問題で考える
・各仕事（講義）を受け持つ人（学生）の上下限
 それぞれの講義の最低・最高受講者数
・各人（学生）が受け持つ仕事（講義）の上下限
 両方とも 1
・各枝のコスト
 学生の希望順位に応じてつける
割当て問題のおさらい
・それぞれの人は、同時に受け持てる仕事の上下限がある
・それぞれの仕事は、受け持つ人の最低人数がある
・人 i が仕事 j を受け持つときに費用 aij がかかる
・これらを満たす、最低コストの、
人対仕事の割当を見つける問題
目的関数：
制約条件：
Σ aij xij
li ≦ Σj=1,…,m xij ≦ ui
l'j ≦ Σi=1,…,n xij ≦ u'j
・「単体法（シンプレックス法）で得られる最適解は、（条件の
係数が整数なら）必ず整数解になっている」
割当問題の求解時間
・割当問題を線形計画のソルバーで解くときの、計算時間を
算定しよう
・変数の数＝枝の数＝学生の数×希望数
・制約条件の数＝各頂点に対して3つ、各枝に対して2つ
＝
（講義の数＋学生の数 × （希望数+1 ））× 2
・学生数 n=2000 、講義数 m =100 でも、
－変数の数＝ 6000
－制約条件の数＝ 16100
・最近のパソコンなら、10分で解けるでしょう
実際に解いてみると
・ほとんどの場合、全ての学生は第3志望までの講義に割り
当てられる。つまり、「第3希望までのどこかに割り当てる問
題」と考えて差し支えない。
・枝重みは：
第1希望：70
第2希望：30
第3希望： 0
として、最大コストの割り当てを線形計画ソルバーで求める
何時間もかかって、そこそこの割当てしか得られなかったものが、
1時間で（ある意味で）最適・公平なものが得られるようになった
重みの自由化
・重みはこれでいいのか？
・どっちでもいいから、と適当に選んでいる学生と、熱心に
「ここに行きたい」と思っている学生が、同じ扱いなのはおかしい
・第1希望＋第2希望＝ 100
となるように、自由に選べるようにする
強い希望が通りやすくなる
重みの自由化 (2)
・そのうちに、まじめに考えて希望の配点をつける人が損を
するようになった
・楽な単位を取りたい学生が、
第１希望 100 ：第２希望 0
と書いて、無理やり配属されるように仕組むようになった
 70:30 と書いた人たちより優先される
第１希望＝100、第２希望＝0~100 とすることにした。
（ 100 : 100 というように書けるようになる）
（学生の持ち点は固定でなくなるが、どのみち、学生は100
点以内しかもらえない）
重みの自由化 (3)
・やっぱり、楽な単位を取りたい学生が、
第１希望 100 ：第２希望 0
と書いて、無理やり配属されるように仕組むようになった
やっぱり、第１希望＝70、第２希望＝30 で
固定することにした
・新しいルールを作ると、そのルールの抜け穴を狙う人が出
る
・抜け穴を狙う人がでてくると、ルールが変わる
・最適化は、ルールがあるところで成り立つので、
ルールの変更や、抜け穴のレベルには関与できない
理学セミナー（旧）
・学生が研究室２箇所に仮所属する
総合科目と違うところは、
・学生は３つの希望を出す。希望順位はなし
・前期・後期２つに分かれていて、各学生は希望の研究室に
前期か後期どちらかに所属する
・授業の内容から（どの本でゼミをするか決めるため）、各研
究室の前期と後期の人数はほぼ同じであってほしい
総合科目と同じように、クラス分けを数理的に行えるか
割り当て問題として、直接解く
・ A研究室を「前期のA研究室」｢後期のA研究室」と２つのク
ラスに分けて考えると、うまくいきそう
・同じ研究室に前期と後期に所属する学生が出てくる
可能性がある
・「研究室の、前期と後期の学生数がほぼ同じ」
という制約が守られない
この２つの問題点をどのように解決するかが鍵
２段階でクラス分けする
・第１フェイズで、総合科目と同じ方法で、学生を希望が通る数を
最大にして、各研究室に割り振る。前期後期は考えない
・第２フェイズで、各研究室の学生を、前期後期に割り振る
－各学生が、前期に１つ、後期に１つ、
研究室に割り当てられるようにする
－前期と後期の人数がほぼ同じようにする
第２フェイズをどのように解くか、が問題
２部グラフの色分け
・学生と所属研究室を結んだ２部グラフを作る
・このグラフを、サイクルと極大なパスに分解する
・それぞれのパスとサイクルを、交互に２色で塗り分ける
 パスの端以外の頂点では、枝２本が２色に塗り分けられる
・塗り分けた色で、前期か後期かを決める
（各枝は、学生・研究室の割当てに対応することに注意）
色分け法の正当性
・このグラフを、サイクルと極大なパスに分解する
 学生頂点は、パスの端にならない
 各研究室頂点を端とするパスは、高々１本
・それぞれのパスとサイクルを、交互に２色で塗り分ける
 学生頂点に接続する枝は２色
 研究室頂点に接続する枝は、両色同数か１つ異なる
計算時間
・グラフを、サイクルと極大なパスに分解する
 グラフ探索で、O（枝数＋頂点数）の時間でできる
・それぞれのパスとサイクルを、交互に２色で塗り分ける
 自明、O（枝数＋頂点数）の時間でできる
※ たいした手間ではない
まとめ
・総合科目のクラス分けは、線形計画法（割当て問題）で解
くと、すばやくできる
・学生の希望も、工夫すればうまく取り入れられるが、抜け
道ができてしまうようだ
・理学セミナー（旧）のクラス分け（前期後期がある）は、２段
階で分けるとうまくいく

Download Report