4817
правок
Поддерево максимального соответствия: различия между версиями
Материал из WEGA
Поддерево максимального соответствия (посмотреть исходный код)
Версия от 09:59, 22 сентября 2015
, 22 сентября 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
Финден и Гордон [8] предложили эвристический алгоритм для решения задачи MAST на бинарных деревьях с временем исполнения <math>O(n^5) \;</math>, не гарантирующий оптимального решения. Кубицка, Кубицкий и Макморрис [13] предложили алгоритм с временем <math>O(n^{(.5 + \epsilon) log \; n)}</math> для той же задачи. Первый алгоритм решения этой задачи за полиномиальное время разработали Стил и Уорноу [15]; время его исполнения составляло <math>O(n^2) \;</math>. Стил и Уорноу также рассматривали случай небинарных и некорневых деревьев. Этот алгоритм требует <math>O(n^2) \;</math> времени для корневых и некорневых деревьев с фиксированной степенью и <math>O(n^{4.5 \; log \; n} )</math> для корневых и некорневых деревьев произвольной степени. Кроме того, они предложили линейную редукцию от корневого дерева к некорневому. Фарак и Торуп предложили алгоритм с временем исполнения <math>O(nc^{\sqrt{log \; n}})</math> для решения задачи MAST на бинарных деревьях; здесь c – константа величиной больше 1. Для деревьев с произвольной степенью этот алгоритм требует <math>O(n^2 c^{\sqrt{log \; n}}) \;</math> времени для некорневого случая [6] и O(n^{1.5 \; log \; n}) – для корневого [7]. Фарак, Пжытычка и Торуп получили алгоритм с временем исполнения <math>O(n \; log^3 n) \;</math> для решения задачи MAST на бинарных деревьях. Као [12] удалось получить алгоритм для этой же задачи с временем исполнения <math>O(n \; log^2 \; n) \;</math>. Для деревьев степени n он выполняется за время <math>O(min \{ n d^2 \; log \; d \; log \; n, n d^{3/2} \; log^3 n \} )</math>. | Финден и Гордон [8] предложили эвристический алгоритм для решения задачи MAST на бинарных деревьях с временем исполнения <math>O(n^5) \;</math>, не гарантирующий оптимального решения. Кубицка, Кубицкий и Макморрис [13] предложили алгоритм с временем <math>O(n^{(.5 + \epsilon) log \; n)}</math> для той же задачи. Первый алгоритм решения этой задачи за полиномиальное время разработали Стил и Уорноу [15]; время его исполнения составляло <math>O(n^2) \;</math>. Стил и Уорноу также рассматривали случай небинарных и некорневых деревьев. Этот алгоритм требует <math>O(n^2) \;</math> времени для корневых и некорневых деревьев с фиксированной степенью и <math>O(n^{4.5 \; log \; n} )</math> для корневых и некорневых деревьев произвольной степени. Кроме того, они предложили линейную редукцию от корневого дерева к некорневому. Фарак и Торуп предложили алгоритм с временем исполнения <math>O(nc^{\sqrt{log \; n}})</math> для решения задачи MAST на бинарных деревьях; здесь c – константа величиной больше 1. Для деревьев с произвольной степенью этот алгоритм требует <math>O(n^2 c^{\sqrt{log \; n}}) \;</math> времени для некорневого случая [6] и O(n^{1.5 \; log \; n}) – для корневого [7]. Фарак, Пжытычка и Торуп получили алгоритм с временем исполнения <math>O(n \; log^3 n) \;</math> для решения задачи MAST на бинарных деревьях. Као [12] удалось получить алгоритм для этой же задачи с временем исполнения <math>O(n \; log^2 \; n) \;</math>. Для деревьев степени n он выполняется за время <math>O(min \{ n d^2 \; log \; d \; log \; n, n d^{3/2} \; log^3 n \} )</math>. | ||
Также была исследована задача MAST для более чем двух деревьев. Амир и Кеселман [1 ] показали, что проблема является NP-полной даже для трех деревьев с неограниченной степенью. Однако для трех или более деревьев с ограниченной степенью известны полиномиальные алгоритмы [1, 5]. | |||
Далее представлен алгоритм Коула и Харихарана для решения задачи MAST на двух бинарных деревьях. Он был получен в результате модернизации алгоритма с временем <math>O(n \; log^3 n) \;</math> [4] (финальная журнальная версия [3] представляет собой сочетание обеих работ). Алгоритм с временем исполнения <math>O(n \; log^3 n) \;</math> из [4] использует следующий подход (хотя авторы и не излагали его в таком виде). Он определяет два специальных случая и затем решает задачу для общего случая путем интерполяции этих специальных случаев. | |||
Специальный случай 1: внутренние вершины обоих деревьев формируют путь. Задача MAST в этом случае фактически сводится к задаче нахождения самой длинной возрастающей последовательности в графе размера n. Хорошо известно, что она может быть решена за время <math>O(n \; log \; n)</math>. | |||
Специальный случай 2: оба дерева, | |||
Специальный случай 2: оба дерева, <math>T_1 \;</math> и <math>T_2 \;</math>, являются полными бинарными деревьями. Для каждой вершины v дерева <math>T_2 \;</math> только определенные вершины u в <math>T_1 \;</math> могут быть отображены на v практичным образом, в том смысле, что поддерево <math>T_1 \;</math> с корнем в u и поддерево <math>T_2 \;</math> с корнем в v имеют непустое поддерево соответствия. Существует <math>O(n \; log^2 \; n)</math> таких пар (u, v), что можно показать следующим образом. Заметим, что для того, чтобы две вершины (u, v) составляли такую пару, поддерево <math>T_1 \;</math> с корнем в u и поддерево <math>T_2 \;</math> с корнем в v должны иметь общую метку листа. Для каждой метки существуют только <math>O(log^2 \; n) \;</math> таких пар, полученных сопряжением каждого потомка листа с этой меткой в дереве <math>T_1 \;</math> с каждым потомком листа с этой меткой в дереве <math>T_2 \;</math>. Таким образом, общее число интересных пар составляет <math>O(n \; log^2 \; n)</math>. Для каждой пары вычисление MAST требует O(1) времени, поскольку вопрос заключается просто в нахождении лучшего способа сопряжения их потомков. | |||
