Участник:Kirillskor/Задача nearest-neighbour-tsp-infty-bas-cases — различия между версиями
Материал из DISCOPAL
Строка 6: | Строка 6: | ||
Стрелочками обозначен выбор пути на основе ближайшего соседа. | Стрелочками обозначен выбор пути на основе ближайшего соседа. | ||
− | Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - | + | Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - не длиннее последовательного перемещения из самой левой в самую правую точки. Обозначим длину этого пути opt_i |
Для длинных стрелок расстояние определим как opt_i / 2 + 1. | Для длинных стрелок расстояние определим как opt_i / 2 + 1. |
Версия 14:02, 11 декабря 2017
Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-tsp-infty-bas-cases