通路/道路铺设问题

Question

今天我们完成了在实验室完成的任务(两小时内完成).问题是:

• 你得到一个m*n矩阵.
• 矩阵有'h'住宅大厅和'b'主建筑入口.
• 这些'h'大厅和'b'入口的位置是已知的(以(x,y)坐标表示).
• 您需要铺设通道,使每个住宅大厅至少有一种方式到达其中一个'b'入口.
• 最多可以存在'b'这样的断开路径.
• 通路的长度必须最小.
• 您只能向上,向下,向左或向右移动.
• 解决方案绝不能是强力企图.

任务结束了.但我仍然在想如何解决这个问题.这些问题是否有标准术语？我该怎么读？

人们也会使用这种算法在城市铺设道路吗？

Answer 1

这是我想出的一个解决方案。它不会生成“b”断开的路径。它生成一条穿过所有宿舍楼和入口的路径。

• 计算每对节点之间的距离（X坐标差+Y坐标差）。现在你有了一个完整的图表。
• 求这个完整图的 MST
• MST 的每个倾斜边缘（非垂直或水平的倾斜边缘）都可以分为两部分 - 水平部分和垂直部分。
• 每个分割可以通过两种方式进行 - 先水平分割，然后垂直分割，或者反之亦然。
• 遍历每个这样的排列并计算长度最小的路径。这就是答案。