Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-tsp-infty-bas-cases — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- cabook-ex-02-04-p98 --> Начальная ситуация как в Приближенный алгоритм для метрической задачи…») |
StasFomin (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
Подсказка: для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального. | Подсказка: для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального. | ||
| − | [[Категория: | + | [[Категория:Решенные задачи]] |
Версия 12:25, 17 декабря 2017
Начальная ситуация как в Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-not-good-for-tsp.
Покажите, что для любой константы C, таких плохих входных данных (для разных n), бесконечное количество.
Подсказка: для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального.