4551
правка
Автоматическая генерация дерева поиска: различия между версиями
Материал из WEGA
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 14:45, 5 мая 2012
, 5 мая 2012→Различение вариантов
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
Нередко время исполнения можно улучшить, если различать разные варианты экземпляров и производить ветвление отдельно для каждого варианта. В таком случае время исполнения будет определяться коэффициентом ветвления наихудшего варианта. В нескольких публикациях такие алгоритмы были получены вручную (например, дерево поиска размера <math>O(2.27^k) \, </math> для CLUSTER EDITING [4]); однако эту задачу можно автоматизировать. Сформулируем ее следующим образом: | Нередко время исполнения можно улучшить, если различать разные варианты экземпляров и производить ветвление отдельно для каждого варианта. В таком случае время исполнения будет определяться коэффициентом ветвления наихудшего варианта. В нескольких публикациях такие алгоритмы были получены вручную (например, дерево поиска размера <math>O(2.27^k) \, </math> для CLUSTER EDITING [4]); однако эту задачу можно автоматизировать. Сформулируем ее следующим образом: | ||
'''Задача (Алгоритм быстрого поиска по дереву) | '''Задача (Алгоритм быстрого поиска по дереву)''' | ||
Дано: NP-полная задача P и мера величины s(I) экземпляра I задачи P, где экземпляры I с s(I) = 0 могут быть решены за полиномиальное время. | '''Дано: NP-полная задача P и мера величины s(I) экземпляра I задачи P, где экземпляры I с s(I) = 0 могут быть решены за полиномиальное время.''' | ||
Требуется: Разбить множество экземпляров P на варианты и для каждого варианта найти такое ветвление, чтобы максимальный коэффициент ветвления среди всех ветвлений был минимальным из возможных.''' | '''Требуется: Разбить множество экземпляров P на варианты и для каждого варианта найти такое ветвление, чтобы максимальный коэффициент ветвления среди всех ветвлений был минимальным из возможных.''' | ||
