4551
правка
Автоматическая генерация дерева поиска: различия между версиями
Материал из WEGA
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 14:35, 5 мая 2012
, 5 мая 2012→Анализ
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) (→Анализ) |
||
| Строка 7: | Строка 7: | ||
== Анализ == | == Анализ == | ||
Для NP-полных задач время работы алгоритма поиска по дереву зависит только от размера дерева поиска с точностью до полиномиального множителя, который, в свою очередь, зависит от количества ветвей и сокращения размера каждой ветви. Если алгоритм решает задачу размера s и рекурсивно вызывает себя для задач с размерами s | Для NP-полных задач время работы алгоритма поиска по дереву зависит только от размера дерева поиска с точностью до полиномиального множителя, который, в свою очередь, зависит от количества ветвей и сокращения размера каждой ветви. Если алгоритм решает задачу размера s и рекурсивно вызывает себя для задач с размерами s - <math>d_1</math>, ..., s - <math>d_i</math>, тогда вектор <math>(d_1, ..., d_i)</math> называется [[вектор ветвления|вектором ветвления]] данной рекурсии. Известно, что размер дерева поиска в таком случае составляет <math>O(\alpha^s) \, </math>, где α – [[коэффициент ветвления]] – единственный действительный корень [[характеристический многочлен|характеристического многочлена]] | ||
где d = max{ | <math>z^d \, </math> – <math>z^{d-d_1}</math> – ... – <math>z^{d-d_i}</math> (1) | ||
где d = max{<math>d_1, ..., d_i</math>}. Для простого алгоритма поиска по дереву CLUSTER EDITING и размера k вектор ветвления имеет значение (1,1,1), а коэффициент ветвления равен 3, что означает, что время исполнения содержит полиномиальный коэффициент <math>O(3^k) \,</math>. | |||
== Различение вариантов == | == Различение вариантов == | ||
