Решение NP-сложных задач для деревьев
В этом разделе рассматриваются особые случаи ЖР-полных задач графов дру- гого типа — не с малым естественным параметром «размера», но со структурно «простым» входным графом. Вероятно, простейшей разновидностью графа яв- ляется дерево. Вспомните, что ненаправленный граф называется деревом, если он является связным и не содержит циклов. Дело даже не только в структурной простоте таких деревьев, но и в том, что многие ЖР-сложные задачи графов эф- фективно решаются в том случае, если нижележащий граф является деревом. На качественном уровне это объясняется следующим образом: если рассмотреть поддерево входных данных с корнем в некотором узле v, решение задачи, ограни- чиваемое этим поддеревом, «взаимодействует» с остатком дерева через v.
Итак, рассматривая разные варианты расположения v в общем решении, мы фактически можем отделить задачу из поддерева v от задачи из остального дерева.Чтобы формализовать этот общий подход и преобразовать его в эффективный алгоритм, потребуются определенные усилия. Сейчас вы увидите, как это делается для разновидностей задачи о независимом множестве; однако важно помнить, что этот принцип достаточно общий, и с таким же успехом можно было рассмотреть для деревьев многие другие ЖР-полные задачи графов.
Сначала мы покажем, что сама задача о независимом множестве для дерева мо- жет быть решена жадным алгоритмом. Затем будет рассмотрено обобщение — за- дача о независимом множестве с максимальным весом, в котором узлам назначаются веса, а ищется независимое множество с максимальным весом. Вы увидите, что задача о независимом множестве с максимальным весом решается для деревьев средствами динамического программирования с использованием довольно пря- молинейной реализации описанных выше рассуждений.
Еще по теме Решение NP-сложных задач для деревьев:
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ПО РЕШЕНИЮ ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ ЗАДАЧ
- Прием создания исходных благоприятных психологический условий для решения задач общения.
- ЗАДАЧА: РЕШЕНИЕ
- Слишком сложные вопросы для начала беседы.
- § 3. СТРУКТУРА РЕШЕНИЯ ПЕДАГОГИЧЕСКИХ ЗАДАЧ
- Психологические особенности решения задач.
- § 3. Мышление, интуиция, воображение в решении задач
- Правило подчинения общения решению задач правового воспитания.
- Прием достижения момента истины в решении задач разговора.
- юридико-психологические исследования решения разных правоохранительных задач
- § 1. ПОНЯТИЕ О ПЕДАГОГИЧЕСКОЙ ДЕЯТЕЛЬНОСТИ КАК ПРОЦЕССЕ НЕПРЕРЫВНОГО РЕШЕНИЯ ПРОФЕССИОНАЛЬНЫХ ЗАДАЧ
- Специфической особенностью творческих процессов решения задач является присутствие в них интуиции.
- Глава IV ПСИХОЛОГО-ПЕДАГОГИЧЕСКАЯ ДИАГНОСТИКА ПОСТУПКОВ КАК СОСТАВНАЯ ЧАСТЬ РЕШЕНИЯ ПЕДАГОГИЧЕСКИХ ЗАДАЧ
- Полное и глубокое изучение следователем и судом психологических особенностей личности обвиняемого способствует решению ряда актуальных задач.
- Задания по анализу педагогической ситуации и решению заключенных в ней педагогических задач
- ФАЗИРОВАНИЕ ПРОСТРАНСТВА ДЛЯ РЕШЕНИЯ
- Жизненная задача и высшее «Я» для мазохистского характера
- Высшее «Я» и жизненная задача для шизоидного характера
- Жизненная задача и высшее «Я» для психопатического характера