- C++相談室 part120 [転載禁止]©2ch.net
406 ：デフォルトの名無しさん[sage]：2015/11/07(土) 09:17:42.53 ID:XiUv/MWJ - 数学板から誘導されてきました
下記の組み合わせ最適化問題を解きたいのですが、計算量が膨大になるため、効率のよい解き方を探しています
C++で実装しているとはいえ、こちらで聞くのが正しいかわかりませんが、お力をお貸しいただけますと幸いです
【問題】
■前提
・テストを控えるP人の学生がおり、同じ塾に所属している
・テストはN科目ある
テストの集合をTと表記し、各テストをT_n (n=1,2,...,N)と表記する
・塾は各科目に対してM通りの強化学習授業を用意している
科目nに対する強化学習授業の集合をC_nと表記し、各強化学習授業をC_nm (m=1,2,...,M)と表記する
・C_nmの実施により、学生p (p=1,2,...,P)はテストT_nの点数がe_nm_p 点あがる
■問題
塾は各科目の強化学習授業を一回ずつ実施する。つまり、n個の強化学習授業の集合C_n (n=1,2,...,N)から一つずつ選んで、N回の強化学習授業を行う。
塾としては、N回の強化学習授業による点数上昇がE点を超える人数を最大化したい
この時、どのようなアルゴリズムで強化学習授業の組み合わせを選べばよいか
全探索をすると解けるのですが、NとMが大きくなると組み合わせが膨大になります
N=10,M=10くらいを想定しておりますので、これを全探索するとなると不可能です
何かヒューリスティックな解き方はありますでしょうか
よろしくお願いいたします
|