c++ - C++ 归纳算法非常慢和动态规划

Question

我有一个数学控制问题，我通过反向归纳来解决。数学问题如下：

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);
}

标签： c++algorithmrecursioninduction

Answer 1

您可以尝试以下完全未经测试的 DP 代码。它需要大约 24*n^3*M 字节的内存；如果你有那么多内存，它应该在几秒钟内运行。如果有某个值永远不会作为真正的返回值出现，你可以去掉seen_[][][]那个值，用 inresult_[][][]表示子问题还没有解决；这将减少大约三分之一的内存需求。它基于您在进行编辑以修复错误之前的代码。

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];
}