4551
правка
Дерево максимальной совместимости: различия между версиями
Материал из WEGA
Дерево максимальной совместимости (посмотреть исходный код)
Версия от 15:59, 5 декабря 2015
, 5 декабря 2015→Основные результаты
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
Точные алгоритмы | Точные алгоритмы | ||
Было показано, что задача MCT является NP-полной для 6 деревьев ([9]) и для 2 деревьев [10]. NP-полнота появляется, когда по меньшей мере одно из входных деревьев имеет неограниченную степень. Для случая двух деревьев с ограниченной степенью Хайн и коллеги упоминают алгоритм с полиномиальным временем исполнения, основанный на выравнивании деревьев [10]. Ганапати и Уорноу [5] предложили экспоненциальный алгоритм для решения задачи MCT в общем виде. Они показали, как для двух деревьев | Было показано, что задача MCT является NP-полной для 6 деревьев ([9]) и для 2 деревьев [10]. NP-полнота появляется, когда по меньшей мере одно из входных деревьев имеет неограниченную степень. Для случая двух деревьев с ограниченной степенью Хайн и коллеги упоминают алгоритм с полиномиальным временем исполнения, основанный на выравнивании деревьев [10]. Ганапати и Уорноу [5] предложили экспоненциальный алгоритм для решения задачи MCT в общем виде. Они показали, как для двух деревьев <math>T_1, T_2 \;</math> вычислить бинарное дерево MCT для любой пары поддеревьев <math>(S_1 \in T_1, S_2 \in T_2) \;</math> при помощи динамических алгоритмов. Поддеревья, корни которых имеют высокую степень, обрабатываются путем рассмотрения каждого возможного разбиения потомков корня на два множества. Из-за этого в оценке сложности появляется экспоненциальный терм относительно d – максимальной степени вершин входных деревьев. Если имеются k входных деревьев, то рассматриваются кортежи из k поддеревьев и производится подобное же разбиение потомков корневых вершин на два множества для k поддеревьев. Следовательно, сложность по-прежнему является экспоненциальной относительно k. | ||
'''Теорема 1 ([5]). Пусть L – множество, содержащее n листьев. Задача MCT для набора из k корневых деревьев с листьями из L, в котором каждое дерево имеет степень не выше d + 1, может быть решена за время <math>O(2^{2kd} n^k) \;</math>.''' | |||
Результат можно легко расширить на некорневые деревья, если рассматривать каждый из n листьев как возможный корень для всех деревьев набора. | Результат можно легко расширить на некорневые деревья, если рассматривать каждый из n листьев как возможный корень для всех деревьев набора. | ||
Теорема 2 ([5]). Пусть дан набор из k некорневых деревьев, степени которых не превышают d + 1, с множеством листьев мощности n. Тогда задача MCT может быть решена за время O( | '''Теорема 2 ([5]). Пусть дан набор из k некорневых деревьев, степени которых не превышают d + 1, с множеством листьев мощности n. Тогда задача MCT может быть решена за время <math>O(2^{2kd} n^{k+1}) \;</math>.''' | ||
Пусть T – набор деревьев с листьями из множества L. В работе [2] рассматривалась следующая задача, названная | Пусть <math>\mathcal{T} \;</math> – набор деревьев с листьями из множества L. В работе [2] рассматривалась следующая задача, названная <math>MCT_p \;</math>: пусть даны <math>\mathcal{T} \;</math> и <math>p \in [0, n] \;</math>; верно ли, что <math>|MCT(\mathcal{T})j| \ge n - p \;</math>? | ||
Теорема 3 ([2] | '''Теорема 3 ([2]). | ||
Терм | 1. Задача <math>MCT_p \;</math> для корневых деревьев может быть решена за время <math>O(min \{ 3^p kn, 2.27^p + kn^3 \}) \;</math>. | ||
2. Задача <math>MCT|p \;</math> для некорневых деревьев может быть решена за время <math>O \big( (p + 1) \times min \{ 3^p kn, 2.27^p + kn^3 \} \big) \;</math>.''' | |||
Терм <math>3^p kn \;</math> возникает из-за использования алгоритма, который вначале за время O(kn) локализует множество S из трех листьев, на котором входные деревья конфликтуют, а затем рекурсивным образом вычисляет деревья максимальной совместимости T1, T2 и T3 для каждого из трех наборов T1, T2 и T3, соответственно, полученных посредством удаления принадлежащего S листа из входных деревьев, и затем возвращает Ti, такое, что \T\ максимально (для i 2 [1; 3]). Терм 2:27p + kn3 появляется из-за использования алгоритма, выполняющего редукцию MCT до 3-HITTING SET. Гийемо и Николя получили отрицательный результат при рассмотрении возможности разрешимости MCT с фиксированными параметрами для входных деревьев степени не выше D. | |||
| Строка 75: | Строка 81: | ||
Теорема 6 ([1]). Существует алгоритм 3-аппроксимации с временем исполнения O(kn + n2) для решения задачи CMCT на наборе k корневых деревьев с n листьев. | Теорема 6 ([1]). Существует алгоритм 3-аппроксимации с временем исполнения O(kn + n2) для решения задачи CMCT на наборе k корневых деревьев с n листьев. | ||
Отметим, что достижимый порог аппроксимации для CMCT не меняется в зависимости от того, рассматриваются ли корневые или некорневые деревья [1]. | Отметим, что достижимый порог аппроксимации для CMCT не меняется в зависимости от того, рассматриваются ли корневые или некорневые деревья [1]. | ||
== Применение == | == Применение == | ||
