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

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
shiro4ao

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

#1

投稿記事 by shiro4ao » 14年前

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

・授業はA~Fまでの6種類があります。
 授業クラスは40人までです。

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


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

さらに、学生を適当な順番から割り当て、満足度
(第1希望2点、第2希望1点第3希望0点
第4希望-1点第5希望-2点など)がなるべく
多い組み合わせを見つけるまで計算させるという
アルゴリズムを考えたのですが、学生は1000人
程いる設定なので計算量的に不可能かと思います。



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

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


/*編集箇所*/

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

学生は240人。
クラスは6クラスあり1クラス40人の定員。

/*変更箇所終了*/



画像

初級者

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

#2

投稿記事 by 初級者 » 14年前

授業は6種類
1クラスは40人まで
学生数は1000人


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

みけCAT

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

#3

投稿記事 by みけCAT » 14年前

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

みけCAT

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

#4

投稿記事 by みけCAT » 14年前

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

さかまき

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

#5

投稿記事 by さかまき » 14年前

そう難しく考えないで、
全員を第1希望で振り分け、必要なら抽選。(第1希望までの人はここでおしまい)
落選者で、第2希望で振り分け、必要なら抽選。(第2希望までの人はここでおしまい)
これを第5希望まで繰り返すと、何か不具合ありますか?

さかまき

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

#6

投稿記事 by さかまき » 14年前

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


shiro4ao

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

#8

投稿記事 by shiro4ao » 14年前

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

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

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

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

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

shiro4ao

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

#9

投稿記事 by shiro4ao » 14年前

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


・学生は240人。
・クラスは6クラスあり1クラス40人の定員。
・学生は第1希望しかない人もいれば第5希望まである人もいます。

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

toyo

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

#10

投稿記事 by toyo » 14年前

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

ゆーずぃ

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

#11

投稿記事 by ゆーずぃ » 14年前

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

さかまき

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

#12

投稿記事 by さかまき » 14年前

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

たとえば各人に、1,2,3,4,5、6の最小公倍数である60ポイントを与え

総志望数1の時は、第1志望に60ポイント
総志望数2の時は、12に各30ポイントを分配
総志望数3の時は、123に各20ポイントを分配
総志望数4の時は、1234に各15ポイントを分配
総志望数5の時は、12345に各12ポイントを分配
総志望数6の時は、123456に各10ポイントを分配

して重みをつけておいて

第1志望の抽選を、第1志望を出している人(つまり全員)を対象に、ポイントの重みを考慮して抽選。
落選者のうち、第2志望を出している人を対象に、第2志望をポイントの重みを考慮して抽選。
落選者のうち、第3志望を出している人を対象に、第3志望をポイントの重みを考慮して抽選。
落選者のうち、第4志望を出している人を対象に、第4志望をポイントの重みを考慮して抽選。
落選者のうち、第5志望を出している人を対象に、第5志望をポイントの重みを考慮して抽選。
落選者のうち、第6志望を出している人は第6志望に入れるはず。
(落選した時点でそのクラスは満席だから、第6志望出した人は、最悪第6希望には入れますよね。)

なんていかが

shiro4ao

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

#13

投稿記事 by shiro4ao » 14年前

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


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




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

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

閉鎖

“C言語何でも質問掲示板” へ戻る