Применение динамического программирования к графам
Динамическое программирование — это алгоритмический метод, который обычно основан на повторяющейся формуле и одном (или нескольких) начальных состояниях. Когда это применяется к графам, мы можем найти кратчайшие пути с одним источником или кратчайшие пути для каждой пары. Давайте посмотрим, какие проблемы может помочь нам решить динамическое программирование.
1. Беллман-Форд
Это алгоритм поиска кратчайших путей из одного источника. Есть другой алгоритм, который делает то же самое — алгоритм Дейкстры. Тогда чем Беллман-Форд отличается от Дейкстры? Хотя алгоритм Дейкстры, будучи жадным, быстрее, чем алгоритм Беллмана-Форда, он терпит неудачу, если в графах есть отрицательные ребра. Таким образом, Bellman-Ford используется для расчета кратчайшего пути из одного источника. Он использует очень элегантное решение для динамического программирования.
Он использует концепцию релаксации, которая уменьшает расстояние до узла, добавляя длину ребра и расстояние до предыдущего узла. Более подробную информацию можно найти здесь». Моя статья будет больше сосредоточена на аспекте динамического программирования.
Повторяемость: Беллман-Форд строит повторяемость по количеству ребер.
Важная концепция здесь заключается в том, что граф использует не более n-1 ребер, и мы можем придумать следующее выражение.
Пусть OPT (i, v) — стоимость кратчайшего пути s-v, использующего не более i ребер.
Тогда OPT (i, v) = 0, если i равно 0 и v = s. Чтобы дотянуться до самого себя, не требуется никаких преимуществ.
OPT (i, v) = ∞, если i = 0 и v не s. Если узел не является соседом v, то нет возможности немедленно добраться до этого узла, поэтому это ∞.
Помимо этого, у нас есть два важных случая:
(1) OPT (i, v) использует менее i ребер. Это левая диаграмма выше. Тогда нам не нужно добавлять вес при перемещении по графику. Вместо этого мы можем просто перейти к следующему краю. «V» — это целевой узел, к которому мы хотим добраться. Поскольку мы еще не нашли цель, мы можем оставить «v» таким, как есть, и просто использовать меньше ребер для поиска целевого узла.
(2) OPT (i, v) использует i ребер. Он представлен на правой диаграмме выше. Затем нам нужно выяснить, каков вес этого края, и перейти к следующему краю.
Но есть загвоздка. Поскольку может быть несколько математических операций с i ребрами, нам нужно извлечь из них минимум.
Обратите внимание, что даже если нам нужно взять как минимум эти 2 разных случая. Почему? Разве OPT (i-1, v) не лучший вариант? Не забывайте, что мы учитываем отрицательные грани, поэтому любой из этих случаев может привести к меньшему пути. Следовательно, нам нужно вычислить их обоих и взять минимум этих двух.
Разве это не напоминает вам задачу о рюкзаке 0–1? Когда-то можно представить узлы как размер рюкзака, а края — как предметы. Для каждого узла вы берете преимущество или не берете и не несете то, что у вас было раньше. Вот почему у них обоих очень похожие повторяющиеся отношения.
А теперь давайте подумаем, сколько там подзадач. Предполагая, что у нас есть n узлов, у нас есть n вариантов для v и n-1 для i. Это означает, что нам нужна матрица n на n, чтобы отслеживать наш прогресс.
Пробел: O (n²)
Какая временная сложность? Требуется O (степень v), чтобы вычислить минимум OPT (i-1, x) + w (x, v). Вам нужно сделать это для каждого n для всей строки i, так что это O (M). И это повторяется для каждой строки, так что это O (NM)
Продолжительность: O (морские мили)
Давайте рассмотрим пример для лучшего понимания.
Вышеупомянутая матрица может быть построена следующим образом:
Здесь возникает важный вопрос. Можем ли мы лучше использовать пространство? Неужели нам действительно нужен весь этот огромный кусок матрицы? Как мы можем заметить из соотношения рекуррентности, а также из того, как матрица была заполнена, нам просто нужно посмотреть на предыдущую строку. Таким образом, нам нужны только две строки этой матрицы, чтобы отслеживать наш прогресс. Фактически, мы можем просто использовать массив для представления прогресса, если бы мы немного изменили отношение повторения, отбросив индекс i. Мы можем это сделать, поскольку каждый узел будет вычислять минимум с одинаковым количеством ребер, и нам просто нужно сохранить результаты для каждого узла. Это та же идея, что и задача о неограниченном рюкзаке. Подробности: https://medium.com/@logicdevildotcom/knapsack-problems-18b2714e0737
Тот, что слева — измененный, а правый — исходный. Если вы сравните их бок о бок, они логически делают то же самое. Разница в том, что в то время как исходный алгоритм проверяет каждый узел на каждой i-й итерации, модифицированная версия проверяет только соседние узлы.
Розовый массив указывает на массив, который мы используем в новом решении DP, а серый — на внутренний цикл for псевдокода.
Продолжительность: O (морские мили)
Пробел: O (N)
Почему порядок релаксации не имеет значения?
В приведенном выше примере есть 3 узла, поэтому можно выполнить две итерации релаксации. Если релаксация происходит в обратном направлении, начиная с узла b, а затем до узла a, первая итерация даст b: бесконечность, a: 2. Затем вторая итерация будет b: 5, a: 2. В первой итерации b нельзя обновить, так как использовалось только одно ребро, можно обновить только узел a, который находится на расстоянии одного ребра от него. Вторая итерация — это когда два ребра использовались от источника до любого места, так что, наконец, можно обновить b. В первой итерации b просто не могло быть обновлено, так как a не был готов.
Тогда как насчет того, чтобы взглянуть на будущее обновление? В первой итерации это будут a: 2 и b: 5. Вторая итерация — это снова a: 2 и b: 5. Дальнейшее продвижение позволяет всем последующим узлам быть готовыми с обновленными расстояниями, поэтому большее количество итераций не меняет значения. Но тогда можно задаться вопросом, а что, если я делаю 100 итераций для 101 узла и делаю прямое обновление. Возможно ли, чтобы все было обновлено в первой итерации, и не было никаких изменений до 99-й итерации, и внезапно появился узел, расстояние которого уменьшилось на 100-й итерации? Нет, это невозможно, потому что прямое обновление не вызывает изменений после 1-й итерации, если нет отрицательного цикла.
Можем ли мы обнаружить отрицательный цикл?
Да! Нам просто нужно запустить алгоритм еще на одну итерацию. Вместо того, чтобы повторять | N | — 1 раз, мы можем сделать это | N | раз. Если значение изменяется на n-й итерации, это означает, что имеется цикл с отрицательным фронтом. Если мы расслабим края назад, это займет максимум n-1 раз. если мы расслабим края вперед, нам понадобится всего одна итерация, и в следующих итерациях изменений не будет. Следовательно, если на n-й итерации происходит какое-либо изменение, причиной его должен быть отрицательный цикл.
2. Флойд-Уоршалл
Что, если я хочу найти кратчайшие пути для всех пар? Мы можем применить Беллмана-Форда к каждому узлу, что даст мне кратчайший путь, который будет N²M. Есть более эффективный способ сделать это с помощью DP.
Давайте посмотрим на следующий пример.
Какой кратчайший путь от 1 до 2?
Какой кратчайший путь от 1 до 3?
Повторяемость: мы можем думать о добавлении произвольного узла k или не вычислять кратчайшие пути для каждой пары. И мы можем сделать это для каждого узла.
Тогда нам нужно рассмотреть два случая:
(1) k не входит в кратчайший путь:
(2) k входит в кратчайший путь:
Таким образом, окончательное отношение повторения выглядит так:
Псевдокод Флойда Уоршалла:
Продолжительность: O (N³)
Пробел: O (N²)
Можем ли мы применить DP, чтобы найти самые длинные пути?
Да, но мы должны быть осторожны, чтобы не включать цикл, и мы получаем простой путь в графе.
Как видно на графике ниже, если есть цикл, самый длинный путь будет бесконечно увеличиваться.
Если у него нет цикла, мы можем модифицировать методы Джикстры, Беллмана-Форда, Флойда-Уоршалла, чтобы рассчитать самые длинные пути.
Но когда дело доходит до DAG, мы точно знаем, что у него нет цикла. Итак, для DAG мы можем использовать топологическую сортировку для вычисления самых длинных путей, которые займут O (N + M).
Мы также можем использовать Djikstra для вычисления кратчайшего расстояния DAG, отрицая расстояния, но его время работы составляет O (M log N), что больше, чем O (M + N), поэтому более эффективно использовать топологическое упорядочение.
Если есть цикл, мы можем применить метод динамического программирования задачи коммивояжера (TSP). Задача TSP — выяснить, учитывая полный граф с весом ребер, указывающим стоимость, каков путь для посещения каждой вершины с минимальными затратами.
Сосредоточив внимание на последнем переходе от k до j (из диаграммы выше), путь P ’посетил каждую вершину в множестве S до k ровно один раз, и это самый короткий путь.
У повторения есть набор узлов, которые следует посетить, и узел, который я сейчас посещаю. Начиная с исходного узла, каждый узел посещается с j, который является последней остановкой каждого тура, а i указывает предпоследний город, в котором нужно остановиться.
Для каждого узла исследуется каждое подмножество от начальной точки до этого узла, так что вычисляется минимальное расстояние от начального узла до каждого другого узла в подмножестве.
До сих пор мы видели, как можно применить динамическое программирование для вычисления кратчайших путей в графах. Если у вас есть вопросы или отзывы, оставьте, пожалуйста, комментарий.