Идея алгоритма Варшалла и возможное улучшение - PullRequest
Новая
       30

Идея алгоритма Варшалла и возможное улучшение

1 голос
/ 01 июня 2019

Алгоритм Варшалла для вычисления транзитивного замыкания орграфа обычно принимает следующую форму (из Идея и усовершенствование алгоритма Варшалла ): 

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)

Но мы могли бы ускорить вышеописанную реализацию, заметив, что обновления нет, если | i-j | <= k, поэтому мы можем пропустить запуск обновления в этом случае. </p>

Я что-то упустил? Разве такого рода улучшения не влияют на время выполнения? (Я еще не потратил время на вычисление времени выполнения для этой версии.)

1 Ответ

2 голосов
/ 01 июня 2019

Что вам не хватает, так это то, что |i - j| не связано с расстоянием между i и j.

Алгоритм Варшала делает на итерации k определение того, существует ли путь между вершиной, помеченной i, и вершиной, помеченной j, с использованием только вершин из {1, ..., k} в качестве промежуточных. Следовательно, R(k)[i,j] должно равняться 1, если выполняется одно из следующих двух условий:

  1. R(k-1)[i,j] = 1. То есть существует путь между вершиной i и вершиной j, использующий только вершины из {1, ..., k-1} в качестве промежуточных.
  2. R(k−1)[i, k] and R(k−1)[k, j]. То есть существует путь от вершины i до вершины k, и существует путь от вершины k до вершины j, каждая из которых использует только вершины среди {1, ..., k-1} в качестве промежуточных.

Значения i или j (и |i-j| в этом отношении) не имеют никакого отношения к расстояниям между вершиной i и вершиной j. Это произвольные метки, служащие идентификаторами для вершин.

...