algorithm - 动态规划 : the case when a subproblem graph is not an acyclic graph?

Question

在动态规划中，子问题图被认为是有向无环图(dag)，但是当子问题图包含循环时如何解决？例如，subproblem(a) 的解决方案取决于 subproblem(b) 和 subproblem(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 将按顺序包含变量的值。这可以通过标准线性代数算法来完成，大概是高斯变换。