gpt4 book ai didi

c++ - Monte Carlo Sims - 请检查我的算法

转载 作者:塔克拉玛干 更新时间:2023-11-02 23:25:42 24 4
gpt4 key购买 nike

基本上,这个问题模拟了以下内容:

有一个装有 50 个绿球和 50 个红球的瓮。

我可以从 jar 里取出球,无需更换,规则如下:每取出一个红球,我将损失一美元,每取出一个绿色球,我将获得一美元。

我可以随时停止采摘。最坏的情况是我选择了所有 100 个,然后净选 0 个。

问题是想出一个最优的停止策略,并创建一个程序来计算该策略的预期值。

我的策略是继续捡球,而捡另一个球的期望值为正。

也就是说,停止规则是动态的。

在 Latex 中,这是图像中的递归公式:

http://i.stack.imgur.com/fnzYk.jpg

#include <stdio.h>
#include <math.h>
#include <stdlib.h>



double ExpectedValue(double, double);
double max(double, double);

main() {

double g = 50;
double r = 50;


double EV = ExpectedValue(g, r);

printf ("%f\n\n", EV);

system("PAUSE");

}


double ExpectedValue(double g, double r){

double p = (g / (g + r));

double q = 1 - p;

if (g == 0)

return r;

if (r == 0)

return 0;

double E_gr = max ((p * ExpectedValue (g - 1, r)) + (q * ExpectedValue (g, r - 1)), (r - g));

return E_gr;

}

double max(double a, double b){

if (a > b)
return a;

else return b;
}

我让它运行了 30 分钟,它仍在运行。对于较小的 g 和 r 值,可以非常快速地计算出解。我做错了什么?

非常感谢任何帮助!

最佳答案

你的算法很好,但是你在浪费信息。对于特定的 (g, r) 对,您计算它的 ExpectedValue,然后丢弃该信息。通常使用递归算法记住以前计算的值可以加快很多

下面的代码一眨眼就跑完了。例如,对于 g = r = 5000,它会在 1 秒内计算出 36.900218。它会记住 ExpectedValue(g, r) 的先前计算,以防止不必要的递归和重新计算。

#include <stdio.h>
#include <stdlib.h>

double ExpectedValue(int g, int r, double ***expectedvalues);
inline double max(double, double);

int main(int argc, char *argv[]) {
int g = 50;
int r = 50;
int i, j;

double **expectedvalues = malloc(sizeof(double*) * (g+1));

// initialise
for (i = 0; i < (g+1); i++) {
expectedvalues[i] = malloc(sizeof(double) * (r+1));
for (j = 0; j < (r+1); j++) {
expectedvalues[i][j] = -1.0;
}
}

double EV = ExpectedValue(g, r, &expectedvalues);
printf("%f\n\n", EV);

// free memory
for (i = 0; i < (g+1); i++) free(expectedvalues[i]);
free(expectedvalues);

return 0;
}

double ExpectedValue(int g, int r, double ***expectedvalues) {
if (g == 0) return r;
if (r == 0) return 0;

// did we calculate this before? If yes, then return that value
if ((*expectedvalues)[g][r] != -1.0) return (*expectedvalues)[g][r];

double p = (double) g / (g + r);
double E_gr = max(p * ExpectedValue(g-1, r, expectedvalues) + (1.0-p) * ExpectedValue(g, r-1, expectedvalues), (double) (r-g));

// store value for later lookup
(*expectedvalues)[g][r] = E_gr;

return E_gr;
}

double max(double a, double b) {
if (a > b) return a;
else return b;
}

关于c++ - Monte Carlo Sims - 请检查我的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5927676/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com