Разработка и анализ алгоритма

Наша работа над алгоритмом начнется с адаптации исходной версии алгоритма Беллмана-Форда, которая была менее эффективной в использовании памяти. Начнем с расширения определений OPT(i, v) из алгоритма Беллмана-Форда, опре- делив их для значений i > n.
При наличии в графе отрицательного цикла (6.22) уже не действует, и кратчайший путь может становиться все короче и короче при многократном проходе отрицательного цикла. Для любого узла v в отрицательном цикле, у которого имеется путь к t, действует следующее утверждение:

(6.30) Если узел v может достигнуть узла t и входит в отрицательный цикл, то

Если граф не содержит отрицательных циклов, то из (6.22) вытекает следующее утверждение:

(6.31) Если G не содержит отрицательных циклов, то OPT(i, v) = OPT(n - 1, v) для всех узлов v и всех i > n.

Но для насколько больших значений i нужно вычислить значения OPT(i, v), прежде чем сделать вывод об отсутствии в графе отрицательных циклов? Напри- мер, узел v может удовлетворять уравнению OPT(n, v) = OPT(n - 1, v) и при этом все равно лежать на отрицательном цикле. (А вы видите почему?) Как выясняется, гарантии дает только выполнение условия для всех узлов.

(6.32) В графе не существует отрицательного цикла с путем к узлу t в том и только в том случае, если OPT(n, v) = OPT(n - 1, v) для всех узлов v.

Доказательство. Утверждение (6.31) уже доказано в прямом направлении. Что касается обратного направления, мы воспользуемся аргументом, примененным ранее для обоснования безопасности преждевременной остановки алгоритма Беллмана-Форда. А именно, предположим, что OPT(n, v) = OPT(n - 1, v) для всех узлов v. Значения OPT(n + 1, v) могут быть вычислены по OPT(n, v); но все эти зна- чения совпадают с соответствующими OPT(n - 1, v). Следовательно, выполняется равенство OPT(n + 1, v) = OPT(n - 1, v). Распространяя эти рассуждения на будущие итерации, мы видим, что ни одно из значений никогда не изменится снова, то есть OPT(i, v) = OPT(n - 1, v) для всех узлов v и всех i > n. Следовательно, не может быть отрицательного цикла C, имеющего путь к t; для любого узла w в этом цикле C из (6.30) следует, что значения OPT(i, w) становятся сколь угодно отрицательными с увеличением i.

Утверждение (6.32) предоставляет механизм O(mn) для принятия решения о том, существует ли в G отрицательный цикл, способный достичь t. Мы вычис- ляем значения OPT(i, v) для узлов G и для значений i вплоть до n. Согласно (6.32), отрицательного цикла не существует в том, и только в том случае, если существует некоторое значение i < n, для которого OPT(i, v) = OPT(i - 1, v) для всех узлов v.

Итак, мы определили, имеется ли в графе отрицательный цикл с путем из цикла к t, но сам цикл еще не найден. Чтобы найти отрицательный цикл, рассмотрим такой узел v, что OPT(n, v) = OPT(n - 1, v): для этого узла путь P из v в t со стоимостью OPT(n, v) должен использовать ровно n ребер. Этот путь минимальной стоимости P из v в t находится обратным отслеживанием по подзадачам. Как и в доказательстве (6.22), простой путь может содержать только n-1 ребер, поэтому путь P должен содержать цикл C. Утверждается, что цикл C имеет отрицательную стоимость.

(6.33) Если граф G состоит из n узлов и OPT(n, v) = OPT(n - 1, v), то путь P из v в t стоимостью OPT(n, v) содержит цикл C и C имеет отрицательную стоимость.

Доказательство. Сначала заметим, что путь P должен содержать n ребер, так как OPT(n, v) = OPT(n - 1, v), поэтому каждый путь, содержащий n - 1 ребер, имеет стоимость большую, чем у пути P. В графе с n узлами путь, состоящий из n ребер, должен содержать (хотя бы) повторяющийся узел; пусть w — узел, встречающий в P более одного раза. Пусть C — цикл в P между двумя последовательными вхож- дениям узла w. Если бы цикл C не был отрицательным, то удаление C из P дало бы путь v-t, содержащий менее n ребер и имеющий не большую стоимость. Это противоречит нашему предположению о том, что OPT(n, v) = OPT(n - 1, v), а следо- вательно, цикл C должен быть отрицательным. ■

(6.34) Описанный выше алгоритм находит отрицательный цикл в G, если такой цикл существует, и выполняется за время O(mn).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка и анализ алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  3. § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
  4. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  5. АЛГОРИТМ
  6. АЛГОРИТМ УДАЧИ
  7. Алгоритм исцеления:
  8. Алгоритм избавления от боли
  9. 2. Специфика и алгоритмы работы с источниками.
  10. Алгоритм обработки результатов.