java - 旅行推销员 - 2-Opt 改进

Question

所以我一直在寻找对旅行商问题的 2-opt 改进的解释，我明白了它的要点，但我不明白一件事。

我知道如果生成的路径的两条边相互交叉，我可以只切换两个点，它们将不再交叉。但是 - 我不明白如何确定两条边是否交叉。

为了明确我的问题，这是我到目前为止所做的:(我是用 java 做的)

1. 我有一个名为 Point 的对象，它代表一个城市，具有 x 和 y 坐标。
2. 我有一个 PointSet，它有一组包含在 List 中的 Points。
3. 我有一个名为 computeByNN() 的 PointSet 方法，它通过最近邻算法以相当短的方式排列 PointSet。

所以现在我有一个排序的 PointSet(不是最优的，但仍然很短)并且我想对其进行 2-opt。但是，我不知道从哪里开始。我是否应该检查每条线段以查看它们是否交叉，如果交叉，则切换两个点？我觉得这违背了启发式的目的，它变成了一种蛮力解决方案。有没有一种有效的方法来确定旅游的两个部分是否交叉？

如果我的问题不清楚，我表示歉意。如果有人需要我，我会尝试对其进行编辑以使其更清楚。

Answer 1

如果您愿意，可以创建一个查找表来检测交叉边。对于 n = 1000，订购 10^12 个条目显然过于奢侈。然而，您可能最担心较短的边缘？假设您的目标是为每个节点包括约 √n 个最近邻居的边。那么你只在兆字节的空间领域，在任何情况下都是 O(n^2) 预处理。从那里开始，这是一种启发式方法，祝你好运!

还会提到这可以即时完成。