Супердерево максимального соответствия: различия между версиями

Перейти к навигации Перейти к поиску

Супердерево максимального соответствия (посмотреть исходный код)

Версия от 14:31, 1 октября 2023

973 байта добавлено ,  1 октября 2023
м
нет описания правки
мНет описания правки
 
(не показано 10 промежуточных версий этого же участника)
Строка 22: Строка 22:




Лемма 1 ([8]). Для любого множества D = fT1;T2... Tkg корневых неупорядоченных деревьев с уникальными метками листьев, таких, что A(T\) = A(T2) = : : : = A(Ti), оптимальное решение задачи 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 (имеются два дерева), супердерево максимального соответствия может быть найдено за время O(TMAST+ n), где TMAST – время, необходимое для вычисления поддерева максимального соответствия двух деревьев с O(n) листьями. Заметим, что TMAST = 0(-jDn\og{2nlD)) (см. [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(TMAST0 + kn), где TMAST0 – время, необходимое для вычисления поддерева максимального соответствия k деревьев с метками листьев из TT 2D A(Tj). Заметим, что T^sr = O(km3 + mD), где n = |Пг;ео А(Щ (см. [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]). Для любого фиксированного k > 3 задача MASP с неограниченной величиной D является NP-полной. Более того, задача MASP является NP-полной даже в случае, когда мы ограничиваемся корневыми триплетами. (Корневой триплет – это бинарное корневое неупорядоченное дерево с уникальными метками листьев, имеющее три листа).


'''Теорема 4 ([8, 1])'''. Для любого фиксированного <math>k \ge 3 \;</math> задача MASP с неограниченной величиной D является NP-полной. Более того, задача MASP является NP-полной даже в случае, когда мы ограничиваемся корневыми триплетами. (Корневой триплет – это бинарное корневое неупорядоченное дерево с уникальными метками листьев, имеющее три листа).


Теорема 5 ([1]). Задача MASP не может быть приближенно решена за полиномиальное время с константным множителем, если только не верно соотношение P = NP.


'''Теорема 5 ([1])'''. Задача MASP не может быть приближенно решена за полиномиальное время с константным множителем, если только не верно соотношение <math>\mathcal{P} = \mathcal{N} \mathcal{P}</math>.


Хотя задача MASP является NP-полной, существует алгоритм аппроксимации для ее приближенного решения.


Хотя задача MASP является NP-полной, существует аппроксимационный алгоритм для ее приближенного решения.


Теорема 6 ([8]). Задача MASP может быть приближенно решена с множителем lognn за время O(n2) ■ min {O(k ■ (log log n)2); O (k + log n • log log n)}. MASP, ограниченная корневыми триплетами, может быть приближенно решена с множителем lognn за время O(k + n2 log  n).


'''Теорема 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 различных меток листьев рассматривался множеством исследователей. Дженссон и коллеги [ ] первыми предложили алгоритм вычисления MAST на T с временем исполнения O(k(2n2)3k. Недавно Гийемо и Берри [5] улучшили это время до O((8n)k); Хоанг и Сунг [ ] снизили его до O((6n)), что показано в теореме 7.


Также существуют алгоритмы вычисления 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 различных меток листьев; их супердерево максимального соответствия может быть найдено за время O((6n)k).
Для случая, когда множество k бинарных деревьев T имеют степень D и n различных меток листьев, Хоанг и Сунг [7] предложили следующее решение для нахождения MASP с фиксированными параметрами и полиномиальным временем исполнения.


'''Теорема 7 ([7])'''. Пусть дано множество k бинарных деревьев T с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время <math>O((6n)^k) \;</math>.


Теорема 8 ([ ]). Пусть дано множество k бинарных деревьев T степени D с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время O((kD)kD+3(2n)k).
Для случая, когда множество k бинарных деревьев T имеют степень D и n различных меток листьев, Хоанг и Сунг [7] предложили следующее решение для нахождения MASP с фиксированными параметрами и полиномиальным временем выполнения.


'''Теорема 8 ([7])'''. Пусть дано множество k бинарных деревьев T степени D с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время <math>O((kD)^{kD+3} (2n)^k) \;</math>.


== Применение ==
== Применение ==
Строка 69: Строка 71:




Задача 2. Пусть D = f T1 ; T2; : ; Tk g – множество корневых неупорядоченных деревьев, в котором каждое дерево Ti имеет уникальные метки листьев, при этом множества меток листьев A(Tj) могут перекрываться. Задача нахождения супердерева максимальной совместимости (MCSP) заключается в построении дерева Q с уникальными метками листьев, с множеством меток листьев A(Q) С ST2D A(Tj), таким, что \A(Q)\ максимально и для каждого Ti 2 D топологическое ограничение поддерева Q0 дерева Q согласно A(Tj) уточняет топологическое ограничение Ti0 согласно Ti; иначе говоря, Ti0 может быть получено путем коллапсирования определенных ребер Qi0.
'''Задача 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:


== См. также ==
== См. также ==
► Поддерево максимального соответствия (для двух бинарных деревьев)
► Поддерево максимального соответствия (для трех или более деревьев)
► Дерево максимальной совместимости


* ''[[Поддерево максимального соответствия|Поддерево максимального соответствия (для двух бинарных деревьев)]]
* ''[[Поддерево максимального соответствия (для трех или более деревьев)]]
* ''[[Дерево максимальной совместимости]]


== Литература ==
== Литература ==
Irina
4501

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10995...15217

Навигация