Допустим, я знаю глобальное оптимальное решение стандартной задачи коммивояжёра для 100 городов. Теперь предположим, что продавец хочет пропустить 5 городов. Нужно ли переделывать TSP? Будет ли последовательность городов, полученная простым удалением этих городов из предыдущего оптимального решения, глобальным оптимумом для нового TSP из 95 городов?
Остается ли оптимальное решение TSP оптимальным даже после пропуска нескольких городов?
Ответы (1)
Обновлено: контрпример заменен евклидовым экземпляром.
Отличный вопрос.
Нет, если вы удалите некоторые города, исходная последовательность городов не останется оптимальной. Вот контрпример:
Координаты узла:
0 0
4 0
4 2
2.6 3
10 3
4 4
4 6
0 6
Вот оптимальный тур:
Теперь предположим, что нам не нужно посещать узел 5. Если мы просто «закроем» исходный тур, стоимость полученного тура составит 21,94:
Но оптимальный тур имеет стоимость 21,44:
(Если вы хотите удалить 5 городов вместо 1, просто поместите все 5 городов близко друг к другу справа.)
person
LarrySnyder610
schedule
08.11.2016
Под стандартным TSP я имел в виду TSP, в котором функции стоимости представляют собой сумму евклидовых расстояний между городами. В вашем примере используется вариант TSP с указанными затратами.
- person Prometheus; 08.11.2016
@Prometheus Отвечает ли мое исправленное решение вашему комментарию? Если это так, рассмотрите возможность принятия моего решения.
- person LarrySnyder610; 16.11.2016
