Построение решений
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.
Еще по теме Построение решений:
- § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
- ДВИЖЕНИЕ: ПОСТРОЕНИЕ
- КОНЦЕПЦИЯ УРОВНЕЙ ПОСТРОЕНИЯ ДВИЖЕНИЙ
- Хаос вопросов со строгой логикой построения
- II. МЕТОДИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ СИСТЕМНЫХ ОПИСАНИЙ
- Построение гороскопа
- Построение здоровья
- § 3. Принципы построения системы (классификации) гражданских договоров
- I. 3. ОБЩАЯ ХАРАКТЕРИСТИКА СИСТЕМНЫХ ОПИСАНИЙ И МЕТОДОВ ИХ ПОСТРОЕНИЯ
- 3. Построение информации и ее восприятие
- СПОСОБЫ ПОСТРОЕНИЯ НАТАЛЬНОЙ КАРТЫ
- Построение двойной карты
- Построение вторичной прогрессии
- 9.3. Психотехника построения высказываний
- 9.3. Психотехника построения высказываний
- Графическое построение мандалы
- Построение дерева целей.
- Порядок графического построения мандалы