4551
правка
Автоматическая генерация дерева поиска: различия между версиями
Перейти к навигации
Перейти к поиску
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 14:29, 5 мая 2012
, 5 мая 2012→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
Эта задача связана с автоматической разработкой и анализом алгоритмов для дерева поиска. Алгоритмы поиска по дереву представляют собой популярный способ нахождения оптимальных решений для NP-полных задач (для простоты изложения рассматриваются только проблемы разрешимости; адаптация для решения задач оптимизации тривиальна). Суть этого подхода заключается в рекурсивном решении нескольких экземпляров меньшего размера таким образом, что хотя бы одна из ветвей содержит положительный ответ в том и только том случае, если его содержит исходный экземпляр. Обычно это достигается путем перебора всех возможных способов присвоить сертификат решения некоторой малой порции входных данных с получением небольшой локальной модификации на экземпляре каждой ветви. | Эта задача связана с автоматической разработкой и анализом алгоритмов для дерева поиска. Алгоритмы поиска по дереву представляют собой популярный способ нахождения оптимальных решений для NP-полных задач (для простоты изложения рассматриваются только проблемы разрешимости; адаптация для решения задач оптимизации тривиальна). Суть этого подхода заключается в рекурсивном решении нескольких экземпляров меньшего размера таким образом, что хотя бы одна из ветвей содержит положительный ответ в том и только том случае, если его содержит исходный экземпляр. Обычно это достигается путем перебора всех возможных способов присвоить сертификат решения некоторой малой порции входных данных с получением небольшой локальной модификации на экземпляре каждой ветви. | ||
Рассмотрим, к примеру, NP-полную задачу перевода в кластеры (CLUSTER EDITING): можно ли модифицировать некоторый граф путем добавления или удаления не более k дуг таким образом, чтобы полученный граф был кластерным графом, или несвязным объединением клик? Чтобы создать алгоритм поиска по дереву для CLUSTER EDITING, следует использовать тот факт, что кластерные графы представляют собой графы, не содержащие | Рассмотрим, к примеру, NP-полную задачу перевода в кластеры (CLUSTER EDITING): можно ли модифицировать некоторый граф путем добавления или удаления не более k дуг таким образом, чтобы полученный граф был [[кластерный граф|кластерным графом]], или несвязным объединением клик? Чтобы создать алгоритм поиска по дереву для CLUSTER EDITING, следует использовать тот факт, что кластерные графы представляют собой графы, не содержащие <math>P_3</math> (путей с 3 вершинами) в качестве порожденного подграфа. Таким образом, решить задачу CLUSTER EDITING можно путем нахождения <math>P_3</math> и разделения его на три ветви следующим способом: удалить первую дугу, удалить вторую дугу или добавить недостающую дугу. Согласно этой трактовке в случае, если <math>P_3</math> не найдено, мы имеем кластерный граф. Исходный экземпляр имеет решение с k модификациями в том и только том случае, если по меньшей мере одна из ветвей имеет решение с k – 1 модификациями. | ||
== Анализ == | == Анализ == | ||