Алгоритм индукции C ++ очень медленное и динамическое программирование

Question

У меня есть проблема математического контроля, которую я решаю с помощью обратной индукции. Математическая проблема заключается в следующем:

с K меньше, чем n. И окончательные условия

Что такое J (0,0,0)?

---

Для этой цели я использую c ++ и 32-битную версию mingw в качестве компилятора.

Проблема заключается в коде (ниже), который решает проблему как индукцию и не дает никаких результатов, если n, M> 15.

Я пытался запустить n = M = 100 в течение 4 дней, но безрезультатно.

У кого-нибудь есть решение? Это опция компилятора для изменения (недостаточно памяти процессора)? Сложность слишком большая?

Вот мой код

const int n = 10;
const int M = 10;

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

    //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)
    {
        double y;
        for (int i = 0; i <= M; i++)
        {
            y = ((double) i)/M;
            {
                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;
}

int main()
{
    J_naive(0.0, 0.0, 0.0);
}

Answer 1

Вы можете попробовать следующий, полностью не проверенный код DP.Требуется около 24 * n ^ 3 * M байт памяти;если у вас столько памяти, она должна запуститься через несколько секунд.Если есть какое-то значение, которое никогда не будет отображаться как истинное возвращаемое значение, вы можете избавиться от seen_[][][] и использовать это значение в result_[][][], чтобы указать, что подзадача еще не решена;это уменьшит требования к памяти примерно на треть.Он основан на вашем коде до того, как вы внесли изменения для исправления ошибок.

const int n = 10;
const int M = 10;

bool seen_[n][n * M][2 * n];       // Initially all false
double result_[n][n * M][2 * n];

double J_naive(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);

    //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][Wdsqrtn + n]) {
            // Haven't seen this subproblem yet: compute the answer
            for (int i = 0; i <= M; i++)
            {
                J_tmp = std::min (J_tmp, ((double) n)*i/M*i/M +
                                  0.5*J_naive(K+1, ZM+i, W0, Wdsqrtn+1) +
                                  0.5*J_naive(K+1, ZM+i, W0, Wdsqrtn-1) );
            }

            result_[K][ZM][Wdsqrtn + n] = J_tmp;
            seen_[K][ZM][Wdsqrtn + n] = true;
        }
    }

    return result_[K][ZM][Wdsqrtn + n];
}