Участник:Kirillskor/Задача nearest-neighbour-tsp-infty-bas-cases — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
<latex>
 
<latex>
 
Определим семейство графов G_i как показано на рисунке.
 
Определим семейство графов G_i как показано на рисунке.
 +
 +
Стрелочками обозначен выбор пути на основе ближайшего соседа.
  
 
Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - последовательное перемещение из самой левой в самую правую точки. Обозначим длину этого пути opt_i
 
Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - последовательное перемещение из самой левой в самую правую точки. Обозначим длину этого пути opt_i
Строка 8: Строка 10:
 
Для длинных стрелок расстояние определим как opt_i / 2 + 1.
 
Для длинных стрелок расстояние определим как opt_i / 2 + 1.
  
Длина оптимального пути для $G_{i+1}$ будет не больше $2 ^ {i + 1} (каждый раз мы увеличиваем в 2 раза + 2 + 2*eps)$
+
Длина оптимального пути для $G_{i+1}$ будет не больше $2 ^ {i + 1}$ (каждый раз мы увеличиваем в 2 раза + 2 + 2*eps, начинаем с 2)$
 +
 
 +
Посчитаем длину пути полученную алгоритмом ближайшего соседа.
 
<\latex>
 
<\latex>

Версия 13:52, 11 декабря 2017

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