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

Question

显示了一条带有卫生间的人造小径（青色点）。我想再添加 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]

这是这个问题的简化版本。

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

Answer 1

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

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

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

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

Answer 2

沿步道随机放置两个新的移动厕所。 使用 Dijkstra 算法找到距离任何厕所最远的节点。 使用 Dijkstra 的最短路径算法逐渐将最近的厕所移向识别的节点。 重复步骤 2 和 3，直到系统稳定并且马桶停止移动。

Answer 3

如果您在步道周围拖动卫生间，并点亮步道上最远的点，并且还显示当前最大距离的一些模拟测量值以及迄今为止找到的最小最大距离，它可能会成为一个有趣的交互式图形游戏。路径的更连续的颜色，指示到最近的洗手间的距离可能会提供线索，帮助找到极小极大值。