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的简化版本。
提示也将不胜感激。
谢谢。
最佳答案
我认为可以通过放松方法有效地解决这一问题。
绘制图表并随机放置两个新的移动厕所。
使用Dijkstra的算法在图中找到离厕所最远的节点。
将最近的移动厕所移至该点，再次使用Dijkstra查找最短的移动路径。马桶只能移动到目的地的总距离的一小部分。
重复步骤2和3，直到系统稳定并且移动厕所停止移动。
通过添加更多退化节点，使节点之间的最大距离低于某个阈值，可以提高解决方案的保真度。
如果某些图形存在局部极小问题，这意味着您将不会总是从不同的随机起始位置获得相同的解决方案，那我将不会感到惊讶，但是这种技术至少可以优化一个解决方案的初始猜测。