algorithm - DAG 路径乘积之和

Question

假设我们有一个边上标有数字的 DAG。将路径的值定义为标签的乘积。对于每个(源，接收器)-pair，我想找到从源到接收器的所有路径的值的总和。您可以使用动态规划在多项式时间内完成此操作，但在如何分解问题方面仍然可以做出一些选择。就我而言，我有一个必须使用不同标签反复评估的 DAG。我的问题是:对于给定的 DAG，我们如何预先计算出一个好的策略来重复计算不同标签的这些值？如果有一种算法可以找到最佳方法，例如最小化乘法次数的方法，那就太好了。但也许这要求太高了，我会很高兴有一个能很好分解的算法。

Answer 1

设 S 是源集，V 是 DAG 的顶点集，E 是边集，n = |V|，m = |S|，W 是存储边权重的 n x n 矩阵， C 是一个 m x n 矩阵，使得 C[i,j] 在算法结束时保持从 i 到 j 的所有路径的值的总和。 为了简化算法的解释和正确性证明，我假设从1到n的图的顶点是拓扑排序的，其中节点1到m是源。这会将 O(|E|+|V|) 添加到我们算法的运行时间中:

算法伪代码:

1: set C[i,j] to 1 if i=j and i is a source node, and to 0 otherwise.
2: sort the DAG topologically
3: for k=1 to n (vertex traversal in the topological order)
4:   foreach predecessor k' of vertex k
5:     foreach i in S
6:       C[i,k] += C[i,k']*W[k',k]

两个外循环总共有O(|E|+|V|)次迭代。因此，算法的运行时间为 O((|V|+|E|).m) 假设加法和乘法需要常数时间。这包括拓扑排序的时间。

正确性证明:我们通过归纳证明，在最外层循环的第k次迭代完成后，C[i,k]是从i到所有路径的值之和k 代表 S 中的每个 i。
基本情况:对于 k = 1 很明显(因为第一个元素没有任何前置元素)
归纳:假设对于所有 j < k 都正确计算了 C[i,j]。从任何源 i 到 k 的所有路径都必须经过 k 的前导 k'。由于我们在拓扑顺序中迭代，因此 k' 必须小于 k，并且根据我们的归纳假设 C[i,k'] 是从 i 到 k' 的路径值的总和。此外，从 i 到 k 的路径值的总和，通过特定前导 k' 等于从 i 到 k' 的路径值的总和，即 C[i,k']，乘以 W[k ',k]。因此，从 i 到 k 的所有路径的值之和是 C[i,k']*W[k',k] 对 k 的所有前驱 k' 的总和。

相同的图结构，不同的 W 矩阵:如果我们需要为具有相同结构但不同 W 的不同图计算矩阵 C，我们可以执行以下操作:让 C' 是一个矩阵，其元素是 3 元组的列表。将上面的第 6 行替换为

C'[i,k].append((i,k',k))

然后通过按拓扑顺序遍历顶点并遍历 C'[i,k] 中的元组，您可以在不查看图结构的情况下计算 C[i,k]。那是因为元组隐含地表示图结构。就复杂性而言，这并没有好坏之分。