Участник:Kirillskor/Задача nearest-neighbour-tsp-infty-bas-cases — различия между версиями
Материал из DISCOPAL
Строка 4: | Строка 4: | ||
Определим семейство графов G_i как показано на рисунке. | Определим семейство графов G_i как показано на рисунке. | ||
− | Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - последовательное перемещение из самой левой в самую правую точки. Обозначим длину этого пути | + | Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - последовательное перемещение из самой левой в самую правую точки. Обозначим длину этого пути opt_i |
− | Для длинных стрелок расстояние определим как половину расстояния от левого конца G_i до правого + 1 | + | Для длинных стрелок расстояние определим как половину расстояния от левого конца G_i до правого + 1 (то есть opt_i / 2 + 1) |
<\latex> | <\latex> |
Версия 13:44, 11 декабря 2017
Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-tsp-infty-bas-cases