假设我们有一个边用数字标记的 DAG。将路径的值定义为标签的乘积。对于每个（源，汇）对，我想找到从源到汇的所有路径的值的总和。您可以使用动态规划在多项式时间内完成此操作，但在如何分解问题方面仍然可以做出一些选择。就我而言，我有一个 DAG，必须用不同的标签反复评估。我的问题是：对于给定的 DAG，我们如何预先计算一个好的策略来重复计算不同标签的这些值？如果有一种算法可以找到最佳方法，例如最小化乘法次数的方法，那就太好了。但也许这问得太多了，我会对一个能很好分解的算法感到非常满意。
问问题
888 次
1 回答
1
令 S 为源集，V 为 DAG 的顶点集，E 为边集，n = |V|，m = |S|，W 为存储边权重的 nxn 矩阵，C 为一个 mxn 矩阵，使得 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] 是 S 中每个 i 从 i 到 k 的所有路径的值之和。
基本情况： k = 1 很明显（因为第一个元素没有任何前任）
归纳: 假设 C[i,j] 对于所有 j < k 都是正确计算的。从任何源 i 到 k 的所有路径都必须经过 k 的前一个 k'。由于我们以拓扑顺序迭代 k' 必须小于 k，并且根据我们的归纳假设 C[i,k'] 是从 i 到 k' 的路径值的总和。此外，通过特定前驱k'的从i到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]。这是因为元组隐含地表示图结构。就复杂性而言，这并没有好坏之分。
于 2012-05-04T18:30:58.600 回答