4817
правок
Обмен ближайшими соседями и относительные расстояния: различия между версиями
Материал из WEGA
Обмен ближайшими соседями и относительные расстояния (посмотреть исходный код)
Версия от 12:50, 26 декабря 2015
, 26 декабря 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 54: | Строка 54: | ||
== Основные результаты == | == Основные результаты == | ||
Пусть | Пусть <math>T_1 \;</math> и T2 – два дерева, каждое из которых содержит n вершин, используемых при вычислении расстояния. | ||
Теорема 1 ([2, 3, 4]). Предположим, что деревья | Теорема 1 ([2, 3, 4]). Предположим, что деревья <math>T_1 \;</math> и <math>T_2 \;</math> невзвешенные. Тогда верны следующие утверждения: | ||
• <math>D_{nni}(T_1, T_2) = D_{lcst}(T_1, T_2) \;</math>. | |||
• Вычисление <math>D_{nni} (T_1, T_2) \;</math> представляет собой NP-полную задачу. | |||
• Предположим, что <math>D_{nni}(T_1, T_2) < d \;</math>. Тогда оптимальная последовательность операций обмена ближайшими соседями, преобразующая <math>T_1 \;</math> в <math>T_2 \;</math>, может быть вычислена за время <math>O(n^2 log \; n + n \cdot 2^{23d/2})</math>. | |||
• Значение <math>D_{nni}(T_1, T_2) \;</math> может быть приближенно вычислено с коэффициентом аппроксимации <math>log \; n + O(1)</math> за полиномиальное время. | |||
Теорема 2 ([1, 2, 3, 4]). Предположим, что деревья <math>T_1 \;</math> и <math>T_2 \;</math> взвешенные. Тогда верны следующие утверждения: | |||
• Значение Dnni(T1; T2) может быть приближенно вычислено с коэффициентом аппроксимации 6 + 6 log n за время O(n2 log n). | • Значение Dnni(T1; T2) может быть приближенно вычислено с коэффициентом аппроксимации 6 + 6 log n за время O(n2 log n). | ||
• Предположим, что | |||
• Предположим, что <math>T_1 \;</math> и <math>T_2 \;</math> могут иметь листья с неуникальными метками. Тогда вычисление Dlcst(T1;T2) представляет собой NP-полную задачу. | |||
• Значение Dlcst (T1; T2) может быть приближенно вычислено с коэффициентом аппроксимации 2 за время O(n2logn). | • Значение Dlcst (T1; T2) может быть приближенно вычислено с коэффициентом аппроксимации 2 за время O(n2logn). | ||
== Применение == | == Применение == | ||
