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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 2: Строка 2:
  
 
<latex>
 
<latex>
Определим семейство графов G_i
+
Определим семейство графов G_i как показано на рисунке.
 +
 
 +
Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - последовательное перемещение из самой левой в самую правую точки. Обозначим длину этого пути l_opt_i
 +
 
 +
Для длинных стрелок расстояние определим как половину расстояния от левого конца G_i до правого + 1.
 
<\latex>
 
<\latex>

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

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