traveling-salesman - ATSP 和 TSP 的区别

Question

这可能是一个有点愚蠢的问题，但解决 TSP 和 ATSP 的确切区别是什么。

我一直认为在 ATSP 中你需要计算返回的路径（因为输入矩阵是不对称的）。

所以 ATSP 的路径是 TSP 的两倍。我对么？

我明白这是一个非常简单的问题，但我的脑海里已经有了疑问。谢谢你。

Answer 1

ATSP 是具有不对称距离的 TSP。

给定具有位置 A、B、C、D、E 的 TSP，其中 A 到 B 的距离为 100，那么 B 到 A 的距离也将为 100。对于 ATSP，这不成立：从 B 到 A 的距离可能是 120。

使用汽车或卡车的真正全球 TSP 始终是 ATSP，因为在道路错误的一侧驾驶是违法的。将 ATSP 视为 TSP 并以最佳方式解决该 TSP不会导致该 ATSP 的最佳解决方案。