3

在递归中求和：它是否总是产生 StackOverflow 错误？

public final static float getAlpha(int t, int i, int N, float[] P, float[][] B, float[][] A, int[] O)
{
    float alpha;
    if (t==1)
    {
        alpha = P[i] * B[i][O[0] - 1];
    }
    else
    {
        float sum = 0;
        int k;
        for (k=0; k < N; k++){
            sum = sum + (getAlpha(t-1, k, N, P, B, A, O) * A[k][i]);
        }
        alpha = sum * B[i][O[0] - 1];
    }
    return alpha;
}

我收到该行的错误：

sum = sum + (getAlpha(t-1, k, N, P, B, A, O) * A[k][i]);

有没有创造性的解决方案？

4

3 回答 3

2

我建议使用动态编程方法。这种方式永远不会计算第二次值，并且您无需担心堆栈溢出。

在由 N 数组创建。

所以Array[i][0] = P[i] * B[i][O[0] - 1]

从这里你将前一行的所有元素相加，然后乘以A[k][i] and B[i][O[0] - 1]wherek是前一列i的行的索引，是当前列的行的索引。

对于最终结果，您需要使用i最初调用它的值。

这样你只做2*t乘法和t*N*N求和。比你现在做的要少得多。

如果您在实际实现方面需要帮助，您应该查找 veterbi 算法。它非常相似。

于 2013-05-10T23:56:24.080 回答
0

在我看来，就像您一遍又一遍地不必要地重新计算相同的值。您的递归遵循树模式，其中每个分支都相同，并且这些分支的每个子分支都相同，等等。因此所涉及的计算量呈指数级增长。

于 2013-05-10T23:35:20.267 回答
0

显然你的 t 非常大（或者有一个错误并且小于 1）。

因此，除非您可以重写此函数以进行尾递归（这很困难，因为递归发生在循环中），并且您在执行尾递归的正确类型的 JVM 上运行（实际上只有少数这样做），否则递归解决方案总是会溢出堆栈。

在这一点上，我建议尝试以迭代方式重写它。这可能意味着从下往上开始，并将中间值存储在数组中。

于 2013-05-10T23:21:23.933 回答