Анализ алгоритма

Этот алгоритм легко реализовать так, чтобы он выполнялся за полиномиальное время. Но приведет ли он к оптимальному ориентированному дереву? Прежде чем делать такой вывод, необходимо учесть одно обстоятельство: не каждое ориентиро- ванное дерево в G соответствует ориентированному дереву в свернутом графе G'.
Не могли ли мы «упустить» настоящее оптимальное ориентированное дерево в G, сосредоточившись на G'?

Ориентированные деревья G' однозначно соответствуют ориентированным деревьям G, которые имеют ровно одно ребро, входящее в цикл C; и эти соответ- ствующие ориентированные деревья имеют одинаковую стоимость в отношении {c'e}, потому что C состоит из ребер стоимости 0. (Мы говорим, что ребро e = (и, v) входит в C, если v принадлежит C, а и не принадлежит.) Итак, чтобы доказать, что наш алгоритм находит оптимальное ориентированное дерево в G, необходимо до- казать, что G имеет оптимальное ориентированное дерево с ровно одним ребром, входящим в C. Сейчас мы это сделаем.

(4.38) Пусть C — цикл в G, состоящий из ребер со стоимостью 0, такой, что r ⅜ C. Тогда существует оптимальное ориентированное дерево с корнем r, в котором в C входит ровно одно ребро.

Доказательство. Рассмотрим оптимальное ориентированное дерево T в G. Так как в T от r существует путь к каждому узлу, существует как минимум одно ребро в T, которое входит в C. Если T входит в C ровно один раз, дело сделано. В про- тивном случае предположим, что T входит в С многократно. Мы покажем, как изменить его для получения ориентированного дерева с не большей стоимостью, которое входит в C ровно один раз.

Пусть e = (a, b) — ребро, входящее в C, которое лежит на самом коротком воз- можном пути от r. В частности, это означает, что никакие ребра на пути от r не могут входить в C. Удалим все ребра T, входящие в C, кроме ребра e. Добавим во все ребра C, кроме ребра, входящего в b, — конец ребра e. Полученный подграф G обозначим T'.

Утверждается, что T' также является ориентированным деревом. Если ут- верждение истинно, мы приходим к желаемому результату, поскольку стои- мость T' очевидно не больше стоимости T: единственные ребра T', которые не принадлежат также T, имеют стоимость 0.

Почему же T является ориентиро- ванным деревом?

Заметим, что у T ровно одно ребро входит в каждый узел v ф r, и никакое ребро не входит в r. Следовательно, T содержит ровно n - 1 ребро; если нам удастся по- казать, что для каждого v в T' существует путь r-v, то граф T должен быть связным в ненаправленном смысле, а следовательно, является деревом. Это означает, что он удовлетворяет исходному определению ориентированного дерева.

Итак, рассмотрим любой узел v = r; мы должны показать, что в T существует путь r-v. Если v C, можно использовать тот факт, что путь в T от r к e был сохра- нен при конструировании T'; значит, чтобы достигнуть v, нужно сначала перейти к e, а потом следовать по ребрам цикла C. Теперь предположим, что v ⅜ C, и введем обозначение P для пути r-v в T. Если путь P не касается C, то он существует и в T'. В противном случае пусть w — последний узел в P ∩ C, а P' — подпуть P от w к v. Заметьте, что все ребра в P' также существуют в T'. Ранее уже было показано, что узел w достижим из r в T', потому что он принадлежит C. Объединяя этот путь к w с подпутем P', мы получаем путь к v. ■

Теперь можно собрать все воедино и убедиться в правильности алгоритма.

(4.39) Алгоритм находит оптимальное ориентированное дерево с корнем r в графе G.

Доказательство. Воспользуемся индукцией по количеству узлов в G. Если ребра F образуют ориентированное дерево, то алгоритм вернет оптимальное ориентированное дерево согласно (4.36). В противном случае рассмотрим задачу с модифицированными стоимостями {c'e|, эквивалентную согласно (4.37). После свертки цикла C со стоимостью 0 для получения меньшего графа G' алгоритм создает оптимальное ориентированное дерево в G' согласно индукционной ги- потезе. Наконец, согласно (4.38), в G существует оптимальное ориентированное дерево, соответствующее оптимальному ориентированному дереву, вычислен- ному для G'. ■

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

Еще по теме Анализ алгоритма:

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