Участник: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
