Монте-Карло Симс - Пожалуйста, проверьте мой алгоритм

Question

В принципе, проблема имитирует следующее:

Есть урна с 50 зелеными шариками и 50 красными шариками.

Мне разрешается выбирать шары из урны без замены по следующим правилам: за каждый выбранный красный шар я теряю доллар, за каждый выбранный зеленый шар - доллар.

Я могу прекратить выбирать, когда захочу. В худшем случае я выбираю все 100, а чистый 0.

Вопрос заключается в том, чтобы придумать оптимальную стратегию остановки и создать программу для вычисления ожидаемого значения стратегии.

Моя стратегия состоит в том, чтобы продолжать выбирать шары, в то время как ожидаемое значение выбора другого шара является положительным.

То есть правило остановки ДИНАМИЧНОЕ.

В латексе вот рекурсивная формула на изображении:

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 решение вычисляется очень быстро. Что я делаю не так?

Любая помощь очень ценится!

Answer 1

Ваш алгоритм в порядке, но вы тратите впустую информацию. Для определенной пары (g, r) вы вычисляете ее ExpectedValue, а затем выбрасываете эту информацию. Зачастую с помощью алгоритмов рекурсии, запоминание ранее вычисленных значений может ускорить его LOT .

Следующий код выполняется в мгновение ока. Например, для g = r = 5000 вычисляется 36.900218 за 1 сек. Он запоминает предыдущие вычисления 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;
}

Answer 2

Грубо говоря, добавление одного шарика к урне удваивает количество вызовов, которые вам нужно будет сделать, до ExpectedValue (давайте не будем спорить о граничных условиях). Это называется O (e ⁿ ) и может поставить на колени самый мощный компьютер на Земле.

Проблема в том, что вы вычисляете одни и те же значения снова и снова. Сохраняйте таблицу ExpectedValue(r,g) и заполняйте ее по мере необходимости, чтобы вам никогда не приходилось вычислять одно и то же значение более одного раза. Тогда вы будете работать в O (n ² ), что намного быстрее.

Answer 3

На мой взгляд, правильное, но довольно прямолинейное решение.

Вот что вы можете сделать:

• Устранить рекурсию!
• Устранить повторные обращения ExpectedValue
• Распараллелить ваш код
• Прочитайте это [конспекты] . Это определенно будет полезно

Я могу предоставить несколько примеров кода, но это будет нечестно.