募集をシェアしてメンターを探そう
シェア

※ この募集は締め切られました。

プログラミング 競技プログラミング Ruby

数値解析で最適なベッティング方法を反復法で求めたい(競技プログラミング、ニュートン法、ガウスニュートン法)

2021年8月25日
単発
予算
10,000円 〜
提案数
2人が提案中
応募期限
終了

全探索でのアルゴリズムを実装しましたが、実行時間が長すぎるため、最適なアルゴリズムを探し、
解説していただきたいです。

数値解析について学校で初歩的なことを学んでいます。
現在Rubyの実務経験が5年以上あります。

50%の確率ので掛け金が2倍になるルーレットがあるとします。

古典的なベッティング方法としてマーチンゲール法(倍賭け法)があり
1単位賭け、負ければその倍の2単位+1の合計3単位、さらに負ければ倍の6単位+1の合計7単位、と賭けていき
つまり

1回目, 賭け額: 1, 純利益: 1, 必要資産: 1
2回目, 賭け額: 3, 純利益: 2, 必要資産: 4
3回目, 賭け額: 7, 純利益: 3, 必要資産: 11
4回目, 賭け額: 15, 純利益: 4, 必要資産: 26

賭け額=(n-1)回目の掛額+1
純利益=賭け額-前回の必要資産
必要資産=賭け額+(n-1)回目の必要資産

ここで、資産が27ドル以上の場合、さらに効率的なベッティング方法が存在し
27ドル持っていると仮定すると

1回目, 賭け額: 3, 純利益: 3, 必要資産: 3, 確率: 0.5, 期待収益: 1.5
2回目, 賭け額: 3, 純利益: 0, 必要資産: 6, 確率: 0.25, 期待収益: 0
3回目, 賭け額: 7, 純利益: 1, 必要資産: 13, 確率: 0.125, 期待収益: 1.25
4回目, 賭け額: 14, 純利益: 1, 必要資産: 27, 確率: 0.0625, 期待収益: 0.625

確率=0.5^(n)
期待収益=確率*0.625
賭け額3,3,7,14が一番期待収益の合計が高い値となりました。
この計算は、全探索して行い、27^4(資産^n)回の計算で最大となる値を取得しました

この3,3,7,14の値を取得するアルゴリズムを少ないループ回数で求めたいです。
多次元のニュートン法を調べましたが、賭け額が負のとき最大となり、条件が存在するときの実装方法が分かりませんでした。

Rubyのコードを下記に示します

```
z = []
k = 27 # 資産

k.times do |a|
k.times do |b|
next unless b >= a
k.times do |c|
next unless c >= (a+b)
k.times do |d|
next unless d >= (a+b+c)

next if k < a+b+c+d

z << [a,b,c,d, (18.to_f/36)*a + (18.to_f/36)**2*b + (18.to_f/36)**3*c + (18.to_f/36)**4*d]
end
end
end
end

p z.sort_by{ |zz| zz[4] }.last
```

言語は問わず、最適なアルゴリズムを回答していただける方を探しています。
Python, Javascriptは理解できます。
最終的にpure javascriptで実装するため、Pythonのライブラリを使わないで説明していただけると助かります。

回答していただいた内容は、Qiitaにまとめたり、他の場所で公開される可能性があることをご了承ください。

募集をシェアしてメンターを探そう
シェア