假设我们有一个带有用数字标记的边的DAG。将路径的值定义为标签的乘积。对于每个(源,宿)-pair,我想找出从源到宿的所有路径的值的总和。您可以使用动态编程在多项式时间内完成此操作,但仍然可以在如何分解问题方面做出一些选择。在我的例子中,我有一个DAG,它必须用不同的标签重复计算。我的问题是:对于给定的DAG,我们如何预先计算一个好的策略来重复计算不同标签的这些值?如果有一种算法能找到一种最优的方法,比如最小化乘法的次数,那就太好了。但也许这要求太高了,我会很高兴有一个算法,只给出一个很好的分解。
发布于 2012-05-05 02:30:59
设S是源集,V是DAG的顶点集,E是边集,n= |V|,m= |S|,W是存储边权重的n×n矩阵,C是m×n矩阵,使得Ci,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次迭代完成后,Ci,k是S中每个i从i到k的所有路径的值的总和。
基本情况:对于k=1很明显(因为第一个元素没有任何前置元素)
归纳:假设Ci,j对于所有j< k都是正确计算的。从任何源i到k的所有路径都必须通过k的前导k‘。由于我们在拓扑级中迭代,k’必须小于k,并且根据我们的归纳假设Ci,k‘是从i到k’的路径的值之和。此外,通过特定前导k‘的从i到k的路径的值之和等于从i到k’的路径的值之和,即Ci,k',乘以Wk',k。因此,从i到k的所有路径的值之和是k的所有前导k‘上的Ci,k'*Wk',k之和。
同样的图结构,不同的W矩阵:如果我们需要计算具有相同结构但不同W的不同图的矩阵C,我们可以这样做:设C‘是一个矩阵,其元素是3元组列表。将上面的第6行替换为
C'[i,k].append((i,k',k))然后通过按拓扑顺序迭代顶点和迭代C'i,k中的元组,你可以计算Ci,k,而不需要查看图的结构。这是因为元组隐式地表示图结构。就复杂性而言,这并不是更好或更坏的。
https://stackoverflow.com/questions/10122597
复制相似问题