<<
>>

Построение решений

S’ ∩ Vt = U.

Утверждается, что S' является независимым множеством в G; это будет противо- речить нашему выбору S как независимого множества с максимальным весом в G, соответствующего условию S ∩ V = U.

Например, предположим, что S' не является независимым; пусть e = (u, v) — ребро, оба конца которого принадлежат S'. Однако и и v одновременно S принадлежать не могут, иначе они будут принадлежать S'., так как оба являются независимыми множествами. Следовательно, и S - S'. и v S'f - S, из чего следует, что и не является узлом аv е Gt - (Vf ∩ ).

Но тогда согласно (10.14) не может быть ребра, соединяющего и и v. ■

Утверждение (10.17) — именно то, что необходимо для определения рекур- рентного отношения для подзадач. Оно сообщает, что информация, необходимая для вычисления f(U), неявно содержится в значениях, уже вычисленных для под- деревьев.

А именно: для всех дочерних t. достаточно просто определить значение независимого множества с максимальным весом S. для G, с учетом ограничения S. ∩ Vt = U ∩ Vt . Это ограничение не определяет точно, что собой представляет S. ∩ У, ; оно лишь говорит, что это может быть любое независимое множество U. U V,., для которого Ui ∩ J’t = U ∩ У, . Следовательно, вес оптимального вари- анта S равен

U ∩ У, и U. U У, независимое }.

Рис.

10.8. Подзадачаft(U) в подграфе Gr В оптимальном решении этой подзадачи мы рассматриваем независимые множества Sj в подграфах-потомках G,, для которых Sj ∩ Vt = U ∩ У,

Наконец, значениеft(U) равно просто w(U) в сумме с максимумами, добавлен- ными по d дочерним узлам t, — не считая того, что для предотвращения повторного подсчета узлов U мы исключаем их из вклада дочерних узлов. Таким образом:

(10.18) Значениеft(U) задается следующим рекуррентным отношением: j

ft(U) = w(U)+ Х>⅞⅜ {£/)— w{£/r Пt/)j:

U. ∩ Vt= U ∩ V, и [/. £ l·' независимое}.

Обобщенный алгоритм просто строит значения всех подзадач по листьям T и вверх.

Чтобы найти независимое множество с максимальным весом в графе G для заданной древовидной декомпозиции (T, {Vt}) графа G:

При необходимости изменить декомпозицию так, чтобы она не имела избыточности Разместить корень T в узле r Для каждого узла t из T в обратном порядке обхода Если t является листом

Для каждого независимого множества U из Vt f(U) = w(U)

Иначе

Для каждого независимого множества U из Vt

f(U) определяется рекуррентным отношением из (10.18)

Конец Если Конец цикла

Вернуть max {fr (U):U £ Vr независимое}

Как обычно, независимое множество с максимальным весом находится обрат- ным отслеживанием по последовательности выполнения.

Время, необходимое для вычисления^ U), находится следующим образом: для каждого из d дочерних узлов tj и для каждого независимого множества Uj в l·' мы за время О(w) проверяем условие Uj ∩ Vt = U ∩ Jf чтобы узнать, должно ли оно рассматриваться при вычислении (10.18).

Для f(U) общее время составляет O(2w+1wd); так как с t связано не бо- лее 2w+1 множеств U, общие затраты времени на узел t составляют O(4w+1wd). На- конец, эти величины суммируются по всем узлам t для получения общего времени выполнения. Мы видим, что сумма по всем узлам t количества дочерних узлов t равна O(n), так как каждый узел считается как дочерний один раз. Следовательно, общее время выполнения составляет O(4w+wn).

10.5.

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

Еще по теме Построение решений:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. ДВИЖЕНИЕ: ПОСТРОЕНИЕ
  3. КОНЦЕПЦИЯ УРОВНЕЙ ПОСТРОЕНИЯ ДВИЖЕНИЙ
  4. Хаос вопросов со строгой логикой построения
  5. II. МЕТОДИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ СИСТЕМНЫХ ОПИСАНИЙ
  6. Построение гороскопа
  7. Построение здоровья
  8. § 3. Принципы построения системы (классификации) гражданских договоров
  9. I. 3. ОБЩАЯ ХАРАКТЕРИСТИКА СИСТЕМНЫХ ОПИСАНИЙ И МЕТОДОВ ИХ ПОСТРОЕНИЯ
  10. 3. Построение информации и ее восприятие
  11. СПОСОБЫ ПОСТРОЕНИЯ НАТАЛЬНОЙ КАРТЫ
  12. Построение двойной карты
  13. Построение вторичной прогрессии
  14. 9.3. Психотехника построения высказываний
  15. 9.3. Психотехника построения высказываний
  16. Графическое построение мандалы
  17. Построение дерева целей.
  18. Порядок графического построения мандалы