クラス編成問題クラス編成問題 総合講義のシステム 定式化：和の最大費用流 一番を 100 点に固定 やっぱり 7 ： 3 に固定 情報科学演習第 3 前期後期の組み分け.

Presentation on theme: "クラス編成問題クラス編成問題 総合講義のシステム 定式化：和の最大費用流 一番を 100 点に固定 やっぱり 7 ： 3 に固定 情報科学演習第 3 前期後期の組み分け."— Presentation transcript:

1 クラス編成問題クラス編成問題 総合講義のシステム 定式化：和の最大費用流 一番を 100 点に固定 やっぱり 7 ： 3 に固定 情報科学演習第 3 前期後期の組み分け

2 事の始まり：総合科目のクラス分け事の始まり：総合科目のクラス分け 総合科目では、東工大の 1 年生全員をいくつかのクラ スに分ける 学生がどの講義を受けたいか、という希望を取る （第 3 希望まで調べる） それぞれの講義には定員がある なるべく学生の希望が多くかなうようにクラス編成した い

3 歴史的な方法 1. 1. 各学生の第 1,2,3 希望、を取り、それを札に書く 2. 2. 各講義の紙を用意する 3. 3. 定員の条件を満たすよに、エイヤと札を講義の紙に 貼る 4. 4. （うまく）希望どおりに分かれていたら終了 5.4 5. うんうんと考えて、札を入れ替え、 4 に戻る 手馴れた教授でも 1 日以上かかったそうな．．．

4 マッチング問題として見るとマッチング問題として見ると まずは簡単のため、 3 つの希望のうち 1 つがかなえば良 い、として考えて、希望がかなう学生の数を最大にす る   たんなる最大マッチング問題 最大マッチングを求めるアルゴリズムを使うと、 講義数を m 、学生の人数を n として O(n 5/2 /m) の時間で解ける 学生数が n=2000 、講義数が m =10 でも、 n 5/2 /m ≒ 200,000,000 (2 億 ) 最近のパソコンなら、 1,2 分で解けそう × 講義 × 定員 学生

5 最適マッチング最適マッチング グラフ G = (V,E) と、枝の重み w ： E →R が与えられたと き、互いに隣接しない枝集合で、枝重み和が最大（最 小）なものを求めよ という問題が最適マッチング問題 最適マッチングは、 O(|V||E|) 時間で求められる 最大マッチング（枝数が最も多いマッチング）は、 O(|V| 1/2 |E|) 時間で求められる

6 最大重みマッチングとして見る最大重みマッチングとして見る まずは簡単のため、それぞれの枝に、学生の第 1,2,3 希 望に応じて重みをつけて、最大重みのマッチングを求 める  第 1 希望が優先されるようになる 講義数を m 、学生の人数を n とすると、 O(n 3 /m) の時間で解ける 学生数が n=2000 、講義数が m =10 でも、 n 3 /m ≒ 10000,000,000 (100 億 ) それでも、最近のパソコンなら、 1,2 時間で解けるで しょう。

7 割当問題として見る割当問題として見る １つの講義に対応する頂点がたくさんあって、これが なんとも無駄が多いので、割当問題で考える 各仕事（講義）を受け持つ人（学生）の上下限   それぞれの講義の最低・最高受講者数 各人（学生）が受け持つ仕事（講義）の上下限   両方とも 1 各枝のコスト   学生の希望順位に応じてつける

8 割当て問題のおさらい割当て問題のおさらい それぞれの人は、同時に受け持てる仕事の上下限がある それぞれの仕事は、受け持つ人の最低人数がある 人 i が仕事 j を受け持つときに費用 a ij がかかる これらを満たす、最低コストの、 人 対 仕事の割当を見つける問題 Σ 目的関数： Σ a ij x ij ≦ Σ = ≦ 制約条件： l i ≦ Σ j=1,…,m x ij ≦ u i ≦ Σ = ≦ l' j ≦ Σ i=1,…,n x ij ≦ u' j 「単体法（シンプレックス法）で得られる最適解は、 （条件の係数が整数なら）必ず整数解になっている」

9 割当問題の求解時間割当問題の求解時間 割当問題を線形計画のソルバーで解くときの、計算時 間を算定しよう ＝＝ 変数の数 ＝ 枝の数 ＝ 学生の数 × 希望数 ＝ 制約条件の数 ＝ 各頂点に対して 3 つ、各枝に対して 2 つ ＝ （＋ × （） ） × 2 ＝ （講義の数 ＋ 学生の数 × （希望数 +1 ） ） × 2 学生数 n=2000 、講義数 m =100 でも、 －＝ － 変数の数 ＝ 6000 －＝ － 制約条件の数 ＝ 16100 最近のパソコンなら、 10 分で解けるでしょう

10 実際に解いてみると実際に解いてみると ほとんどの場合、全ての学生は第 3 志望までの講義に割 り当てられる。つまり、「第 3 希望までのどこかに割り 当てる問題」と考えて差し支えない。 枝重みは： 第 1 希望： 70 第 2 希望： 30 第 3 希望： 0 として、最大コストの割り当てを線形計画ソルバーで求 める 何時間もかかって、そこそこの割当てしか得られなかったものが、 1 時間で（ある意味で）最適 公平なものが得られるようになった 何時間もかかって、そこそこの割当てしか得られなかったものが、 1 時間で（ある意味で）最適 公平なものが得られるようになった

11 重みの自由化重みの自由化 重みはこれでいいのか？ どっちでもいいから、と適当に選んでいる学生と、熱心 に 「ここに行きたい」と思っている学生が、同じ扱いなのは おかしい ＋＝ 第 1 希望 ＋ 第 2 希望 ＝ 100 となるように、自由に選べるようにする 強い希望が通りやすくなる

12 重みの自由化 (2) そのうちに、まじめに考えて希望の配点をつける人が 損をするようになった 楽な単位を取りたい学生が、 第１希望 100 ： 第２希望 0 と書いて、無理やり配属されるように仕組むようになっ た   70:30 と書いた人たちより優先される ＝＝ 第１希望＝ 100 、第２希望＝ 0~100 とすることにした。 : （ 100 : 100 というように書けるようになる） （学生の持ち点は固定でなくなるが、どのみち、学生 は 100 点以内しかもらえない）

13 重みの自由化 (3) やっぱり、楽な単位を取りたい学生が、 第１希望 100 ： 第２希望 0 と書いて、無理やり配属されるように仕組むようになっ た ＝＝ やっぱり、第１希望 ＝ 70 、第２希望 ＝ 30 で 固定することにした ＝＝ やっぱり、第１希望 ＝ 70 、第２希望 ＝ 30 で 固定することにした 新しいルールを作ると、そのルールの抜け穴を狙う人が 出る 抜け穴を狙う人がでてくると、ルールが変わる 最適化は、ルールがあるところで成り立つので、 ルールの変更や、抜け穴のレベルには関与できない

14 理学セミナー （旧） 学生が研究室２箇所に仮所属する 総合科目と違うところは、 学生は３つの希望を出す。希望順位はなし 前期・後期２つに分かれていて、各学生は希望の研究 室に前期か後期どちらかに所属する 授業の内容から（どの本でゼミをするか決めるため）、 各研究室の前期と後期の人数はほぼ同じであってほし い 総合科目と同じように、クラス分けを数理的に行える か

15 割り当て問題として、直接解く割り当て問題として、直接解く A 研究室を「前期の A 研究室」｢後期の A 研究室」と２つ のクラスに分けて考えると、うまくいきそう 同じ研究室に前期と後期に所属する学生が出てくる 可能性がある 「研究室の、前期と後期の学生数がほぼ同じ」 という制約が守られない この２つの問題点をどのように解決するかが鍵

16 ２段階でクラス分けする２段階でクラス分けする 第１フェイズで、総合科目と同じ方法で、学生を希望が通 る数を最大にして、各研究室に割り振る。前期後期は考え ない 第２フェイズで、各研究室の学生を、前期後期に割り振る － － 各学生が、前期に１つ、後期に１つ、 研究室に割り当てられるようにする － － 前期と後期の人数がほぼ同じようにする 第２フェイズをどのように解くか、が問題

17 ２部グラフの色分け２部グラフの色分け 学生と所属研究室を結んだ２部グラフを作る このグラフを、サイクルと極大なパスに分解する それぞれのパスとサイクルを、交互に２色で塗り分ける   パスの端以外の頂点では、枝２本が２色に塗り分けら れる 塗り分けた色で、前期か後期かを決める （各枝は、学生・研究室の割当てに対応することに注 意）

18 色分け法の正当性色分け法の正当性 このグラフを、サイクルと極大なパスに分解する   学生頂点は、パスの端にならない   各研究室頂点を端とするパスは、高々１本 それぞれのパスとサイクルを、交互に２色で塗り分ける   学生頂点に接続する枝は２色   研究室頂点に接続する枝は、両色同数か１つ異な る

19 計算時間計算時間 グラフを、サイクルと極大なパスに分解する  （＋）  グラフ探索で、 O （ 枝数 ＋頂点数 ）の時間ででき る それぞれのパスとサイクルを、交互に２色で塗り分ける  （＋ ）  自明、 O （ 枝数 ＋ 頂点数 ）の時間でできる ※ ※ たいした手間ではない

20 まとめまとめ 総合科目のクラス分けは、線形計画法（割当て問題） で解くと、すばやくできる 学生の希望も、工夫すればうまく取り入れられるが、 抜け道ができてしまうようだ 理学セミナー（旧）のクラス分け（前期後期がある） は、２段階で分けるとうまくいく