4551
правка
Автоматическая генерация дерева поиска: различия между версиями
Перейти к навигации
Перейти к поиску
м
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 14:51, 17 июля 2014
, 17 июля 2014нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 4: | Строка 4: | ||
Эта задача связана с автоматической разработкой и анализом алгоритмов для дерева поиска. Алгоритмы поиска по дереву представляют собой популярный способ нахождения оптимальных решений для NP-полных задач (для простоты изложения рассматриваются только проблемы разрешимости; адаптация для решения задач оптимизации тривиальна). Суть этого подхода заключается в рекурсивном решении нескольких экземпляров меньшего размера таким образом, что хотя бы одна из ветвей содержит положительный ответ в том и только том случае, если его содержит исходный экземпляр. Обычно это достигается путем перебора всех возможных способов присвоить сертификат решения некоторой малой порции входных данных с получением небольшой локальной модификации на экземпляре каждой ветви. | Эта задача связана с автоматической разработкой и анализом алгоритмов для дерева поиска. Алгоритмы поиска по дереву представляют собой популярный способ нахождения оптимальных решений для NP-полных задач (для простоты изложения рассматриваются только проблемы разрешимости; адаптация для решения задач оптимизации тривиальна). Суть этого подхода заключается в рекурсивном решении нескольких экземпляров меньшего размера таким образом, что хотя бы одна из ветвей содержит положительный ответ в том и только том случае, если его содержит исходный экземпляр. Обычно это достигается путем перебора всех возможных способов присвоить сертификат решения некоторой малой порции входных данных с получением небольшой локальной модификации на экземпляре каждой ветви. | ||
Рассмотрим, к примеру, NP-полную задачу перевода в кластеры (CLUSTER EDITING): можно ли модифицировать некоторый граф путем добавления или удаления не более k | Рассмотрим, к примеру, NP-полную задачу перевода в кластеры (CLUSTER EDITING): можно ли модифицировать некоторый граф путем добавления или удаления не более k ребер таким образом, чтобы полученный граф был [[кластерный граф|кластерным графом]], или несвязным объединением клик? Чтобы создать алгоритм поиска по дереву для CLUSTER EDITING, следует использовать тот факт, что кластерные графы представляют собой графы, не содержащие <math>P_3</math> (путей с 3 вершинами) в качестве порожденного подграфа. Таким образом, решить задачу CLUSTER EDITING можно путем нахождения <math>P_3</math> и разделения его на три ветви следующим способом: удалить первое ребро, удалить второе ребро или добавить недостающее ребро. Согласно этой трактовке в случае, если <math>P_3</math> не найдено, мы имеем кластерный граф. Исходный экземпляр имеет решение с k модификациями в том и только том случае, если по меньшей мере одна из ветвей имеет решение с k – 1 модификациями. | ||
== Анализ == | == Анализ == | ||
| Строка 28: | Строка 28: | ||
Грэмм и коллеги [3] описали метод получения алгоритмов быстрого поиска по дереву для CLUSTER EDITING и родственных задач, в которых мерой величины является количество операций редактирования k. Чтобы различать разные варианты, подграфы нумеруются таким образом, чтобы каждый экземпляр заведомо содержал не менее одного из этих подграфов. В рамках этого подхода можно найти ветвление для определенного варианта. | Грэмм и коллеги [3] описали метод получения алгоритмов быстрого поиска по дереву для CLUSTER EDITING и родственных задач, в которых мерой величины является количество операций редактирования k. Чтобы различать разные варианты, подграфы нумеруются таким образом, чтобы каждый экземпляр заведомо содержал не менее одного из этих подграфов. В рамках этого подхода можно найти ветвление для определенного варианта. | ||
Стандартным способом систематического получения специализированных ветвлений для вариантов экземпляров является использование сочетания [[базовое ветвление|базового ветвления]] и [[правила редукции данных|правил редукции данных]]. Базовое ветвление представляет собой простейшую технику ветвления; правило редукции данных заменяет экземпляр эквивалентным ему по решению экземпляром меньшего размера за полиномиальное время. Для применения этого подхода к CLUSTER EDITING прежде всего требуется небольшая модификация задачи: мы будем рассматривать ''аннотированную'' версию, в которой | Стандартным способом систематического получения специализированных ветвлений для вариантов экземпляров является использование сочетания [[базовое ветвление|базового ветвления]] и [[правила редукции данных|правил редукции данных]]. Базовое ветвление представляет собой простейшую технику ветвления; правило редукции данных заменяет экземпляр эквивалентным ему по решению экземпляром меньшего размера за полиномиальное время. Для применения этого подхода к CLUSTER EDITING прежде всего требуется небольшая модификация задачи: мы будем рассматривать ''аннотированную'' версию, в которой ребро может быть помечено как ''неизменное'', а отсутствующее ребро – как ''запрещенное''. Любая аннотированная подобным образом пара вершин не подлежит последующему редактированию. Для пары вершин базовое ветвление попадает в один из двух вариантов – неизменное либо запрещенное (для одного из вариантов потребуется операция редактирования). Правила редукции заключаются в следующем: если два неизменных ребра являются смежными, третье ребро порождаемого ими треугольника также должно быть неизменным; если смежными являются неизменное и запрещенное ребра, третье ребро порождаемого ими треугольника должно быть запрещенным. | ||
На рис. 1 представлен пример подобного ветвления. | На рис. 1 представлен пример подобного ветвления. | ||
Используя усовершенствованный метод поиска места для всех возможных вариантов и для различения всех ветвлений одного варианта, Грэмм и коллеги [3] разработали несколько алгоритмов поиска по дереву для задач модификации графов. | Используя усовершенствованный метод поиска места для всех возможных вариантов и для различения всех ветвлений одного варианта, Грэмм и коллеги [3] разработали несколько алгоритмов поиска по дереву для задач модификации графов. | ||
| Строка 36: | Строка 36: | ||
Автоматическая генерация дерева поиска, рис. 1 | Автоматическая генерация дерева поиска, рис. 1 | ||
Ветвление для варианта в алгоритме CLUSTER EDITING с использованием только базового ветвления на парах вершин (двойные круги) и применения правил редукции (звездочки). Неизменные | Ветвление для варианта в алгоритме CLUSTER EDITING с использованием только базового ветвления на парах вершин (двойные круги) и применения правил редукции (звездочки). Неизменные ребра обозначены жирной линией, запрещенные – пунктирной. Числа около подграфов обозначают изменение размера задачи k. Вектор ветвления имеет значение (1,2,3,3,2), что соответствует размеру дерева поиска <math>O(2.27^k) \, </math> | ||
[[Файл:ASTG tab1.png]] | [[Файл:ASTG tab1.png]] | ||