蒙特卡罗模拟 - 请检查我的算法

Question

蒙特卡罗模拟 - 请检查我的算法

c++algorithm

6

基本上，这个问题模拟如下：

有一个装有50个绿球和50个红球的盒子。

我可以按以下规则从盒子中取出球，不放回：每次取出一个红球，我就损失一美元；每次取出一个绿球，我就赚一美元。

我可以随时停止取球。最坏的情况是我取出了所有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值，解决方案可以非常快地计算出来。我做错了什么吗？

非常感谢任何帮助！

- AlmostSurely

1

这是一个有趣的问题，但就我而言，我会采用分析方法而不是模拟方法来解决它。 - Jason S

“我的策略是继续挑选球，只要挑选另一个球的预期价值为正。”-- 这很容易回答。根本不要玩，因为一开始的预期价值为0。 - Jason S

但是你可以做得更好。（对读者来说是有趣的练习） - Jason S

3个回答

2

在我看来，这是一个正确但相当直接的解决方案。

你可以这样做：

消除递归！
消除对ExpectedValue的重复计算
并行化你的代码
阅读这个[讲义]，它肯定会有用的

我可以提供一些代码样例，但那并不公平。

- Evgeny Gavrin

2

粗略地说，往瓮里添加一个球会使您必须调用 ExpectedValue 的次数翻倍（让我们不要争论边界条件）。这被称为 O(eⁿ)，它足以使地球上最强大的计算机崩溃。

问题在于您重复计算相同的值。保持 ExpectedValue(r,g) 的表格，并随着进程填写，这样您就永远不必重复计算相同的值。然后，您将在 O(n²) 中工作，速度快得多。

- Beta

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- orlp · Accepted Answer

你的算法很好，但你浪费了信息。对于某个特定的二元组 (g, r)，你计算了其期望值，然后就把这个信息扔掉了。通常，在递归算法中记住之前计算过的值可以大大加快运行速度。

下面的代码运行非常迅速。例如，对于 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;
}