4551
правка
Супердерево максимального соответствия: различия между версиями
Материал из WEGA
Супердерево максимального соответствия (посмотреть исходный код)
Версия от 00:22, 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 деревьев, супердерево максимального соответствия может быть найдено за время <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]). | '''Теорема 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]). | ||
Следующие две теоремы доказывают, что в общем случае задача вычисления супердерева максимального соответствия является NP-полной. | Следующие две теоремы доказывают, что в общем случае задача вычисления супердерева максимального соответствия является NP-полной. | ||
'''Теорема 4 ([8, 1])'''. Для любого фиксированного <math>k \ge 3 \;</math> задача MASP с неограниченной величиной D является NP-полной. Более того, задача MASP является NP-полной даже в случае, когда мы ограничиваемся корневыми триплетами. (Корневой триплет – это бинарное корневое неупорядоченное дерево с уникальными метками листьев, имеющее три листа). | |||
Теорема 5 ([1]). Задача MASP не может быть приближенно решена за полиномиальное время с константным множителем, если только не верно соотношение P = | |||
'''Теорема 5 ([1])'''. Задача MASP не может быть приближенно решена за полиномиальное время с константным множителем, если только не верно соотношение <math>\mathcal{P} = \mathcal{N} \mathcal{P}</math>. | |||
