4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 11: | Строка 11: | ||
== Основные результаты == | == Основные результаты == | ||
Финден и Гордон [8] предложили эвристический алгоритм для решения задачи MAST на бинарных деревьях с временем | Финден и Гордон [8] предложили эвристический алгоритм для решения задачи MAST на бинарных деревьях с временем выполнения <math>O(n^5) \;</math>, не гарантирующий оптимального решения. Кубицка, Кубицкий и Макморрис [13] предложили алгоритм с временем <math>O(n^{(0,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 на бинарных деревьях, где <math>c \;</math> – константа величиной больше 1. Для деревьев с произвольной степенью этот алгоритм требует <math>O(n^2 c^{\sqrt{log \; n}}) \;</math> времени для некорневого случая [6] и <math>O(n^{1,5 \; log \; n})</math> – для корневого [7]. Фарак, Пжытычка и Торуп получили алгоритм с временем выполнения <math>O(n \; log^3 n) \;</math> для решения задачи MAST на бинарных деревьях. Као [12] удалось получить алгоритм для этой же задачи с временем выполнения <math>O(n \; log^2 \; n) \;</math>. Для деревьев степени d он выполняется за время <math>O(min \{ n d^2 \; log \; d \; log^2 n, n d^{3/2} \; log^3 n \} )</math>. | ||
Также была исследована задача MAST для более чем двух деревьев. Амир и Кеселман [1 ] показали, что проблема является NP-полной даже для трех деревьев с неограниченной степенью. Однако для трех или более деревьев с ограниченной степенью известны полиномиальные алгоритмы [1, 5]. | Также была исследована задача MAST для более чем двух деревьев. Амир и Кеселман [1 ] показали, что проблема является NP-полной даже для трех деревьев с неограниченной степенью. Однако для трех или более деревьев с ограниченной степенью известны полиномиальные алгоритмы [1, 5]. | ||
Далее представлен алгоритм Коула и Харихарана для решения задачи MAST на двух бинарных деревьях. Он был получен в результате модернизации алгоритма с временем <math>O(n \; log^3 n) \;</math> [4] (финальная журнальная версия [3] представляет собой сочетание обеих работ). Алгоритм с временем | Далее представлен алгоритм Коула и Харихарана для решения задачи MAST на двух бинарных деревьях. Он был получен в результате модернизации алгоритма с временем <math>O(n \; log^3 n) \;</math> [4] (финальная журнальная версия [3] представляет собой сочетание обеих работ). Алгоритм с временем выполнения <math>O(n \; log^3 n) \;</math> из [4] использует следующий подход (хотя авторы и не излагали его в таком виде). Он определяет два специальных случая и затем решает задачу для общего случая путем интерполяции этих специальных случаев. | ||
Строка 28: | Строка 28: | ||
В данной работе были предложены две оптимизации, каждая из которых приводит к сокращению времени | В данной работе были предложены две оптимизации, каждая из которых приводит к сокращению времени выполнения на коэффициент log n. | ||
Оптимизация 1: время | Оптимизация 1: время выполнения алгоритма для специального случая полных деревьев улучшается до <math>O(n \; log \; n)</math> следующим образом. Пара вершин (u, v), <math>u \in T_1 \;</math>, <math>v \in T_2 \;</math>, считается интересной, если существует поддерево соответствия, отображающее u на v. Как показано ниже, для полных деревьев общее число интересных пар (u, v) составляет всего <math>O(n \; log \; n)</math>. Рассмотрим вершину v в дереве <math>T_2 \;</math>. Пусть <math>L_2 \;</math> – множество листьев, являющихся потомками v. Пусть <math>L_1 \;</math> – множество тех листьев <math>T_1 \;</math>, которые имеют те же метки, что и листья в <math>L_2 \;</math>. Отображены на v могут быть только вершины u, принадлежащие к поддереву <math>T_1 \;</math>, порожденному <math>L_1 \;</math>. Количество таких вершин составляет O(размер поддерева <math>T_2</math> с корнем в v). Таким образом, общее число интересных пар представляет собой сумму всех поддеревьев <math>T_2 \;</math>, или <math>O(n \; log \; n)</math>. | ||
Строка 42: | Строка 42: | ||
Случай с более высокой степенью | Случай с более высокой степенью | ||
Эту технику можно обобщить на случаи более высоких степеней d > 2, за счет сочетания ее с техниками из ([6, глава 2]) для неограниченных степеней. Полученный алгоритм теоретически должен выполняться за время <math>O(min \{ n \sqrt{d} \; log^2 \; n, nd \; log n \; log \; d \} )</math>; однако на деле время его | Эту технику можно обобщить на случаи более высоких степеней d > 2, за счет сочетания ее с техниками из ([6, глава 2]) для неограниченных степеней. Полученный алгоритм теоретически должен выполняться за время <math>O(min \{ n \sqrt{d} \; log^2 \; n, nd \; log n \; log \; d \} )</math>; однако на деле время его выполнения составляет <math>O(n \sqrt{d} \; log \; n)</math>. | ||
== Применение == | == Применение == |
правок