学生振り分けアルゴリズムについて

[shiro4ao]

・学生が授業の希望を持っています。
　第１希望しかない人もいれば第５希望まである人もいます。

・授業はA～Fまでの６種類があります。
　授業クラスは４０人までです。

・この条件のもと出来る限りの希望を多く通し
　多くの人間が満足するアルゴリズムをさがす。


希望の少ない人から優先的に授業に割り当てていくアルゴリズム
を実装したのですが、それだと希望の多い学生がふりになる（希望の低い
授業に割り当てられる）ことがわかりました。（←実装前に気づけ

さらに、学生を適当な順番から割り当て、満足度
（第１希望2点、第２希望１点第３希望０点
第４希望－１点第５希望－２点など）がなるべく
多い組み合わせを見つけるまで計算させるという
アルゴリズムを考えたのですが、学生は１０００人
程いる設定なので計算量的に不可能かと思います。



なにか良いアルゴリズムはあるでしょうか…

(以前へろりさんに助けていただいたのですが、力不足で実装できませんでした。)


/*編集箇所*/

アルゴリズムの目的は
・なるべく多くの学生に授業に参加してもらう。（＝希望がかぶって参加できない組み合わせ減らす）
・なるべく多くの学生を満足度の高いふりわけをおこなう。
　（ただし、なにをもって「満足度がたかい」をするかは考える。
　　第５希望に振り分けられる学生を減らすことが満足度がたかいとするか、
　　点数の合計が多いほうが（第５希望が多かろうが）満足度がたかいとす
　　るか、といった問題）

学生は２４０人。
クラスは６クラスあり１クラス４０人の定員。

/*変更箇所終了*/

[初級者]

授業は６種類
１クラスは４０人まで
学生数は１０００人


他の条件はないのですか？
１つの授業を複数のクラスで行なうとか…。

[みけCAT]

「安定結婚問題」の応用かな？
とりあえずこのキーワードでググってみてください。

[みけCAT]

いや、違いますね。
すみません。

[さかまき]

そう難しく考えないで、
全員を第１希望で振り分け、必要なら抽選。（第１希望までの人はここでおしまい）
落選者で、第２希望で振り分け、必要なら抽選。（第２希望までの人はここでおしまい）
これを第５希望まで繰り返すと、何か不具合ありますか？

[さかまき]

しかし、学生１０００人中、２４０人分のコマしか用意しない学校って
生徒募集しすぎのボッタクリ学校ですね。

[dic]

プリム法
http://ja.wikipedia.org/wiki/%E3%83%97% ... 0%E6%B3%95
では　どうでしょうか？

[shiro4ao]

>初級者さん
ありがとうございます
与えられた条件とは異なるのですが、
「なるべく満足度を上げたい」「なるべく多くの学生に受講してもらいたい」
という目標のために少し、条件を変えて考えてみたいと思います。

>みけCATさん
ありがとうございます
依然、へろりさんからも安定結婚問題を応用してはというアドバイスを頂いたのですが
なかなか難しくて…

>さかまきさん
ありがとうございます
はじめはおっしゃるようなアルゴリズムを考えたのですが、そうなると
例えば、「５つ希望のある学生」が先に第一希望へ割り当てられ、
「１つしか希望のない学生」がはいれなくなってしまう場合があります。

「ボッタクリ学校」の件は少し条件を変えて考えてみたいと思います。

>dicさん
ありがとうございます
プリム法については少し勉強してみます。

[shiro4ao]

「なるべく満足度を上げたい」「なるべく多くの学生に受講してもらいたい」
という目標のアルゴリズムを探すために少し、条件を変えて考えてみたいと思います。


・学生は２４０人。
・クラスは６クラスあり１クラス４０人の定員。
・学生は第１希望しかない人もいれば第５希望まである人もいます。

アルゴリズムの目的は
・なるべく多くの学生に授業に参加してもらう。（＝希望がかぶって参加できない組み合わせ減らす）
・なるべく多くの学生を満足度の高いふりわけをおこなう。
　（ただし、なにをもって「満足度がたかい」をするかは考える。
　　第５希望に振り分けられる学生を減らすことが満足度がたかいとするか、
　　点数の合計が多いほうが（第５希望が多かろうが）満足度がたかいとす
　　るか、といった問題）

[toyo]

そうなるとアルゴリズム＝満足度の定義ということですね
正解はないので個人の考え方しだいになってしまいます
さかまきさんの方法でも満足度は高いかもしれません

[ゆーずぃ]

現時点では第1希望までしかない生徒は第1希望の授業に入れなかった時点でどこの授業にも入れず次の授業振り分けまでニート同然なのですから、第1希望しかない生徒から優先的に入れていくしかないと思いますよ。
ニートが発生した時点で授業を受ける人数が減っていって、どんどん授業に空きが出来てしまうわけですからね。
もしくは、自分の希望が全て断たれた生徒の行く末を案じる施策を行うか。ですね。
今のルールだと、例え第5希望で入ったとしてもニートよりは満足度が高いはずですから。

[さかまき]

＞・学生は第１希望しかない人もいれば第５希望まである人もいます。
可能性として、第５希望まで出した人もニートになる可能性があると思うので第６希望も聞いておく必要が
あるんじゃないでしょうか？
ということで第６志望もあると勝手に仕様を加えて

たとえば各人に、１，２，３，４，５、６の最小公倍数である６０ポイントを与え

総志望数１の時は、第１志望に６０ポイント
総志望数２の時は、１２に各３０ポイントを分配
総志望数３の時は、１２３に各２０ポイントを分配
総志望数４の時は、１２３４に各１５ポイントを分配
総志望数５の時は、１２３４５に各１２ポイントを分配
総志望数６の時は、１２３４５６に各１０ポイントを分配

して重みをつけておいて

第１志望の抽選を、第１志望を出している人（つまり全員）を対象に、ポイントの重みを考慮して抽選。
落選者のうち、第２志望を出している人を対象に、第２志望をポイントの重みを考慮して抽選。
落選者のうち、第３志望を出している人を対象に、第３志望をポイントの重みを考慮して抽選。
落選者のうち、第４志望を出している人を対象に、第４志望をポイントの重みを考慮して抽選。
落選者のうち、第５志望を出している人を対象に、第５志望をポイントの重みを考慮して抽選。
落選者のうち、第６志望を出している人は第６志望に入れるはず。
（落選した時点でそのクラスは満席だから、第６志望出した人は、最悪第６希望には入れますよね。）

なんていかが

[shiro4ao]

＞ずーいさん
ありがとうございます。
"ニート"状態の学生を抑えるために第一希望しかない人は
真っ先に割り当てるという方法ですね。
なんとか、頑張ってみます。


＞さかまきさん
ありがとうございます。
なるほど、つまり、希望の少ない学生ほど、
希望が通りやすくなるというわけですね。
難しそうなので、少し検討してみます。




みなさん、ありがとうございました。
いくつか方法を上げていただいたので
実装してみようかと思います。

それではこれで解決とさせていただきます。