Восстановление пути - алгоритм псевдоумножения (умножение матриц) - PullRequest
Новая
       49

Восстановление пути - алгоритм псевдоумножения (умножение матриц)

0 голосов
/ 12 июня 2019

Context

В настоящее время я работаю над восстановлением пути в некоторых из моих алгоритмов графа.Для решения задачи «один источник-кратчайшие пути» я использовал массив предшественников для восстановления кратчайшего пути от одного узла-источника ко всем остальным узлам.

Быстрый пример: [0, 3, 0,0]

Кратчайший путь от источника 0 до цели 1 будет [0, 3, 1], потому что начиная с целевого узла 1, путь можно построить, возвращаясь назад, используя 'родительский массив.1 достигнуто за 3, а 3 достигнуто за 0. 0 является источником.Готово.

Следующие алгоритмы представляют собой алгоритмы всех пар кратчайших путей.Самым простым примером был алгоритм Флойда-Варшалла, в результате которого получается матрица, содержащая все узлы-преемники.Хороший пример псевдокода восстановления можно найти в Wikipedia - Floyd Warshall .Подводя итог: Матрица используется для хранения каждого преемника из одного конкретного исходного узла.В основном он использует тот же подход, что и раньше, для каждого узла в качестве источника и продвижения вперед, а не назад.

Вопрос - Как создать матрицу преемников в случае алгоритма псевдоумножения?

Давайте сначала посмотрим на алгоритм: 

    for(int m = 0; m < nodeCount - 1; m++) {
        Matrix nextResultMatrix = new Matrix(nodeCount, nodeCount, Integer.MAX_VALUE);

        for(int i = 0; i < nodeCount; i++) {
            for(int j = 0; j < nodeCount; j++) {
                int value = Integer.MAX_VALUE;

                for(int k = 0; k < nodeCount; k++) {
                    value = Math.min(
                                value,
                                resultMatrix.at(i, k) + sourceMatrix.at(k, j)
                            );
                }
                nextResultMatrix.setAt(i, j, value);
            }
        }
        resultMatrix = nextResultMatrix;
    }

На каждой итерации будет вычисляться матрица для кратчайших путей длины m.Внутренний цикл очень похож на умножение матрицы.В самом внутреннем цикле алгоритм проверяет, является ли текущий путь короче пути от источника i по k до цели j.После завершения внутреннего k-цикла устанавливается значение внутри новой матрицы результатов.Что приводит к проблеме:

В случае алгоритма Флойда-Варшалла было легче определить, был ли путь короче и какой узел теперь является преемником.В этом случае значение, которое было вычислено в k-петле, будет установлено в любом случае.Можно ли здесь определить преемника?

Размышления о возможном решении

  • Алгоритм псевдоумножения предоставляет матрицу для каждой итерации, которая представляет кратчайшие пути длины m.Может быть, это поможет найти решение, не увеличивая и без того сложную по времени и не сохраняя каждую матрицу одновременно.
  • Я нашел интересную идею в комментарии здесь к stackoverflow, которая может привести крешение ссылка .Из того, что там заявлено, кажется, что это довольно тяжелая работа для отслеживания кратчайших путей.Я еще не полностью обдумал идею и то, как ее реализовать.

1 Ответ

0 голосов
/ 15 июня 2019

Мое решение

Итак, пройдя алгоритм и выяснив, что именно означает каждый шаг, я наконец-то смог найти решение. Я попытаюсь объяснить изменения в коде здесь, но сначала позвольте мне представить решение: 

for(int m = 0; m < nodeCount - 1; m++) {
    Matrix nextResultMatrix = new Matrix(nodeCount, nodeCount, Integer.MAX_VALUE);

    for(int i = 0; i < nodeCount; i++) {
        for(int j = 0; j < nodeCount; j++) {
            int value = resultMatrix.at(i, j);
            int shorterPathFoundOverNode = prevMatrix.at(i, j);

            // new shortest path from node i to j is
            // the minimum path that can be found from node i over k to j
            // k will be the node itself and every other node

            for(int k = 0; k < nodeCount; k++) {

                if(resultMatrix.at(i, k) != Graph.NO_EDGE && sourceMatrix.at(k, j) != Graph.NO_EDGE) {
                    if(value > resultMatrix.at(i, k) + sourceMatrix.at(k, j)) {

                        // update value if path is shorter
                        value = resultMatrix.at(i, k) + sourceMatrix.at(k, j);

                        shorterPathFoundOverNode = k;
                    }
                }
            }

            nextResultMatrix.setAt(i, j, value);
            prevMatrix.setAt(i, j, shorterPathFoundOverNode);
        }
    }

    resultMatrix = nextResultMatrix;
}

  • Очень основная, но важная идея состояла в том, чтобы заменить значение инициализации значения внутри цикла j из Integer.MAX значением, которое было найдено ранее, или на первой итерации значением, которое использовалось для инициализации матрицы. (Integer.MAX). Это также было важно, потому что условие было бы истинным один раз за итерацию, что раньше не вызывало никаких проблем, но сейчас - поскольку мы выполняем больше действий внутри условия - это важно.

  • Необходимо было заменить метод Math.min условием if, чтобы иметь возможность делать больше, чем просто устанавливать значение.

  • Для восстановления кратчайших путей используется метод отслеживания предыдущих узлов. Это очень похоже на проблему с одним источником кратчайших путей, как указано в вопросе. Конечно, в этом случае необходимо использовать матрицу, поскольку все узлы будут исходным узлом.

Чтобы подвести итог идеи: Установите дополнительную матрицу, которая отслеживает предыдущий узел для каждого целевого узла. При повторении цикла k сохраните предыдущий узел, если был найден более короткий путь (Важно: только если он на самом деле короче предыдущего пути).

...