Автоматическая генерация дерева поиска: различия между версиями

Рассмотрим, к примеру, NP-полную задачу перевода в кластеры (CLUSTER EDITING): можно ли модифицировать некоторый граф путем добавления или удаления не более k ребер таким образом, чтобы полученный граф был [[кластерный граф|кластерным графом]], или несвязным объединением клик? Чтобы создать алгоритм поиска по дереву для CLUSTER EDITING, следует использовать тот факт, что кластерные графы представляют собой графы, не содержащие <math>P_3</math> (путей с 3 вершинами) в качестве порожденного подграфа. Таким образом, решить задачу CLUSTER EDITING можно путем нахождения <math>P_3</math> и разделения его на три ветви следующим способом: удалить первое ребро, удалить второе ребро или добавить недостающее ребро. Согласно этой трактовке в случае, если <math>P_3</math> не найдено, мы имеем кластерный граф. Исходный экземпляр имеет решение с k модификациями в том и только том случае, если по меньшей мере одна из ветвей имеет решение с k – 1 модификациями.

Для NP-полных задач время работы алгоритма поиска по дереву зависит только от размера дерева поиска с точностью до полиномиального множителя, который, в свою очередь, зависит от количества ветвей и сокращения размера каждой ветви. Если алгоритм решает задачу размера s и рекурсивно вызывает себя для задач с размерами s - <math>d_1</math>, ..., s - <math>d_i</math>, тогда вектор <math>(d_1, ..., d_i)</math> называется [[вектор ветвления|вектором ветвления]] данной рекурсии. Известно, что размер дерева поиска в таком случае составляет <math>O(\alpha^s) \, </math>, где α – [[коэффициент ветвления]] – единственный действительный корень [[характеристический многочлен|характеристического многочлена]]

'''Задача (Алгоритм быстрого поиска по дереву)'''

'''Дано: NP-полная задача P и мера величины s(I) экземпляра I задачи P, где экземпляры I с s(I) = 0 могут быть решены за полиномиальное время.'''

Стандартным способом систематического получения специализированных ветвлений для вариантов экземпляров является использование сочетания [[базовое ветвление|базового ветвления]] и [[правила редукции данных|правил редукции данных]]. Базовое ветвление представляет собой простейшую технику ветвления; правило редукции данных заменяет экземпляр эквивалентным ему по решению экземпляром меньшего размера за полиномиальное время. Для применения этого подхода к CLUSTER EDITING прежде всего требуется небольшая модификация задачи: мы будем рассматривать ''аннотированную'' версию, в которой ребро может быть помечено как ''неизменное'', а отсутствующее ребро – как ''запрещенное''. Любая аннотированная подобным образом пара вершин не подлежит последующему редактированию. Для пары вершин базовое ветвление попадает в один из двух вариантов – неизменное либо запрещенное (для одного из вариантов потребуется операция редактирования). Правила редукции заключаются в следующем: если два неизменных ребра являются смежными, третье ребро порождаемого ими треугольника также должно быть неизменным; если смежными являются неизменное и запрещенное ребра, третье ребро порождаемого ими треугольника должно быть запрещенным.