4551
правка
Автоматическая генерация дерева поиска: различия между версиями
Перейти к навигации
Перейти к поиску
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 14:46, 5 мая 2012
, 5 мая 2012→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
Грэмм и коллеги [3] описали метод получения алгоритмов быстрого поиска по дереву для CLUSTER EDITING и родственных задач, в которых мерой величины является количество операций редактирования k. Чтобы различать разные варианты, подграфы нумеруются таким образом, чтобы каждый экземпляр заведомо содержал не менее одного из этих подграфов. В рамках этого подхода можно найти ветвление для определенного варианта. | Грэмм и коллеги [3] описали метод получения алгоритмов быстрого поиска по дереву для CLUSTER EDITING и родственных задач, в которых мерой величины является количество операций редактирования k. Чтобы различать разные варианты, подграфы нумеруются таким образом, чтобы каждый экземпляр заведомо содержал не менее одного из этих подграфов. В рамках этого подхода можно найти ветвление для определенного варианта. | ||
Стандартным способом систематического получения специализированных ветвлений для вариантов экземпляров является использование сочетания базового ветвления и правил редукции данных. Базовое ветвление представляет собой простейшую технику ветвления; правило редукции данных заменяет экземпляр эквивалентным ему по решению экземпляром меньшего размера за полиномиальное время. Для применения этого подхода к CLUSTER EDITING прежде всего требуется небольшая модификация задачи: мы будем рассматривать аннотированную версию, в которой дуга может быть помечена как неизменная, а отсутствующая дуга – как запрещенная. Любая аннотированная подобным образом пара вершин не подлежит последующему редактированию. Для пары вершин базовое ветвление попадает в один из двух вариантов – неизменное либо запрещенное (для одного из вариантов потребуется операция редактирования). Правила редукции заключаются в следующем: если две неизменных дуги являются смежными, третья дуга порождаемого ими треугольника также должна быть неизменной; если смежными являются неизменная и запрещенная дуги, третья дуга порождаемого ими треугольника должна быть запрещенной. | Стандартным способом систематического получения специализированных ветвлений для вариантов экземпляров является использование сочетания [[базовое ветвление|базового ветвления]] и [[правила редукции данных|правил редукции данных]]. Базовое ветвление представляет собой простейшую технику ветвления; правило редукции данных заменяет экземпляр эквивалентным ему по решению экземпляром меньшего размера за полиномиальное время. Для применения этого подхода к CLUSTER EDITING прежде всего требуется небольшая модификация задачи: мы будем рассматривать ''аннотированную'' версию, в которой дуга может быть помечена как ''неизменная'', а отсутствующая дуга – как ''запрещенная''. Любая аннотированная подобным образом пара вершин не подлежит последующему редактированию. Для пары вершин базовое ветвление попадает в один из двух вариантов – неизменное либо запрещенное (для одного из вариантов потребуется операция редактирования). Правила редукции заключаются в следующем: если две неизменных дуги являются смежными, третья дуга порождаемого ими треугольника также должна быть неизменной; если смежными являются неизменная и запрещенная дуги, третья дуга порождаемого ими треугольника должна быть запрещенной. | ||
На рис. 1 представлен пример подобного ветвления. | На рис. 1 представлен пример подобного ветвления. | ||
Используя усовершенствованный метод поиска места для всех возможных вариантов и для различения всех ветвлений одного варианта, Грэмм и коллеги [3] разработали несколько алгоритмов поиска по дереву для задач модификации графов. | Используя усовершенствованный метод поиска места для всех возможных вариантов и для различения всех ветвлений одного варианта, Грэмм и коллеги [3] разработали несколько алгоритмов поиска по дереву для задач модификации графов. | ||
| Строка 48: | Строка 48: | ||
(n, 3)-MAXSAT, мера величины m 2 1.341 1.2366 [2] | (n, 3)-MAXSAT, мера величины m 2 1.341 1.2366 [2] | ||
(n, 3)-MAXSAT, мера величины l 2 1.1058 1.0983 [2] | (n, 3)-MAXSAT, мера величины l 2 1.1058 1.0983 [2] | ||
== Применение == | == Применение == | ||