动态规划:子问题图不是无圈图的情况？

Question

在动态规划中，子问题图被认为是有向无圈图(dag)，但是当子问题图包含一个圈时，如何解决？例如，子问题(A)的解取决于子问题(B)和子问题(C)的解，子问题(B)的解同样取决于子问题(A)的解。

Answer 1

在某些情况下(精确地说，当函数的值彼此线性依赖时)，您可以将问题简化为求解线性方程组。例如，如果你知道

sub(a) = sub(b) + sub(c)
sub(b) = sub(c) * 2 + 5
sub(c) = sub(a) - 1

然后你可以建立一个线性系统，它看起来像一个矩阵。在这种情况下

       a   b   c    value
eq.1   1  -1  -1      0
eq.2   0   1  -2      5
eq.3  -1   0   1     -1

所以，你有一个矩阵A和一个向量c，你想要找到这样的x，使得Ax = c。向量x将按顺序包含变量的值。这可以用标准的线性代数算法，大概是高斯变换来实现。