あなたの映画力を試せる!POPLETA映画検定(無料) >>

多数のランダムな値を取るものの組み合わせ最適化を考えています。

例です。
足し算を1分間でどのくらいの数解けるか毎日テストを行います。正解した数が点数です。
人数は100人。
全員がテストを受けますが、
テストを行う前に何人か予め指定し、
指定した人の合計点を1000点目指します。
人数は何人でもいいですが、教室の入れ替えがあるため、できるだけ同じ人とします。

こういった場合のアルゴリズムはどのようなものを使えばいいのでしょうか?
ナップサックかなとも思ったのですが、
容量と価値の判断基準が2つあります。
例は判断は点数のみです。

色々なアルゴリズムがありどれをどう考えていいのかわかりません
ヒントを頂けると嬉しいです

A 回答 (6件)

No.4へのコメントについてです。



> 人数少なくなのか、ぴったしなのか計算が楽なのか何をとるかでアルゴリズムが変わるとは思いますがどんな考えをすればいいでしょうか?

 それこそが「評価関数」ってことなんですよ。「何が良いか」の評価方法をきっちり(つまりどんな結果同士を比べた場合でも優劣が機械的に判定できるように)決めなきゃどうにもならない。で、「何が良いか」は「本来の目的」に合うようにする、という指針で考えるんです。
 仮に「本来の目的」なんてものがないただのお遊びの話だとすると(ご質問からはそうとしか思えないのだが)、評価関数は勝手に設定すりゃ良くて、評価関数ごとにそれぞれまるで違う問題になる。
    • good
    • 0

「何人か選んで合計点をぴったりにしましょう」なら subset sum. 「目標になるべく近づけましょう (でも越えちゃダメ)」な

らナップサック問題. 「目標になるべく近づけましょう (越えちゃっても近ければ OK)」は... どうしようかなぁ. NPC っぽいけど.
    • good
    • 0

> 色々なアルゴリズムがあり



って、そんなわけないでしょうよ。

 人jが得点xを取る確率φ[j](x)が測定してあるとして、人の集合P(|P|=n)を与えた時に合計得点がxになる確率Φ[n](x)がどうなるかを考える、という話だろうな。ただし「1000点を目指す」では話にならない。というのは「合計999点と合計998点ではどっちが良いか」ぐらいのことなら「目指す」と言っとけば決められるけれども、たとえば「(合計999点になる確率が50%で合計900点になる確率が50%) というのと、(合計998点になる確率が50%で合計910点になる確率が50%)というのでは、どっちが良いか」と訊かれたら「目指す」だけじゃ決めようがない。つまり、分布の「良さ」を評価する評価関数E(Φ)を具体的に与えなくちゃどうしようもありません。

 現実には学習効果というものがあって、各人の能力(つまりφ)が変化するから、この理想化にはちと無理があるが、「長い期間にわたって毎日毎日やってるからすでに平衡状態に達していて、学習効果は無視できる」と仮定できるやも知れぬ。(「なんちゅう無駄な苦行をやってるのか…」という話はさておくとして。)
  P={1,2,…, n}
としたとき、Φ[n](x)は漸化式
  Φ[1](x) = φ[1](t)
  Φ[j](x) = Σφ[j](t)Φ[j-1](x+t) (Σはt=0〜満点の範囲の総和)
で決まる。その上で、「全員Aの中からどの何人をPに選べばE(Φ)が最大になるか」という組み合わせ問題を考えるんだな。

 しかしφ[j]がわかっていないとこの先には進めない。とりあえず近似で議論するとして、確率φ[j](x)は経験的に正規分布で近似できるであろう、とすると、jさんの平均得点をμ[j], 得点の標準偏差をσ[j]、Φ[n](x) の平均得点をm, 得点の標準偏差をsとするとき、
  m = Σμ[j] (Σはj∈Pの総和)
  s^2 = Σ(σ[j])^2 (Σはj∈Pの総和)
ということになる。
 が、Eを具体的に与えないと、この先には行けないと思うな。
    • good
    • 0
この回答へのお礼

回答ありがとうございます
アルゴリズムではなく予測値の質問になっていました

テスト結果がわかっている場合はどうでしょうか?
簡単にするため数を減らします。合計を20点に近づけたい場合で結果が2点3点3点4点4点8点15点だったとします。
大きい方から数えた方が楽ですが、15点4点とぴったしになりません
小さい方から数えると2点から8点までの人を選べばおしまいです
人数少なくぴったしだと2点3点15点となります
人数少なくなのか、ぴったしなのか計算が楽なのか何をとるかでアルゴリズムが変わるとは思いますがどんな考えをすればいいでしょうか?

お礼日時:2019/02/14 23:34

「テスト前に人を指名」するってことは, テストで何点取れるかわからないってことだよね. そんな状況で「指定した人の合計点を1000点に近づける」ことは不可能だよ.



もちろん
誰も氏名しない
ことにより「たった 1000点しか違わない」といえるけど, そのような答えでいいですか?
    • good
    • 0
この回答へのお礼

回答ありがとうございます
確かにアルゴリズムではなく質問が値の予測になっていますね

ではテスト結果がわかっている場合はどうでしょうか?
簡単にするため数を減らします。合計を20点に近づけたい場合で結果が2点3点3点4点4点8点15点だったとします。
大きい方から数えた方が楽ですが、15点4点とぴったしになりません
小さい方から数えると2点から8点までの人を選べばおしまいです
人数少なくぴったしだと2点3点15点となります
人数少なくなのか、ぴったしなのか計算が楽なのか何をとるかでアルゴリズムが変わるとは思いますがどんな考えをすればいいでしょうか?

お礼日時:2019/02/14 23:33

「同じ人」がどういう意味なのかわからん. 本当に「同じ人」を選んでいいなら, 例えば「10点をとった人」を 100回選べば「1000点」になる.



こんなわけのわからない例じゃなくって, もっときちんとした問題の定義をしなければ「アルゴリズム」など考えようもありませんよ.
    • good
    • 0
この回答へのお礼

毎日テストをしていて、
テスト前に人を指名します
指定した人の合計点を1000点に近づけるようにします(例なので、1000点でなくても200点でも問題ありません)

累積ではなく
毎日テスト前に人を指定し、指定された人の合計点を近づけるようにします

お礼日時:2019/02/08 12:53

どのような問題なのかがわからんのだけど.... 特に


「人数は何人でもいいですが、教室の入れ替えがあるため、できるだけ同じ人とします。」
の部分.

これがなければ単純に「何人か選んで 1000点目指せばいい」と解釈できる (「目指す」があいまいだが) けど, この文のせいでいったいなにをしたいのかがさっぱりわからなくなっている.
    • good
    • 0
この回答へのお礼

回答ありがとうございます

書き方が悪くてごめんなさい
問題としては
単純に何人か選んで1000点目指せばいい
だけどできれば同じ人ならもっといいです

当てはまるようなものはありますでしょか?

お礼日時:2019/02/07 21:55

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aと関連する良く見られている質問

Q統計学の平均値の誤差範囲って何ですか? 平均値に誤差なんて出るのですか? 平均値には全てにおいて誤差

統計学の平均値の誤差範囲って何ですか?

平均値に誤差なんて出るのですか?

平均値には全てにおいて誤差範囲というのが存在するのですか?

Aベストアンサー

#4です。

「平均値の差の検定」を間違えていることに気付きました。
私の記述は、A社B社「2組の平均値の差の検定」ですので、平均値の差の期待値は0、分散は分散の加法性で、σ^2/nの2倍になりますので、平均値の差はN(0,2σ^2/n)の正規分布に従うとして検定せねばなりません。

スミマセンでした。

Q統計学の質問です。この問題がわかりません。 ∫xdF(x) 0〜∞まで積分なのですが、解答をみると、

統計学の質問です。この問題がわかりません。
∫xdF(x) 0〜∞まで積分なのですが、解答をみると、部分積分よりとなっているのですが、どのように部分積分ができるのかわかりません。よろしくお願いします。

Aベストアンサー

No.1へのコメントについてです。

E(X) = ∫{0〜∞} x φ(x) dx でしょ。だからですよってば。

Q統計学のしつもんです。この2番を解いてもらってもよろしいでしょうか?1番の答えは幾何分布となり、 G

統計学のしつもんです。この2番を解いてもらってもよろしいでしょうか?1番の答えは幾何分布となり、
G(p)=1-e^-λとなりました。

Aベストアンサー

(1)の答だとおっしゃる式が意味をなしてないでしょう。Ex(λ)の確率密度関数をφ(x)とすれば、
  P(Y=y) = ∫{y〜y+1} φ(x) dx (y∈自然数)
という離散分布ですよね。(1)ができれば(2)は真面目に計算すればどうということはないでしょう。

Q統計学の質問です。この一番の解き方を教えてください。

統計学の質問です。この一番の解き方を教えてください。

Aベストアンサー

ところで, この積分っていったいなにを表しているんだろうか. 被積分関数の |x| が理由もなにもなく虚空からひょっこり現れてるよねぇ.

Q袋の中に均質等大の球1000個が入っていて赤球が7個、白球が993個ある。この袋から無作為な復元抽出

袋の中に均質等大の球1000個が入っていて赤球が7個、白球が993個ある。この袋から無作為な復元抽出(取り出した球はもとに戻す)を500回行うとき赤球を取り出す回数をXとする。
(1)k回赤球が出る確率Pkを式で表せ
(2)平均E[x]と分散V[x]を求めよ

サイコロを4回振って1の出る回数をXとする。
(1)Xの回数が0,2,4の時の確率P0,P2,P4を求めよ
(2)平均E[X]と分散V[X]を求めよ。

以上の問題なのですが、解き方と答えを教えて欲しいです。よろしくお願いします。

Aベストアンサー

二項分布です。

(前半)
n 回取り出して、赤が k 回である確率は
 P(n, k) = nCk * p^k * (1 - p)^(n - k)
です。

(1) 赤を取り出す確率は、1000個のうちの7個ですから p=7/1000。n = 500 のとき、赤が k 回出る確率は
 Pk = 500Ck * (7/1000)^k * (993/1000)^(500 - k)

(2) 二項分布の期待値、分散は
 E[X] = np = 500 * 7/1000 = 3.5
 V[X] = np(1 - p) = 500 * 7/1000 * 993/1000 = 3.4755

どうしてこういう公式になるのかは、テキストを復習してください。

(後半)
サイコロを n 回振って、1の目が k 回出る確率は
 P(n, k) = nCk * (1/6)^k * (5/6)^(n - k)

(1) n=4 のとき、k=0 の確率は
 P(4, 0) = 4C0 * (1/6)^0 * (5/6)^4 = 625/1296
k=2 の確率は
 P(4, 2) = 4C2 * (1/6)^2 * (5/6)^2 = 6 * 25/1296 = 25/216
k=4 の確率は
 P(4, 4) = 4C4 * (1/6)^4 * (5/6)^0 = 1/1296 = 25/216

(2) 二項分布の期待値、分散なので
 E[X] = np = 4 * 1/6 = 2/3
 V[X] = np(1 - p) = 4 * (1/6) * (5/6) = 5/9

二項分布です。

(前半)
n 回取り出して、赤が k 回である確率は
 P(n, k) = nCk * p^k * (1 - p)^(n - k)
です。

(1) 赤を取り出す確率は、1000個のうちの7個ですから p=7/1000。n = 500 のとき、赤が k 回出る確率は
 Pk = 500Ck * (7/1000)^k * (993/1000)^(500 - k)

(2) 二項分布の期待値、分散は
 E[X] = np = 500 * 7/1000 = 3.5
 V[X] = np(1 - p) = 500 * 7/1000 * 993/1000 = 3.4755

どうしてこういう公式になるのかは、テキストを復習してください。

(後半)
サイコロを n 回振って、1の目が...続きを読む

Q長方形の対角の寸法を普通の電卓で計算出来ますか? 関数電卓を使わずに、普通の電卓で計算出来るのなら、

長方形の対角の寸法を普通の電卓で計算出来ますか?
関数電卓を使わずに、普通の電卓で計算出来るのなら、教えていただけますか?

Aベストアンサー

√キーとメモリ機能があれば簡単。
ピタゴラスの定理を使う。
縦a、横bとすると、a×a=の答えをM+(メモリー+キー)、b×b=の答えをM+(メモリー+キー)、MR(メモリーリコール)、√
で出た答えが、対角線の長さ

Q正規分布の和の計算

正規分布の和について教えて頂けませんか?
あるサイトを見たら、2つの正規分布の和の新しい平均はμ1+μ2だと解説しています。
これは間違いでしょうか?正しいでしょうか?
A組の数学の平均が70点(100点満点)で、B組が90点(同じテスト)の場合、A+B組の数学の平均は70+90となります・・・・そんなはずはありません!しかし他のサイトにも同じ解説がありました。
これは(μ1+μ2)/2の間違いではないでしょうか???
よろしくお願いします。

Aベストアンサー

ANo.12に付けられたコメントについてです。

> 現実世界で実際にこのように足して新しい分散を考えるときはどのような時

 たとえば「アボカドの種と、手作り植木鉢をひとつづつ袋に入れたセットを作った。種の質量の分布と植木鉢の質量の分布がわかっているとき、袋には種と鉢をランダムに投入したとすると、袋の質量の分布は?」

 種と鉢とが独立にサンプリングされている場合、袋の質量の確率密度関数φは、種の質量の確率密度関数sと鉢の質量の確率密度関数hの「畳み込み積分(convolution)φ=s*h 」で計算できます。しかし、平均や分散を知りたいだけなら、sとhの平均と分散だけわかっていれば良く、畳み込み積分は必要ない。(もちろん、どうしてそんな公式が成り立つのかを証明するには、畳み込み積分を使うんです。)

 統計学で最も重要な応用をひとつ挙げれば、「平均μ、標準偏差σを持つある分布からランダムに10個のサンプルx[1],x[2],…,x[10]を取って、その平均値mを計算する。mはどんな分布に従うか。」
 (「平均値m」なんて言葉でうっかりわかった気にならないで)mってどうやって計算するのかを考えれば、
   m = (1/10)x[1] + (1/10)x[2] + … + (1/10)x[10]
です。(重み付きの)足し算で計算したものmの分布を考えているわけですから、mが従う分布の平均と分散はご覧のサイトに書いてあるであろう公式を使って計算できますね。

ANo.12に付けられたコメントについてです。

> 現実世界で実際にこのように足して新しい分散を考えるときはどのような時

 たとえば「アボカドの種と、手作り植木鉢をひとつづつ袋に入れたセットを作った。種の質量の分布と植木鉢の質量の分布がわかっているとき、袋には種と鉢をランダムに投入したとすると、袋の質量の分布は?」

 種と鉢とが独立にサンプリングされている場合、袋の質量の確率密度関数φは、種の質量の確率密度関数sと鉢の質量の確率密度関数hの「畳み込み積分(convolution)φ=s*h 」で計算...続きを読む

Q二進法を学校で学ぶ意義って何でしょうか??

二進法を学校で学ぶ意義って何でしょうか??

Aベストアンサー

プログラミングなどの方向に興味を持つ人を生み出すためだね。電流の切れている瞬間を 0,流れている瞬間を 1と考えることによって,すべての数を電流の断続の組み合わせで表すことができる。この性質を利用したのがコンピュータである。

Q光速を超えることは出来ないらしいですが、もし、光速×(10の1兆乗×1000兆乗×1000兆乗)のス

光速を超えることは出来ないらしいですが、もし、光速×(10の1兆乗×1000兆乗×1000兆乗)のスピードの物体に乗って宇宙旅行をすれば、地球みたいな星、探せますか?

Aベストアンサー

早すぎて見えない・・・に一票入れておく。

なぜ見えないのか?
光の速度で移動すると、外からの光などの電磁波は真正面からしか届かないのです。
…そう。進んでいる方向に光る点が見えるだけで、他には何も見えず、また光の中に何があるのかすら判断できない状態になるのです。

Q統計学の質問です。 P(Z<=z| Y>y)のような条件付き分布関数は同時密度関数のように、 P (

統計学の質問です。
P(Z<=z| Y>y)のような条件付き分布関数は同時密度関数のように、
P (Z<=z,Y>y)/P( Y>y)とできますか?

Aベストアンサー

はい。


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング