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

Материал из DISCOPAL
< Приближенный алгоритм для метрической задачи коммивояжера‎ | Задачи
Версия от 20:48, 7 декабря 2017; StasFomin (обсуждение | вклад) (Новая страница: «<!-- cabook-ex-02-04-p98 --> Начальная ситуация как в Приближенный алгоритм для метрической задачи…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск


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

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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.

Источник — «https://discopal.ispras.ru/index.php?title=Приближенный_алгоритм_для_метрической_задачи_коммивояжера/Задачи/nearest-neighbour-tsp-infty-bas-cases&oldid=6461»