Warshall算法的思想和改进

问题描述

主要基于以下思想：利用问题与其简单版本（而不是较小版本）之间的关系。 Warshall和Floyd发表了他们的算法，没有提到动态编程。尽管如此，这些算法当然具有动态编程风格，并且已被视为该技术的应用。

The Warshall-Floyd algorithm is based on essentially the idea: exploit a relationship between a problem and its simpler rather than smaller version. Warshall and Floyd published their algorithms without mentioning dynamic programming. Nevertheless, the algorithms certainly have a dynamic programming flavor and have come to be considered applications of this technique.

ALGORITHM Warshall(A[1..n, 1..n])
    //ImplementsWarshall’s algorithm for computing the transitive closure
    //Input: The adjacency matrix A of a digraph with n vertices
    //Output: The transitive closure of the digraph
    R(0) ←A
    for k←1 to n do
        for i ←1 to n do
            for j ←1 to n do
                R(k)[i, j ]←R(k−1)[i, j ] or (R(k−1)[i, k] and R(k−1)[k, j])
    return R(n)

对于某些情况，我们可以加快上述Warshall算法的实现通过重构其最内层的循环来进行输入

We can speed up the above implementation of Warshall’s algorithm for some inputs by restructuring its innermost loop

我在上面的文字中提出的问题是

My question on above text are following

1. 作者的主意是利用问题与其简单版本而不是较小版本之间的关系。请

1. What does author mean by idea is " exploit a relationship between a problem and its simpler rather than smaller version" Please elobaorate.

如上文实现中所述，我们如何提高速度。

How can we improve speed as author mentioned in above implemenation.

推荐答案

从1开始的公式表示最短路径问题（可以看作是传递闭包问题的概括）具有属性；但是，对于此属性，不存在形式描述（就数学定义而言）。最优子结构属性对于使问题适合动态规划是必需的。

The formulation from 1. means that the shortest path problem (which can be seen as a generalization of the transitive closure problem) has the optimal substructure property; however for this property does not exist a formal description (in the sense of a mathematical definition). The optimal substructure property is necessary for a problem to be amenable to dynamic programming.

这篇关于Warshall算法的思想和改进的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！