Участник:Kirillskor/Задача nearest-neighbour-tsp-infty-bas-cases — различия между версиями
Материал из DISCOPAL
Строка 10: | Строка 10: | ||
Для длинных стрелок расстояние определим как opt_i / 2 + 1. | Для длинных стрелок расстояние определим как opt_i / 2 + 1. | ||
− | Длина оптимального пути для $G_{i+1}$ будет не больше $2 ^ {i + | + | Длина оптимального пути для $G_{i+1}$ будет не больше $2 ^ {i + 2}$ (каждый раз мы увеличиваем в 2 раза + 2 + 2*eps, начинаем с 2)$ |
Посчитаем длину пути полученную алгоритмом ближайшего соседа. | Посчитаем длину пути полученную алгоритмом ближайшего соседа. | ||
<\latex> | <\latex> |
Версия 14:08, 11 декабря 2017
Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-tsp-infty-bas-cases