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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
Стрелочками обозначен выбор пути на основе ближайшего соседа.
 
Стрелочками обозначен выбор пути на основе ближайшего соседа.
  
Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - последовательное перемещение из самой левой в самую правую точки. Обозначим длину этого пути opt_i
+
Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - не длиннее последовательного перемещения из самой левой в самую правую точки. Обозначим длину этого пути opt_i
  
 
Для длинных стрелок расстояние определим как opt_i / 2 + 1.
 
Для длинных стрелок расстояние определим как opt_i / 2 + 1.

Версия 14:02, 11 декабря 2017

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