4501
правка
Супердерево максимального соответствия: различия между версиями
Материал из WEGA
Супердерево максимального соответствия (посмотреть исходный код)
Версия от 00:19, 2 ноября 2015
, 2 ноября 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
Лемма 1 ([8]). Для любого множества <math>D = \{ T_1, T_2, ..., T_k \} \;</math> корневых неупорядоченных деревьев с уникальными метками листьев, таких, что <math>\Lambda(T_1) = \Lambda(T_2) = ... = \Lambda(T_k) \;</math>, оптимальное решение задачи MASP для D является оптимальным решением задачи MAST для D, и наоборот. | '''Лемма 1 ([8]). Для любого множества <math>D = \{ T_1, T_2, ..., T_k \} \;</math> корневых неупорядоченных деревьев с уникальными метками листьев, таких, что <math>\Lambda(T_1) = \Lambda(T_2) = ... = \Lambda(T_k) \;</math>, оптимальное решение задачи MASP для D является оптимальным решением задачи MAST для D, и наоборот.''' | ||
| Строка 28: | Строка 28: | ||
Теорема 2. ([8]) Если k = 2 (имеются два дерева), супердерево максимального соответствия может быть найдено за время <math>O(T_{MAST} + n) \;</math>, где <math>T_{MAST} \;</math> – время, необходимое для вычисления поддерева максимального соответствия двух деревьев с O(n) листьями. Заметим, что <math>T_{MAST} = O( \sqrt{Dn} \; log(2n/D)) \;</math> (см. [9]). | '''Теорема 2. ([8]) Если k = 2 (имеются два дерева), супердерево максимального соответствия может быть найдено за время <math>O(T_{MAST} + n) \;</math>, где <math>T_{MAST} \;</math> – время, необходимое для вычисления поддерева максимального соответствия двух деревьев с O(n) листьями. Заметим, что <math>T_{MAST} = O( \sqrt{Dn} \; log(2n/D)) \;</math> (см. [9]).''' | ||
В [11] было приведено обобщение теоремы 2 и предложено следующее решение. | В [11] было приведено обобщение теоремы 2 и предложено следующее решение. | ||
Теорема 3 ([1]). Для любого фиксированного k > 2 в случае, если каждый лист D встречается в 1 дереве либо в k деревьев, супердерево максимального соответствия может быть найдено за время O( | Теорема 3 ([1]). Для любого фиксированного k > 2 в случае, если каждый лист D встречается в 1 дереве либо в k деревьев, супердерево максимального соответствия может быть найдено за время <math>O(T'_{MAST} + kn) \;</math>, где <math>T'_{MAST} \;</math> – время, необходимое для вычисления поддерева максимального соответствия k деревьев с метками листьев из <math>\bigcap_{T_i \in D} \Lambda(T_i) \;</math>. Заметим, что <math>T'_{MAST} = O(km^3 + m^D) \;</math>, где <math>n = | \bigcap_{T_i \in D} \Lambda(T_i) | \;</math> (см. [4]). | ||
