Просмотр исходного текста страницы Участник:Kirillskor/Задача nearest-neighbour-tsp-infty-bas-cases

[[Файл:tsp_bad_nn.png]][[Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-tsp-infty-bas-cases]]

<latex>
Определим семейство графов G_i как показано на рисунке.

Стрелочками обозначен выбор пути на основе ближайшего соседа.

Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - последовательное перемещение из самой левой в самую правую точки. Обозначим длину этого пути opt_i

Для длинных стрелок расстояние определим как opt_i / 2 + 1.

Длина оптимального пути для $G_{i+1}$ будет не больше $2 ^ {i + 1}$ (каждый раз мы увеличиваем в 2 раза + 2 + 2*eps, начинаем с 2)$

Посчитаем длину пути полученную алгоритмом ближайшего соседа.
<\latex>