Решение NP-сложных задач для деревьев
В разделе 10.1 мы разработали алгоритм для задачи о вершинном покрытии, который хорошо работает при не слишком большом размере покрытия. Было показано, что найти относительно малое вершинное покрытие намного проще, чем в полностью обобщенной задаче вершинного покрытия.
Дело даже не только в структурной простоте таких деревьев, но и в том, что многие NP-сложные задачи графов эффективно решаются в том случае, если нижележащий граф является деревом.
На качественном уровне это объясняется следующим образом: если рассмотреть поддерево входных данных с корнем в некотором узле v, решение задачи, ограничиваемое этим поддеревом, «взаимодействует» с остатком дерева через v.
Итак, рассматривая разные варианты расположения v в общем решении, мы фактически можем отделить задачу из поддерева v от задачи из остального дерева.
Чтобы формализовать этот общий подход и преобразовать его в эффективный алгоритм, потребуются определенные усилия.
Сейчас вы увидите, как это делается для разновидностей задачи о независимом множестве; однако важно помнить, что этот принцип достаточно общий, и с таким же успехом можно было рассмотреть для деревьев многие другие NP-полные задачи графов.
Сначала мы покажем, что сама задача о независимом множестве для дерева может быть решена жадным алгоритмом. Затем будет рассмотрено обобщение — задача о независимом множестве с максимальным весом, в котором узлам назначаются веса, а ищется независимое множество с максимальным весом.
Вы увидите, что задача о независимом множестве с максимальным весом решается для деревьев средствами динамического программирования с использованием довольно прямолинейной реализации описанных выше рассуждений.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу