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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- cabook-ex-02-04-p98 --> Начальная ситуация как в Приближенный алгоритм для метрической задачи…»)
 
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
 
(не показано 6 промежуточных версий этого же участника)
Строка 7: Строка 7:
 
Подсказка: для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального.
 
Подсказка: для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального.
  
[[Категория:For-group-V]]
+
[[Категория:Решенные задачи]]

Текущая версия на 15:49, 20 мая 2020


Начальная ситуация как в Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-not-good-for-tsp.

Покажите, что для любой константы C, таких плохих входных данных (для разных n), бесконечное количество.

Подсказка: для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального.