4551
правка
Автоматическая генерация дерева поиска: различия между версиями
Материал из WEGA
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 14:44, 5 мая 2012
, 5 мая 2012→Различение вариантов
Irina (обсуждение | вклад) (→Анализ) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
== Различение вариантов == | == Различение вариантов == | ||
Нередко время исполнения можно улучшить, если различать разные варианты экземпляров и производить ветвление отдельно для каждого варианта. В таком случае время исполнения будет определяться коэффициентом ветвления наихудшего варианта. В нескольких публикациях такие алгоритмы были получены вручную (например, дерево поиска размера O(2. | Нередко время исполнения можно улучшить, если различать разные варианты экземпляров и производить ветвление отдельно для каждого варианта. В таком случае время исполнения будет определяться коэффициентом ветвления наихудшего варианта. В нескольких публикациях такие алгоритмы были получены вручную (например, дерево поиска размера <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 на варианты и для каждого варианта найти такое ветвление, чтобы максимальный коэффициент ветвления среди всех ветвлений был минимальным из возможных.''' | ||
