4446
правок
Супердерево максимального соответствия: различия между версиями
Материал из WEGA
Супердерево максимального соответствия (посмотреть исходный код)
Версия от 14:31, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 44: | Строка 44: | ||
Хотя задача MASP является NP-полной, существует алгоритм | Хотя задача MASP является NP-полной, существует аппроксимационный алгоритм для ее приближенного решения. | ||
| Строка 50: | Строка 50: | ||
Также существуют алгоритмы вычисления MASP с фиксированными параметрами и полиномиальным временем решения. Случай с множеством k бинарных деревьев T с n различных меток листьев рассматривался множеством исследователей. Дженссон и коллеги [8] первыми предложили алгоритм вычисления MAST на T с временем | Также существуют алгоритмы вычисления 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>. | '''Теорема 7 ([7])'''. Пусть дано множество k бинарных деревьев T с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время <math>O((6n)^k) \;</math>. | ||
Для случая, когда множество k бинарных деревьев T имеют степень D и n различных меток листьев, Хоанг и Сунг [7] предложили следующее решение для нахождения MASP с фиксированными параметрами и полиномиальным временем | Для случая, когда множество k бинарных деревьев T имеют степень D и n различных меток листьев, Хоанг и Сунг [7] предложили следующее решение для нахождения MASP с фиксированными параметрами и полиномиальным временем выполнения. | ||
| Строка 80: | Строка 80: | ||
== См. также == | == См. также == | ||
* ''[[Поддерево максимального соответствия (для двух бинарных деревьев)]] | * ''[[Поддерево максимального соответствия|Поддерево максимального соответствия (для двух бинарных деревьев)]] | ||
* ''[[Поддерево максимального соответствия (для трех или более деревьев)]] | * ''[[Поддерево максимального соответствия (для трех или более деревьев)]] | ||
* ''[[Дерево максимальной совместимости]] | * ''[[Дерево максимальной совместимости]] | ||
