4501
правка
Поддерево максимального соответствия (для трех или более деревьев): различия между версиями
Перейти к навигации
Перейти к поиску
Поддерево максимального соответствия (для трех или более деревьев) (посмотреть исходный код)
Версия от 23:02, 24 сентября 2015
, 24 сентября 2015→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
Вспомним, что классический динамический алгоритм вычисления MAST для двух бинарных деревьев за время O( | Вспомним, что классический динамический алгоритм вычисления MAST для двух бинарных деревьев за время <math>O(n^2) \;</math> [11] обрабатывает все пары внутренних вершин двух деревьев восходящим образом. Для каждой пары таких вершин он вычисляет значение MAST для поддеревьев, корнями которых являются вершины этой пары. Имеется <math>O(n^2) \;</math> пар таких вершин; значение MAST для поддеревьев, корнями которых является заданная пара вершин, может быть вычислено за константное время из значений MAST ранее обработанных пар вершин. | ||
Чтобы подготовить почву для более общего случая, обозначим за k-MAST( | Чтобы подготовить почву для более общего случая, обозначим за <math>k-MAST(\overrightarrow{v}) \;</math> решение задачи k-MAST для поддеревьев <math>T^1(v_1), ..., T^k(v_k) \;</math>, где <math>T^i(v_i) \;</math> – поддерево <math>T^i \;</math> с корнем <math>v_i \;</math>. Если для всех i <math>u_i \;</math> является непосредственным потомком <math>v_i \;</math> в <math>T^i \;</math>, то <math>\overrightarrow{v} \;</math> доминирована <math>\overrightarrow{u} \;</math> (обозначается <math>\overrightarrow{v} \prec \overrightarrow{u} \;</math>). | ||