4446
правок
Поддерево максимального соответствия (для трех или более деревьев): различия между версиями
Перейти к навигации
Перейти к поиску
Поддерево максимального соответствия (для трех или более деревьев) (посмотреть исходный код)
Версия от 00:08, 25 сентября 2015
, 25 сентября 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
Наивное расширение алгоритма для двух деревьев на алгоритм для k деревьев потребует перевычисления k-MAST( | Наивное расширение алгоритма для двух деревьев на алгоритм для k деревьев потребует перевычисления <math>k-MAST(\overrightarrow{v}) \;</math> для всех возможных кортежей <math>\overrightarrow{v} \;</math> посредством обработки этих кортежей в порядке, согласующемся с отношением доминирования. Основная идея, позволяющая избежать возникновения сложности <math>\Omega (n^k) \;</math>, заключается в замене вычисления <math>k-MAST(\overrightarrow{v}) \;</math> вычислением связанного с ним значения, <math>mast(\overrightarrow{v}) \;</math>, представляющего собой размер максимального множества соответствия для поддеревьев <math>(T^1, ..., T^k) \;</math> с корнями в <math>(v_1, ..., v_k) \;</math>, при условии дополнительного ограничения, заключающегося в том, что сами поддеревья соответствия имеют корни в <math>v_1, ..., v_k \;</math>, соответственно. Очевидно, что <math>k-MAST(T^1, ..., T^k) = max_{\overrightarrow{v}} \; mast(\overrightarrow{v}) \;</math> . | ||
Преимущество вычисления mast вместо k-MAST следует из того факта, что большинство значений mast являются нулевыми и можно достаточно эффективно определить v с ненулевыми значениями mast. | Преимущество вычисления mast вместо k-MAST следует из того факта, что большинство значений mast являются нулевыми и можно достаточно эффективно определить <math>\overrightarrow{v} \;</math> с ненулевыми значениями mast. | ||
Примечание 1. Если mast(vE) > 0, то v = (lcaT1 (a;b);::: lcaT (a; b)) для некоторых меток листьев a, b, где lcaT (a; b) – самый низкий общий предок листьев с метками a и b в дереве V. | Примечание 1. Если mast(vE) > 0, то v = (lcaT1 (a;b);::: lcaT (a; b)) для некоторых меток листьев a, b, где lcaT (a; b) – самый низкий общий предок листьев с метками a и b в дереве V. | ||