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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 16 промежуточных версий 1 участника)
Строка 2: Строка 2:
  
 
<latex>
 
<latex>
Определим семейство графов G_i
+
Определим семейство графов G_i как показано на рисунке.
 +
 
 +
Стрелочками обозначен выбор пути на основе ближайшего соседа.
 +
 
 +
Пусть пути стартуют из самой левой точки, тогда кратчайший путь будет - не длиннее последовательного перемещения из самой левой в самую правую точки. Обозначим длину этого пути opt_i
 +
 
 +
Для длинных стрелок расстояние определим как opt_i / 2 + 1.
 +
 
 +
Длина оптимального пути для $G_{i+1}$ будет не больше $2 ^ {i + 2}$ (каждый раз мы увеличиваем в 2 раза + 2 + 2*eps, начинаем с 2)$
 +
 
 +
Посчитаем длину пути полученную алгоритмом ближайшего соседа.
 +
 
 +
$\sum\limits_{j=1}^{i} 2^{i-j}*opt_j \geq \sum\limits_{j=1}^{i} 2^i \geq i * 2 ^ i
 +
 
 +
Значит путь ближайшего соседа в i / 4 раз длиннее оптимального пути.
 +
 
 +
Значит для любой константы C существует i, такое что i / 4 > C, начиная с некоторого i, и таких i бесконечно много.
 +
 
 +
Значит это верно и для бесконечного числа n, что и требовалось доказать.
 
<\latex>
 
<\latex>
 +
 +
[[Категория:Решения]]

Текущая версия на 15:24, 17 декабря 2017

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