1294
правки
Автоматическая генерация дерева поиска: различия между версиями
Перейти к навигации
Перейти к поиску
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 18:03, 21 ноября 2024
, 21 ноябрь→Анализ
Irina (обсуждение | вклад) мНет описания правки |
KVN (обсуждение | вклад) (→Анализ) |
||
| Строка 7: | Строка 7: | ||
== Анализ == | == Анализ == | ||
Для NP-полных задач время работы алгоритма поиска по дереву зависит только от размера дерева поиска с точностью до полиномиального множителя, который, в свою очередь, зависит от количества ветвей и сокращения размера каждой ветви. Если алгоритм решает задачу размера s и рекурсивно вызывает себя для задач с размерами s - <math>d_1</math>, ..., s - <math>d_i</math>, тогда вектор <math>(d_1, ..., d_i)</math> называется | Для 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) | ||
| Строка 16: | Строка 16: | ||
Нередко время выполнения можно улучшить, если различать разные варианты экземпляров и производить ветвление отдельно для каждого варианта. В таком случае время выполнения будет определяться коэффициентом ветвления наихудшего варианта. В нескольких публикациях такие алгоритмы были получены вручную (например, дерево поиска размера <math>O(2.27^k) \, </math> для CLUSTER EDITING [4]); однако эту задачу можно автоматизировать. Сформулируем ее следующим образом: | Нередко время выполнения можно улучшить, если различать разные варианты экземпляров и производить ветвление отдельно для каждого варианта. В таком случае время выполнения будет определяться коэффициентом ветвления наихудшего варианта. В нескольких публикациях такие алгоритмы были получены вручную (например, дерево поиска размера <math>O(2.27^k) \, </math> для CLUSTER EDITING [4]); однако эту задачу можно автоматизировать. Сформулируем ее следующим образом: | ||
'''Задача | '''Задача.''' ''Алгоритм быстрого поиска по дереву'' '''('''''Fast search tree algorithm''''')''' | ||
'''Дано: NP-полная задача P и мера величины s(I) экземпляра I задачи P, где экземпляры I с s(I) = 0 могут быть решены за полиномиальное время.''' | '''Дано:''' ''NP-полная задача P и мера величины s(I) экземпляра I задачи P, где экземпляры I с s(I) = 0 могут быть решены за полиномиальное время'''''.''' | ||
'''Требуется:''' ''Разбить множество экземпляров P на варианты и для каждого варианта найти такое ветвление, чтобы максимальный коэффициент ветвления среди всех ветвлений был минимальным из возможных.'' | |||