Автоматическая генерация дерева поиска

Ключевые слова и синонимы: Автоматическое доказательство для верхней границы времени выполнения алгоритмов расщепления

Постановка задачи

Эта задача связана с автоматической разработкой и анализом алгоритмов для дерева поиска. Алгоритмы поиска по дереву представляют собой популярный способ нахождения оптимальных решений для NP-полных задач (для простоты изложения рассматриваются только проблемы разрешимости; адаптация для решения задач оптимизации тривиальна). Суть этого подхода заключается в рекурсивном решении нескольких экземпляров меньшего размера таким образом, что хотя бы одна из ветвей содержит положительный ответ в том и только том случае, если его содержит исходный экземпляр. Обычно это достигается путем перебора всех возможных способов присвоить сертификат решения некоторой малой порции входных данных с получением небольшой локальной модификации на экземпляре каждой ветви.

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

Анализ

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

[math]\displaystyle{ z^d \, }[/math] – [math]\displaystyle{ z^{d-d_1} }[/math] – ... – [math]\displaystyle{ z^{d-d_i} }[/math] (1)

где d = max{[math]\displaystyle{ d_1, ..., d_i }[/math]}. Для простого алгоритма поиска по дереву CLUSTER EDITING и размера k вектор ветвления имеет значение (1,1,1), а коэффициент ветвления равен 3, что означает, что время выполнения содержит полиномиальный коэффициент [math]\displaystyle{ O(3^k) \, }[/math].

Различение вариантов

Нередко время выполнения можно улучшить, если различать разные варианты экземпляров и производить ветвление отдельно для каждого варианта. В таком случае время выполнения будет определяться коэффициентом ветвления наихудшего варианта. В нескольких публикациях такие алгоритмы были получены вручную (например, дерево поиска размера [math]\displaystyle{ O(2.27^k) \, }[/math] для CLUSTER EDITING [4]); однако эту задачу можно автоматизировать. Сформулируем ее следующим образом:

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

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

Требуется: Разбить множество экземпляров P на варианты и для каждого варианта найти такое ветвление, чтобы максимальный коэффициент ветвления среди всех ветвлений был минимальным из возможных.

Это определение задачи не вполне конкретно; в частности, необходимо иметь возможность быстро распознать вариант, к которому принадлежит экземпляр. Также неясно, существует ли оптимальный алгоритм поиска по дереву; можно полагать, что коэффициент ветвления можно последовательно уменьшать, повышая сложность различения вариантов.

Основные результаты

Грэмм и коллеги [3] описали метод получения алгоритмов быстрого поиска по дереву для CLUSTER EDITING и родственных задач, в которых мерой величины является количество операций редактирования k. Чтобы различать разные варианты, подграфы нумеруются таким образом, чтобы каждый экземпляр заведомо содержал не менее одного из этих подграфов. В рамках этого подхода можно найти ветвление для определенного варианта.

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

Автоматическая генерация дерева поиска, рис. 1

Ветвление для варианта в алгоритме CLUSTER EDITING с использованием только базового ветвления на парах вершин (двойные круги) и применения правил редукции (звездочки). Неизменные ребра обозначены жирной линией, запрещенные – пунктирной. Числа около подграфов обозначают изменение размера задачи k. Вектор ветвления имеет значение (1,2,3,3,2), что соответствует размеру дерева поиска [math]\displaystyle{ O(2.27^k) \, }[/math]

Автоматическая генерация дерева поиска, таблица 1

Сводные данные по размерам деревьев поиска, в которых автоматизация привела к улучшению. Сравниваются тривиальные, известные и новые алгоритмы. Под «известным» понимается лучшее из ранее опубликованных деревьев поиска, созданных вручную. Здесь m обозначает количество дизъюнктов, а l – длину формулы

Применение

Грамметал [3] применял автоматизированное создание алгоритмов поиска по дереву для нескольких задач модификации графов (см. также таблицу 1). Хиффнер [5] продемонстрировал применение алгоритма DOMINATING SET на графах степенью не выше 4, при этом мерой величины является размер доминирующего множества.

Федин и Куликов [2] исследовали варианты алгоритма SAT; однако в их работе была доказана только верхняя граница для фиксированного алгоритма, сами же алгоритмы не строились. Скьернаа [6] также представил результаты различных вариантов алгоритма SAT; его подход не требует введения пользователем правил редукции данных – они определяются автоматически.

Открытые вопросы

Анализ алгоритмов поиска по дереву можно значительно улучшить, если описывать «размер» экземпляра при помощи более чем одной переменной, что приводит к возникновению многовариантных рекуррентностей [1]. Использование этого подхода при автоматизированном написании алгоритмов пока еще является делом будущего. Не раз отмечалось, что улучшенные временные границы, полученные в результате различения большего количества вариантов, не обязательно ускоряют выполнение программы, но могут даже замедлить его. Тщательное изучение компромиссов, связанных с соответствующей адаптацией автоматизированных схем, еще ждет своих исследователей.

Экспериментальные результаты Грэмм и коллеги [3], а также Хиффнер [5] разработали алгоритмы поиска по дереву для нескольких NP-полных задач. Федин и Куликов [2] и Скъернаа [6] также добились результатов в нахождении удовлетворительных вариантов. Сводные данные приведены в таблице 1.

См. также

• Вершинное покрытие и деревья поиска

Литература

1. Eppstein, D.: Quasiconvex analysis of backtracking algorithms. In: Proc. 15th SODA, ACM/SIAM, pp. 788-797 (2004)

2. Fedin, S.S., Kulikov, A.S.: Automated proofs of upper bounds on the running time of splitting algorithms. J. Math. Sci. 134, 2383-2391 (2006). Улучшенные результаты можно найти по адресу по адресу http://logic.pdmi.ras.ru/~kulikov/autoproofs.html

3. Gramm, J., Guo, J., HCiffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39, 321-347 (2004)

4. Gramm, J., Guo, J., HCiffner, F., Niedermeier, R.: Graph-modeled data clustering: Exact algorithms for clique generation. Theor. Comput. Syst. 38, 373-392 (2005)

5. HCiffner, F.: Graph Modification Problems and Automated Search Tree Generation. Diplomarbeit, Wilhelm-Schickard-Institut fur Informatik, Universitat Tubingen (2003)

6. Skjernaa, B.: Exact Algorithms for Variants of Satisfiability and Colouring Problems. Ph. D. thesis, University of Aarhus, Department of Computer Science (2004)