Мемоизация и наивные алгоритмы - ответ 2 разных

Question

Я написал два рекурсивных алгоритма на с ++ на основе биномиального дерева.Один очень наивный, а другой - с воспоминаниями.Тем не менее, оба дают мне разные результаты.Наивный имеет хороший результат, это то, что я ожидаю в конце, но очень медленный.

Предположим, n=M=6 Я получаю J_naive (0,0,0) = 0.97916666666666652 и J_SO (0,0,0,0) = 0.80729166666666652

Есть ли кто-нибудь, кто видит проблему со вторым алгоритмом?

Наивный алгоритм:

double J_naive (double K, double Z, double W)
{
    double J_tmp = exp(100.0);

    if (Z >= 1.0)
        return 0.0;

    //Final condition : Boundaries
    if (K == n)
    {
        double I_WGreaterThanZero = 0.0;
        if (W > 0) I_WGreaterThanZero = 1.0;

        if (Z >= I_WGreaterThanZero) return 0.0;
        return exp(100.0);//Infinity
    }

    //Induction
    else if (K < n)
    {
        double y;
        for (int i = 0; i <= M; i++)
        {
            y = ((double) i)/M;
            if (Z+y <= 1)
                J_tmp = std::min (J_tmp, ((double) n)*y*y +
                                  0.5*J_naive(K+1.0, Z+y, W + 1.0/sqrt(n)) +
                                  0.5*J_naive(K+1.0, Z+y, W - 1.0/sqrt(n)) );
        }
    }

    return J_tmp;
}

И код с памяткой

typedef vector<vector <bool>> v2dbool;
typedef vector<vector <double>> v2ddouble;
v2dbool seen_[n];
v2ddouble result_[n];

double J_MEMO (unsigned K, unsigned ZM, double W0, int Wdsqrtn)
{
    double J_tmp = exp(100.0);
    double WGreaterThanZero = 0.0;

    double Z = (double) ZM / M;
    double W = W0 + Wdsqrtn * 1./sqrt(n);
    int ind = (K+Wdsqrtn)/2.;

    //Final condition : Boundaries
    if (K == n)
    {

        if (W > 0) WGreaterThanZero = 1.0;
        else WGreaterThanZero = 0.0;

        if (Z >= WGreaterThanZero) return 0.0;
        return exp(100.0);//Infinity
    }

    //Induction
    else if (K < n)
    {
        if (!seen_[K][ZM][ind])
        {
            for (int i = 0; i <= M; i++)
            {
               if ((double) (ZM+i)/M <= 1)
                 J_tmp = std::min (J_tmp, ((double) n)*i/M*i/M +
                                   1./2.*J_MEMO(K+1, ZM+i, W0, Wdsqrtn+1) +
                                   1./2.*J_MEMO(K+1, ZM+i, W0, Wdsqrtn-1) );
            }

            result_[K][ZM][ind] = J_tmp;
            seen_[K][ZM][ind] = true;
        }
    }

    return result_[K][ZM][ind];
}

void initiateVector ()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < M+1; j++)
        {
            seen_[i].resize (j+1, std::vector<bool>(i+1, false));
            result_[i].resize (j+1, std::vector<double>(i+1));
        }
    }
}

Answer 1

Не углубляясь слишком глубоко в код, я вижу, что в J_MEMO у вас нет переменной y, но передается ZM+i непосредственно в качестве второго параметра.Такое ощущение, что вы должны пропустить ZM+i/M там, а не делить ZM в начале функции, чтобы получить Z.Или просто вернуть y.