在小径上优化2个额外卫生间的位置（python）

Question

This image显示了一条带洗手间的小径（蓝点）。我想再增加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，直到系统稳定，移动厕所停止移动。你知道吗

通过增加更多的退化节点，使得节点间的最大距离低于某个阈值，可以提高解的保真度。你知道吗

如果有些图存在局部极小值问题，意味着从不同的随机起始位置不一定总能得到相同的解，我一点也不感到惊讶，但这种技术至少可以改进对解的初始猜测。你知道吗

Answer 2

如果你在小径上拖拽洗手间，照亮小径上最远的点，同时显示当前最大距离的模拟测量值，以及迄今为止发现的最小最大距离，这可能是一个有趣的交互式图形游戏。一个更连续的颜色的痕迹，表明距离最近的洗手间可能会给线索，以帮助寻找极小值。你知道吗