Я беру класс Алгоритмы: проектирование и анализ II , один из вопросов:
Какое из следующих утверждений верно?
- Рассмотрим экземпляр TSP, в котором стоимость каждого ребра равна либо 1, либо 2. Тогда оптимальное путешествие может быть вычислено за полиномиальное время.
- Рассмотрим экземпляр TSP, в котором стоимость каждого ребра отрицательна. Алгоритм динамического программирования, описанный в видео-лекциях, может не
правильно рассчитать оптимальный (т.е. минимальную сумму длин ребер) тур
этого экземпляра.
- Рассмотрим экземпляр TSP, в котором стоимость каждого ребра отрицательна. Удаление вершины и всех ее инцидентных ребер не может увеличить
стоимость оптимального (т. е. минимальная сумма длин ребер) тура.
- Рассмотрим экземпляр TSP, в котором стоимость каждого ребра представляет собой евклидово расстояние между двумя точками в месте (как в программировании).
Задание № 5). Удаление вершины и всех ее инцидентных ребер не может
увеличить стоимость оптимального (т. е. минимальной суммы длин ребер)
тур.
Я утверждаю следующее:
Алгоритм DP не делает никаких предположений о граничных затратах, поэтому вариант 2 неверен.
Если все веса ребер отрицательны, то удаление вершины и всех ее падающих ребер, безусловно, может увеличить минимальную сумму, поскольку в действительности этот вес ребра теперь добавляется к предыдущему минимуму. Таким образом, вариант 3 неверен.
Возьмите оптимальный тур в оригинальном экземпляре. Теперь вместо посещения удаленной вершины v перейдите прямо от предшественника v к его преемнику в туре. Поскольку евклидово расстояние удовлетворяет «неравенству треугольника», этот ярлык только уменьшает общее пройденное расстояние. Конечно, лучший тур может быть только лучше. Таким образом, вариант 4 является правильным.
Однако я не могу найти никакого значения для проблем TSP с затратами на единицу продукции. Вариант 1 - просто уловка, или есть что-то еще?