4446
правок
Автоматическая генерация дерева поиска: различия между версиями
Материал из WEGA
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 14:20, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 1: | Строка 1: | ||
Ключевые слова и синонимы: [[Автоматическое доказательство для верхней границы времени | Ключевые слова и синонимы: [[Автоматическое доказательство для верхней границы времени выполнения алгоритмов расщепления]] | ||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 11: | Строка 11: | ||
<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) | ||
где d = max{<math>d_1, ..., d_i</math>}. Для простого алгоритма поиска по дереву CLUSTER EDITING и размера k вектор ветвления имеет значение (1,1,1), а коэффициент ветвления равен 3, что означает, что время | где d = max{<math>d_1, ..., d_i</math>}. Для простого алгоритма поиска по дереву CLUSTER EDITING и размера k вектор ветвления имеет значение (1,1,1), а коэффициент ветвления равен 3, что означает, что время выполнения содержит полиномиальный коэффициент <math>O(3^k) \,</math>. | ||
== Различение вариантов == | == Различение вариантов == | ||
Нередко время | Нередко время выполнения можно улучшить, если различать разные варианты экземпляров и производить ветвление отдельно для каждого варианта. В таком случае время выполнения будет определяться коэффициентом ветвления наихудшего варианта. В нескольких публикациях такие алгоритмы были получены вручную (например, дерево поиска размера <math>O(2.27^k) \, </math> для CLUSTER EDITING [4]); однако эту задачу можно автоматизировать. Сформулируем ее следующим образом: | ||
'''Задача (Алгоритм быстрого поиска по дереву)''' | '''Задача (Алгоритм быстрого поиска по дереву)''' | ||
| Строка 52: | Строка 52: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Анализ алгоритмов поиска по дереву можно значительно улучшить, если описывать «размер» экземпляра при помощи более чем одной переменной, что приводит к возникновению многовариантных рекуррентностей [1]. Использование этого подхода при автоматизированном написании алгоритмов пока еще является делом будущего. | Анализ алгоритмов поиска по дереву можно значительно улучшить, если описывать «размер» экземпляра при помощи более чем одной переменной, что приводит к возникновению многовариантных рекуррентностей [1]. Использование этого подхода при автоматизированном написании алгоритмов пока еще является делом будущего. | ||
Не раз отмечалось, что улучшенные временные границы, полученные в результате различения большего количества вариантов, не обязательно ускоряют | Не раз отмечалось, что улучшенные временные границы, полученные в результате различения большего количества вариантов, не обязательно ускоряют выполнение программы, но могут даже замедлить его. Тщательное изучение компромиссов, связанных с соответствующей адаптацией автоматизированных схем, еще ждет своих исследователей. | ||
Экспериментальные результаты | Экспериментальные результаты | ||
