1

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

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

为了让我的问题更清楚，这就是我到目前为止所做的：（我在 java 中做了）

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

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

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

4

1 回答 1

1

如果您愿意，可以创建一个查找表来检测交叉边缘。对于 n = 1000，订购 10^12 个条目显然过于奢侈。但是，您可能最担心较短的边缘？假设您的目标是为每个节点包含大约 √n 个最近邻居的边。那么你只处于兆字节空间的领域，并且无论如何都是 O(n^2) 预处理。从那里它是一个启发式，祝你好运！

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

于 2013-09-06T23:08:48.790 回答