4551
правка
Обмен ближайшими соседями и относительные расстояния: различия между версиями
Перейти к навигации
Перейти к поиску
м
Обмен ближайшими соседями и относительные расстояния (посмотреть исходный код)
Версия от 19:54, 26 декабря 2015
, 26 декабря 2015→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 84: | Строка 84: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
1. Существует ли алгоритм аппроксимации с константным коэффициентом для вычисления расстояния обмена ближайшими соседями на невзвешенных эволюционных деревьях, или O(log n)-аппроксимация – лучшая из всех? | 1. Существует ли алгоритм аппроксимации с константным коэффициентом для вычисления расстояния обмена ближайшими соседями на невзвешенных эволюционных деревьях, или O(log n)-аппроксимация – лучшая из всех? | ||
2. Является ли вычисление расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях NP-полной задачей, если неуникальные метки листьев не допускаются? | 2. Является ли вычисление расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях NP-полной задачей, если неуникальные метки листьев не допускаются? | ||
3. Можно ли улучшить коэффициент аппроксимации для вычисления расстояния переноса поддерева с линейной стоимостью на взвешенных эволюционных деревьях? | 3. Можно ли улучшить коэффициент аппроксимации для вычисления расстояния переноса поддерева с линейной стоимостью на взвешенных эволюционных деревьях? | ||
== См. также == | == См. также == | ||