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