4551
правка
Супердерево максимального соответствия: различия между версиями
Перейти к навигации
Перейти к поиску
м
Супердерево максимального соответствия (посмотреть исходный код)
Версия от 00:36, 2 ноября 2015
, 2 ноября 2015→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 71: | Строка 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>. | ||
== Открытые вопросы == | == Открытые вопросы == | ||