4501
правка
Поддерево максимального соответствия (для трех или более деревьев): различия между версиями
Перейти к навигации
Перейти к поиску
Поддерево максимального соответствия (для трех или более деревьев) (посмотреть исходный код)
Версия от 16:01, 24 сентября 2015
, 24 сентября 2015→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача нахождения поддерева максимального соответствия для k деревьев (k-MAST) представляет собой обобщение [[Поддерево_максимального_соответствия|подобной же задачи для двух деревьев]] (Maximum Agreement Subtree, MAST). Рассмотрим кортеж из k корневых деревьев с помеченными листьями ( | Задача нахождения поддерева максимального соответствия для k деревьев (k-MAST) представляет собой обобщение [[Поддерево_максимального_соответствия|подобной же задачи для двух деревьев]] (Maximum Agreement Subtree, MAST). Рассмотрим кортеж из k корневых деревьев с помеченными листьями <math>(T_1, T_2, ..., T_k) \;</math>. Пусть <math>A = \{ a_1, a_2, ..., a_n \} \;</math> – множество меток листьев. Любое подмножество <math>B \subseteq A \;</math> уникальным образом определяет так называемое топологическое ограничение T|B дерева T согласно B. А именно, T|B является топологическим поддеревом T, натянутым на все листья, помеченные элементами из B, и самых низких общих предков всех пар этих листьев. Отношение наследования в T|B определяется таким образом, чтобы оно было согласовано с отношением наследования в T. Подмножество B множества A, такое, что <math>T^1|B, ..., T^k|B \;</math> являются изоморфными, называется множеством соответствия. | ||
Задача 1 (k-MAST) | '''Задача 1 (k-MAST)''' | ||
Дано: Кортеж | Дано: Кортеж <math>\overrightarrow{T} = (T^1, ..., T^k) \;</math> деревьев с помеченными листьями, с общим набором меток <math>A = \{ a_1, ..., a_n \} \;</math>, таким, что для каждого дерева <math>T_i \;</math> существует взаимно однозначное отображение между множеством листьев этого дерева и множеством меток A. | ||
Требуется: найти k-MAST(T), равное множеству соответствия максимальной мощности дерева T. | Требуется: найти k-MAST(T), равное множеству соответствия максимальной мощности дерева T. | ||