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

С учетом отношений между деревьями и ориентированными деревьями задача на- хождения ориентированного дерева с минимальной стоимостью, конечно, сильно напоминает задачу нахождения минимального остовного дерева для ненаправ- ленных графов.
Следовательно, будет естественно для начала поинтересоваться, нельзя ли напрямую применить идеи, разработанные для той задачи, в этой ситу- ации. Например, должно ли ориентированное дерево с минимальной стоимостью содержать ребро с наименьшей стоимостью во всем графе? Можно ли безопасно удалить самое «дорогостоящее» ребро в цикле и быть полностью уверенным в том, что оно отсутствует в оптимальном ориентированном дереве?

Разумеется, ребро с наименьшей стоимостью в G не будет принадлежать оп- тимальному ориентированному дереву, если e входит в корневой узел, поскольку искомое ориентированное дерево не должно иметь ребер, входящих в корень. Но даже если ребро с наименьшей стоимостью в G принадлежит ориентированному дереву с корнем r, оно не обязательно принадлежит оптимальному, как показывает


пример на рис. 4.19. Действительно, включение ребра со стоимостью 1 на рис. 4.19 не позволит включить ребро со стоимостью 2 из корня r (так как узел может иметь только одно входное ребро), а это, в свою очередь, приводит к неприемлемой стоимости 10 при включении другого ребра из r. Такие аргументы никогда не за- трудняли решение задачи минимального остовного дерева, в которой всегда было безопасно включить ребро с минимальной стоимостью; это наводит на мысль, что поиск оптимального ориентированного дерева может быть намного более сложной задачей. (Стоит заметить, что оптимальное ориентированное дерево на рис. 4.19 также включает ребро цикла с максимальной стоимостью; при другой структуре оптимальное ориентированное дерево даже может содержать ребро с наибольшей стоимостью во всем графе.)

а Ъ

Рис. 4.19. a — направленный граф с обозначенной стоимостью ребер; и b — оптимальное ориентированное дерево с корнем в узле r этого графа

Несмотря на все сложности, для этой задачи можно спроектировать алгоритм жадного типа, просто наше недальновидное правило выбора ребер должно быть чуть более сложным. Для начала разберемся, почему не работает общая стратегия включения ребер с наименьшей стоимостью. Формальное описание этой стратегии выглядит так: для каждого узла v Ф r выбирается ребро с минимальной стоимостью, входящее в v (с произвольной разбивкой «ничьих»); обозначим это множество из n - 1 ребер F*. Рассмотрим подграф (V, F*). Так как мы знаем, что оптимальное ориентированное дерево должно иметь ровно одно ребро, входящее в каждый узел v Ф r, а (V, F*) представляет способ принятия решений с минимальной стои- мостью, мы приходим к следующему факту.

(4.36) Если (V, F*) — ориентированное дерево, то это ориентированное дерево с минимальной стоимостью.

Итак, сложность в том, что (V, F*) может и не быть ориентированным деревом. В этом случае из (4.34) следует, что в (V, F*) должен присутствовать цикл C, не включающий корень. Теперь нужно решить, что делать в такой ситуации.

Чтобы рассуждения стали более понятными, начнем со следующего наблю- дения. Каждое ориентированное дерево содержит ровно одно ребро, входящее в каждый узел v ф r; если выбрать некоторое ребро v и вычесть постоянную ве- личину из стоимости каждого ребра, входящего в v, то общая стоимость каждого ориентированного дерева изменится на одинаковую величину.

По сути, это оз- начает, что фактическая стоимость всех остальных ребер, входящих в v, относи- тельна этой величины. Пусть уv означает минимальную стоимость любого ребра, входящего в v. Для каждого ребра e = (и, v) со стоимостью cг > 0 определяется модифицированная стоимость c', равная c - у . Поскольку c > у , все модифи- цированные стоимости остаются неотрицательными. Но важнее то, что из этого вытекает следующий факт.

(4.37) T является оптимальным ориентированным деревом в G со стоимостя- ми {ce} в том, и только в том случае, если оно также является оптимальным ориен- тированным деревом с модифицированными стоимостями {c'e}.

Доказательство. Возьмем произвольное ориентированное дерево Т. Разность между его стоимостью с набором стоимостей {ce} и {c'e} равна в точности то есть

Это объясняется тем, что у ориентированного дерева в каждый узел v из суммы входит ровно одно ребро. Поскольку разность между двумя ребрами не зависит от выбора ориентированного дерева T, мы видим, что граф T имеет минимальную стоимость с {ce} в том, и только в том случае, если он имеет минимальную стои- мость с {c'e}. ■

Теперь рассмотрим задачу в контексте стоимостей {c'e}. Все ребра в множестве F имеют стоимость 0 с модифицированными стоимостями; таким образом, если (V, F) содержит цикл C, мы знаем, что стоимость всех ребер в C равна 0. Из этого следует, что мы можем использовать сколько угодно ребер из C (не нарушающих правила построения ориентированного дерева), поскольку включение ребер из C не повышает стоимость.

В продолжение работы алгоритма C свертывается в один суперузел с форми- рованием меньшего графа G' = (V', E'). Здесь V' содержит узлы V- C плюс один узел c*, представляющий C. Каждое ребро e E преобразуется в ребро e' E'

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

Ниже приводится полный алгоритм.

Для каждого узла v ф r

Пусть yv - минимальная стоимость ребра, входящего в узел v Заменить стоимости всех ребер e, входящих в v, на c'=ce - yv Выбрать одно ребро со стоимостью 0, входящее в каждый узел v Ф r; полученное множество обозначается F*

Если F* образует ориентированное дерево, вернуть его Иначе существует направленный цикл C £ F*

Свернуть C в один суперузел; полученный граф обозначается G' = (V', E') Рекурсивно найти оптимальное ориентированное дерево (V', F') в G' со стоимостями {c'e}

Развернуть (V', F') в ориентированное дерево (V, F) в G, добавляя все ребра C, кроме одного

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

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

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