1294
правки
Автоматическая генерация дерева поиска: различия между версиями
Материал из WEGA
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 18:12, 21 ноября 2024
, 21 ноябрь→Постановка задачи
KVN (обсуждение | вклад) (→Анализ) |
KVN (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
Эта задача связана с автоматической разработкой и анализом алгоритмов для дерева поиска. Алгоритмы поиска по дереву представляют собой популярный способ нахождения оптимальных решений для NP-полных задач (для простоты изложения рассматриваются только проблемы разрешимости; адаптация для решения задач оптимизации тривиальна). Суть этого подхода заключается в рекурсивном решении нескольких экземпляров меньшего размера таким образом, что хотя бы одна из ветвей содержит положительный ответ в том и только том случае, если его содержит исходный экземпляр. Обычно это достигается путем перебора всех возможных способов присвоить сертификат решения некоторой малой порции входных данных с получением небольшой локальной модификации на экземпляре каждой ветви. | Эта задача связана с автоматической разработкой и анализом алгоритмов для дерева поиска. Алгоритмы поиска по дереву представляют собой популярный способ нахождения оптимальных решений для NP-полных задач (для простоты изложения рассматриваются только проблемы разрешимости; адаптация для решения задач оптимизации тривиальна). Суть этого подхода заключается в рекурсивном решении нескольких экземпляров меньшего размера таким образом, что хотя бы одна из ветвей содержит положительный ответ в том и только том случае, если его содержит исходный экземпляр. Обычно это достигается путем перебора всех возможных способов присвоить сертификат решения некоторой малой порции входных данных с получением небольшой локальной модификации на экземпляре каждой ветви. | ||
Рассмотрим, к примеру, NP-полную задачу перевода в кластеры (CLUSTER EDITING): можно ли модифицировать некоторый граф путем добавления или удаления не более k ребер таким образом, чтобы полученный граф был | Рассмотрим, к примеру, NP-полную '''задачу перевода в кластеры''' (''CLUSTER EDITING problem''): можно ли модифицировать некоторый граф путем добавления или удаления не более k ребер таким образом, чтобы полученный граф был '''кластерным графом''' (''cluster graph'') , или несвязным объединением [[Клика|клик]]? Чтобы создать алгоритм поиска по дереву для 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> называется '''вектором ветвления''' (branching vector) данной рекурсии. Известно, что размер дерева поиска в таком случае составляет <math>O(\alpha^s) \, </math>, где α – '''коэффициент ветвления''' (branching number) – единственный действительный корень '''характеристического многочлена ('''characteristic polynomial''')''' | Для NP-полных задач время работы алгоритма поиска по дереву зависит только от размера дерева поиска с точностью до полиномиального множителя, который, в свою очередь, зависит от количества ветвей и сокращения размера каждой ветви. Если алгоритм решает задачу размера s и рекурсивно вызывает себя для задач с размерами s - <math>d_1</math>, ..., s - <math>d_i</math>, тогда вектор <math>(d_1, ..., d_i)</math> называется '''вектором ветвления''' (''branching vector'') данной рекурсии. Известно, что размер дерева поиска в таком случае составляет <math>O(\alpha^s) \, </math>, где α – '''коэффициент ветвления''' (''branching number'') – единственный действительный корень '''характеристического многочлена ('''''characteristic polynomial''''')''' | ||
<math>z^d \, </math> – <math>z^{d-d_1}</math> – ... – <math>z^{d-d_i}</math> (1) | <math>z^d \, </math> – <math>z^{d-d_1}</math> – ... – <math>z^{d-d_i}</math> (1) | ||
| Строка 29: | Строка 29: | ||
Грэмм и коллеги [3] описали метод получения алгоритмов быстрого поиска по дереву для CLUSTER EDITING и родственных задач, в которых мерой величины является количество операций редактирования k. Чтобы различать разные варианты, подграфы нумеруются таким образом, чтобы каждый экземпляр заведомо содержал не менее одного из этих подграфов. В рамках этого подхода можно найти ветвление для определенного варианта. | Грэмм и коллеги [3] описали метод получения алгоритмов быстрого поиска по дереву для CLUSTER EDITING и родственных задач, в которых мерой величины является количество операций редактирования k. Чтобы различать разные варианты, подграфы нумеруются таким образом, чтобы каждый экземпляр заведомо содержал не менее одного из этих подграфов. В рамках этого подхода можно найти ветвление для определенного варианта. | ||
Стандартным способом систематического получения специализированных ветвлений для вариантов экземпляров является использование сочетания | Стандартным способом систематического получения специализированных ветвлений для вариантов экземпляров является использование сочетания базового ветвления и правил редукции данных. '''Базовое ветвление''' (''basic branching'') представляет собой простейшую технику ветвления; '''правило редукции данных''' (''data reduction rule'') заменяет экземпляр эквивалентным ему по решению экземпляром меньшего размера за полиномиальное время. Для применения этого подхода к CLUSTER EDITING прежде всего требуется небольшая модификация задачи: мы будем рассматривать ''аннотированную'' версию, в которой ребро может быть помечено как ''неизменное'', а отсутствующее ребро – как ''запрещенное''. Любая аннотированная подобным образом пара вершин не подлежит последующему редактированию. Для пары вершин базовое ветвление попадает в один из двух вариантов – неизменное либо запрещенное (для одного из вариантов потребуется операция редактирования). Правила редукции заключаются в следующем: если два неизменных ребра являются смежными, третье ребро порождаемого ими треугольника также должно быть неизменным; если смежными являются неизменное и запрещенное ребра, третье ребро порождаемого ими треугольника должно быть запрещенным. | ||
На рис. 1 представлен пример подобного ветвления. | На рис. 1 представлен пример подобного ветвления. | ||
Используя усовершенствованный метод поиска места для всех возможных вариантов и для различения всех ветвлений одного варианта, Грэмм и коллеги [3] разработали несколько алгоритмов поиска по дереву для задач модификации графов. | Используя усовершенствованный метод поиска места для всех возможных вариантов и для различения всех ветвлений одного варианта, Грэмм и коллеги [3] разработали несколько алгоритмов поиска по дереву для задач модификации графов. | ||
