c++ - C++归纳算法非常慢且动态编程

我有一个数学控制问题，我通过反向归纳法解决。数学问题如下：
k小于n。
以及最终条件
什么是J（0,0,0）？
为此，我使用c++和mingw 32位作为编译器。
问题是解决问题的代码（如下）是归纳法，如果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);
}

最佳答案

您可以尝试以下完全未经测试的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];
}