4551
правка
Обмен ближайшими соседями и относительные расстояния: различия между версиями
Перейти к навигации
Перейти к поиску
м
Обмен ближайшими соседями и относительные расстояния (посмотреть исходный код)
Версия от 22:50, 26 декабря 2015
, 26 декабря 2015→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
• найдено соответствие между расстоянием обмена ближайшими соседями и расстоянием переноса поддеревьев с линейной стоимостью на невзвешенных деревьях; | • найдено соответствие между расстоянием обмена ближайшими соседями и расстоянием переноса поддеревьев с линейной стоимостью на невзвешенных деревьях; | ||
• вычисление расстояния обмена ближайшими соседями является NP-полной задачей, однако допускает возможность разрешимости с фиксированными параметрами и применение алгоритмов аппроксимации с | • вычисление расстояния обмена ближайшими соседями является NP-полной задачей, однако допускает возможность разрешимости с фиксированными параметрами и применение алгоритмов аппроксимации с логарифмическими коэффициентами; | ||
• разработан алгоритм 2-аппроксимации для вычисления расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях. | • разработан алгоритм 2-аппроксимации для вычисления расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях. | ||