<<
>>

Решение NP-сложных задач для деревьев

В разделе 10.1 мы разработали алгоритм для задачи о вершинном покрытии, кото- рый хорошо работает при не слишком большом размере покрытия. Было показано, что найти относительно малое вершинное покрытие намного проще, чем в полно- стью обобщенной задаче вершинного покрытия.

В этом разделе рассматриваются особые случаи ЖР-полных задач графов дру- гого типа — не с малым естественным параметром «размера», но со структурно «простым» входным графом. Вероятно, простейшей разновидностью графа яв- ляется дерево. Вспомните, что ненаправленный граф называется деревом, если он является связным и не содержит циклов. Дело даже не только в структурной простоте таких деревьев, но и в том, что многие ЖР-сложные задачи графов эф- фективно решаются в том случае, если нижележащий граф является деревом. На качественном уровне это объясняется следующим образом: если рассмотреть поддерево входных данных с корнем в некотором узле v, решение задачи, ограни- чиваемое этим поддеревом, «взаимодействует» с остатком дерева через v.

Итак, рассматривая разные варианты расположения v в общем решении, мы фактически можем отделить задачу из поддерева v от задачи из остального дерева.

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

Сначала мы покажем, что сама задача о независимом множестве для дерева мо- жет быть решена жадным алгоритмом. Затем будет рассмотрено обобщение — за- дача о независимом множестве с максимальным весом, в котором узлам назначаются веса, а ищется независимое множество с максимальным весом. Вы увидите, что задача о независимом множестве с максимальным весом решается для деревьев средствами динамического программирования с использованием довольно пря- молинейной реализации описанных выше рассуждений.

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

Еще по теме Решение NP-сложных задач для деревьев:

  1. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  2. ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ПО РЕШЕНИЮ ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ ЗАДАЧ
  3. Прием создания исходных благоприятных психологический условий для решения задач общения.
  4. ЗАДАЧА: РЕШЕНИЕ
  5. Слишком сложные вопросы для начала беседы.
  6. § 3. СТРУКТУРА РЕШЕНИЯ ПЕДАГОГИЧЕСКИХ ЗАДАЧ
  7. Психологические особенности решения задач.
  8. § 3. Мышление, интуиция, воображение в решении задач
  9. Правило подчинения общения решению задач правового воспитания.
  10. Прием достижения момента истины в решении задач разговора.
  11. юридико-психологические исследования решения разных правоохранительных задач
  12. § 1. ПОНЯТИЕ О ПЕДАГОГИЧЕСКОЙ ДЕЯТЕЛЬНОСТИ КАК ПРОЦЕССЕ НЕПРЕРЫВНОГО РЕШЕНИЯ ПРОФЕССИОНАЛЬНЫХ ЗАДАЧ
  13. Специфической особенностью творческих процессов решения задач является присутствие в них интуиции.
  14. Глава IV ПСИХОЛОГО-ПЕДАГОГИЧЕСКАЯ ДИАГНОСТИКА ПОСТУПКОВ КАК СОСТАВНАЯ ЧАСТЬ РЕШЕНИЯ ПЕДАГОГИЧЕСКИХ ЗАДАЧ
  15. Полное и глубокое изучение следователем и судом психологических особенностей личности обвиняемого способствует решению ряда актуальных задач.
  16. Задания по анализу педагогической ситуации и решению заключенных в ней педагогических задач
  17. ФАЗИРОВАНИЕ ПРОСТРАНСТВА ДЛЯ РЕШЕНИЯ
  18. Жизненная задача и высшее «Я» для мазохистского характера
  19. Высшее «Я» и жизненная задача для шизоидного характера
  20. Жизненная задача и высшее «Я» для психопатического характера