algorithm - 给定一组二维坐标系中的点，如果我们只访问所有点一次，如何计算最小距离和路径？

Question

限制条件如下:

1. 设置固定阈值，使距离大于阈值由距离本身计算 distance小于等于distance视为常数值；

2. 最好让路径随x坐标增加(即p1.x <= p2.x <= ... <= pn.x)， 但是先考虑condition.1，然后是condition.2；

3. 我们只能访问每个点一次。

Answer 1

优化注意事项:因此，基本上是具有 2 个转弯的最短哈密顿路径(条件 1 和 2)。考虑到最短的 HP 可以用旅行推销员算法解决(虚拟城市与所有其他城市的距离为零)，为了获得更好的优化解决方案，您可以尝试根据条件 1 处理距离矩阵，然后再将其提供给 TSP 算法。 更多关于如何为这个最短的 HP 使用 TSP here .

蛮力方法

为了便于阅读，我将把您的观点称为 [A、B、...C]。让我们像这样表示我们的观点:

+---+---+---+
|   | X | Y |
+---+---+---+
| A | 0 | 0 |
| B | 4 | 3 |
| C | 0 | 3 |
+---+---+---+

然后用毕达哥拉斯定理创建一个距离矩阵:

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| A | 0.00 | 5.00 | 3.00 |
| B | 5.00 | 0.00 | 4.00 |
| C | 3.00 | 4.00 | 0.00 |
+---+------+------+------+

我对您的第一个条件(固定阈值)的理解是，任何低于某个值的距离都被视为零。将该条件应用于距离矩阵(假设在我们的例子中为 3.50)。

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| A | 0.00 | 5.00 | 0.00 |
| B | 5.00 | 0.00 | 4.00 |
| C | 0.00 | 4.00 | 0.00 |
+---+------+------+------+

现在，如果我们坚持我们的蛮力方法，我们必须资助所有可能的路线排列。在我们的例子中，这将是简单的

+------+-----------+--------------+
| Path | Distances | Total Length |
+------+-----------+--------------+
| ABC  | 5+4       |            9 |
| ACB  | 0+4       |            4 |
| BAC  | 5+0       |            5 |
| BCA  | 4+0       |            4 |
| CAB  | 0+5       |            5 |
| CBA  | 4+5       |            9 |
+------+-----------+--------------+

删除相同但相反的路线。

+------+-----------+--------------+
| Path | Distances | Total Length |
+------+-----------+--------------+
| ABC  | 5+4       |            9 |
| ACB  | 0+4       |            4 |
| BAC  | 5+0       |            5 |
+------+-----------+--------------+

按总长度取最短的，这就是您的解决方案。

第二个条件 - X 上的距离优于 Y 上的距离

据我所知，这种情况只有在总长度相等时才会激活。在这种情况下，使用点的 X 坐标差的绝对值创建距离矩阵:

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| A | 0.00 | 4.00 | 0.00 |
| B | 4.00 | 0.00 | 4.00 |
| C | 0.00 | 4.00 | 0.00 |
+---+------+------+------+

根据您绑定(bind)的路线总结距离，并使用它的最小值来决定应该首选哪一条。