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