Разница между ATSP и TSP

Question

Это может быть немного глупый вопрос, но какова точная разница в решении TSP и ATSP.

Я всегда думал, что в ATSP вам нужно вычислить обратный путь (поскольку входная матрица асимметрична).

Таким образом, путь для ATSP вдвое длиннее, чем TSP. Я прав?

Я понимаю, что это очень простой вопрос, но у меня возникли сомнения. Спасибо.

Answer 1

ATSP - это TSP с асимметричными расстояниями.

Учитывая TSP с местоположениями A, B, C, D, E, для которых расстояние от A до B равно 100, тогда расстояние для B до A также будет равно 100. Для ATSP это не так: расстояние от B до A может составлять 120.

Настоящий TSP, использующий легковой или грузовой автомобиль, всегда является ATSP, потому что вождение на неправильной стороне дороги незаконно. Рассмотрение ATSP как TSP и оптимальное решение TSP не приведут к оптимальному решению для этого ATSP.