python - 优化路线上另外 2 个卫生间的位置 (python)

Question

This image显示了一 strip 有卫生间的人造步道(青色点)。我想再添加 2 个卫生间，使沿步道上任意位置到 3 个卫生间中最近的一个的最大距离最小化。

# Data

# trail is a list of segments between the magenta and/or cyan points (in the image).
# Each of the segments in turn is a list of endpoints.
trail = [[[0, 0], [1, 0]], [[2, 0], [3, 0]], [[3, 0], [4, 0]], [[4, 0], [5, 0]], [[6, 0], [7, 0]], [[5, 1], [6, 1]], [[1, 2], [2, 2]], [[4, 2], [5, 2]], [[1, -1], [2, -1]], [[3, -1], [4, -1]], [[5, -1], [6, -1]], [[4, -2], [5, -2]], [[1, 2], [1, 0]], [[1, 0], [1, -1]], [[2, 2], [2, 0]], [[2, 0], [2, -1]], [[3, 2], [3, 0]], [[4, 2], [4, 0]], [[4, 0], [4, -1]], [[4, -1], [4, -2]], [[5, 2], [5, 1]], [[5, 1], [5, 0]], [[5, 0], [5, -1]], [[5, -1], [5, -2]], [[6, 1], [6, 0]], [[6, 0], [6, -1]], [[3, -1], [4, 0]]]

restroom = [0, 0]

这是 this question 的简化版本.

提示也将不胜感激。谢谢。

Answer 1

我认为这个可以通过放松的方法来有效解决。

1. 拿出你的图表并随机放置两个新的移动厕所。
2. 使用 Dijkstra 算法查找图中距离厕所最远的节点。
3. 将最近的移动厕所移向该点，再次使用 Dijkstra 找到移动的最短路径。厕所只能移动到目的地总距离的一小部分。
4. 重复步骤 2 和 3，直到系统稳定并且移动厕所停止移动。

通过添加更多退化节点以使节点之间的最大距离低于某个阈值，可以提高解决方案的保真度。

如果某些图表存在一些局部最小值问题，这意味着您不会总是从不同的随机起始位置获得相同的解决方案，我一点也不会感到惊讶，但这种技术至少会完善对一个解决方案。