4511
правок
Супердерево максимального соответствия: различия между версиями
Перейти к навигации
Перейти к поиску
м
Супердерево максимального соответствия (посмотреть исходный код)
Версия от 14:31, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 12 промежуточных версий этого же участника) | |||
| Строка 12: | Строка 12: | ||
Задача 1. Пусть D = | Задача 1. Пусть <math>D = \{ T_1, T_2, ..., T_k \} \;</math> – множество корневых неупорядоченных деревьев, в котором каждое дерево <math>T_i \;</math> имеет уникальные метки листьев, при этом множества меток листьев <math>\Lambda (T_i) \;</math> могут перекрываться. Задача нахождения супердерева максимального соответствия заключается в построении дерева <math>Q \;</math> с уникальными метками листьев, с множеством меток листьев <math>\Lambda (Q) \subseteq \bigcup_{T_i \in D} \Lambda (T_i) \;</math>, таким, что <math>| \Lambda (Q) | \;</math> максимально и для каждого <math>T_i \in D \;</math> топологическое ограничение <math>T_i \;</math> согласно <math>\Lambda (Q) \;</math> изоморфно топологическому ограничению <math>Q \;</math> согласно <math>\Lambda (T_i) \;</math>. | ||
Далее будут использоваться следующие обозначения: n = \{ | Далее будут использоваться следующие обозначения: <math>n = | \bigcup_{T_i \in D} \Lambda (T_i) | \;</math>, <math>k = | D | \;</math> и <math>D = max_{T_i \in D} \big\{ deg(T_i) \big\} \;</math>, где <math>deg(T_i) \;</math> – степень <math>T_i \;</math>. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 22: | Строка 22: | ||
Лемма 1 ([8]). Для любого множества 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 (имеются два дерева), супердерево максимального соответствия может быть найдено за время O( | '''Теорема 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]). | ||
Следующие две теоремы доказывают, что в общем случае задача вычисления супердерева максимального соответствия является NP-полной. | Следующие две теоремы доказывают, что в общем случае задача вычисления супердерева максимального соответствия является NP-полной. | ||
'''Теорема 4 ([8, 1])'''. Для любого фиксированного <math>k \ge 3 \;</math> задача MASP с неограниченной величиной D является NP-полной. Более того, задача MASP является NP-полной даже в случае, когда мы ограничиваемся корневыми триплетами. (Корневой триплет – это бинарное корневое неупорядоченное дерево с уникальными метками листьев, имеющее три листа). | |||
'''Теорема 5 ([1])'''. Задача MASP не может быть приближенно решена за полиномиальное время с константным множителем, если только не верно соотношение <math>\mathcal{P} = \mathcal{N} \mathcal{P}</math>. | |||
Хотя задача MASP является NP-полной, существует аппроксимационный алгоритм для ее приближенного решения. | |||
'''Теорема 6 ([8])'''. Задача MASP может быть приближенно решена с множителем <math>\frac{n}{log \; n}</math> за время <math>O(n^2) \cdot min \{ O(k \cdot (log \; log \; n)^2), O(k + log \; n \cdot log \; log \; n) \} </math>. MASP, ограниченная корневыми триплетами, может быть приближенно решена с множителем <math>\frac{n}{log \; n}</math> за время <math>O(k + n^2 log^2 \; n)</math>. | |||
Также существуют алгоритмы вычисления MASP с фиксированными параметрами и полиномиальным временем решения. Случай с множеством k бинарных деревьев T с n различных меток листьев рассматривался множеством исследователей. Дженссон и коллеги [8] первыми предложили алгоритм вычисления MAST на T с временем выполнения <math>O(k(2n^2)^{3k^2}) \;</math>. Недавно Гийемо и Берри [5] улучшили это время до <math>O((8n)^k) \;</math>; Хоанг и Сунг [7] снизили его до <math>O((6n)^k) \;</math>, что показано в теореме 7. | |||
'''Теорема 7 ([7])'''. Пусть дано множество k бинарных деревьев T с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время <math>O((6n)^k) \;</math>. | |||
Для случая, когда множество k бинарных деревьев T имеют степень D и n различных меток листьев, Хоанг и Сунг [7] предложили следующее решение для нахождения MASP с фиксированными параметрами и полиномиальным временем выполнения. | |||
'''Теорема 8 ([7])'''. Пусть дано множество k бинарных деревьев T степени D с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время <math>O((kD)^{kD+3} (2n)^k) \;</math>. | |||
== Применение == | == Применение == | ||
| Строка 69: | Строка 71: | ||
Задача 2. Пусть D = | '''Задача 2'''. Пусть <math>D = \{ T_1, T_2, ..., T_k \} \;</math> – множество корневых неупорядоченных деревьев, в котором каждое дерево <math>T_i \;</math> имеет уникальные метки листьев, при этом множества меток листьев <math>\Lambda(T_i) \;</math> могут перекрываться. Задача нахождения супердерева максимальной совместимости (MCSP) заключается в построении дерева <math>Q \;</math> с уникальными метками листьев, с множеством меток листьев <math>\Lambda(Q) \subseteq \bigcup_{T_i \in D} \Lambda(T_i) \;</math>, таким, что <math>| \Lambda(Q) | \;</math> максимально и для каждого <math>T_i \in D \;</math> топологическое ограничение поддерева <math>Q_i' \;</math> дерева <math>Q \;</math> согласно <math>\Lambda(T_i) \;</math> уточняет топологическое ограничение <math>T'_i \;</math> согласно <math>T_i \;</math>; иначе говоря, <math>T'_i \;</math> может быть получено путем коллапсирования определенных ребер <math>Q'_i \;</math>. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 78: | Строка 79: | ||
== См. также == | == См. также == | ||
* ''[[Поддерево максимального соответствия|Поддерево максимального соответствия (для двух бинарных деревьев)]] | |||
* ''[[Поддерево максимального соответствия (для трех или более деревьев)]] | |||
* ''[[Дерево максимальной совместимости]] | |||
== Литература == | == Литература == | ||