algorithm - 通路/道路铺设问题

Question

今天我们有一项任务要在实验室完成(两个小时内)。问题是:

• 给你一个 m*n 矩阵。
• 矩阵有“h”个宿舍楼和“b”个主楼入口。
• 这些“h”大厅和“b”入口的位置是已知的(根据 (x,y) 坐标)。
• 您需要铺设 channel ，使每个宿舍楼至少有一条路可以到达“b”入口之一。
• 最多可以有 'b' 个这样的断开连接的路径。
• 路径的长度必须最短。
• 你只能上下左右移动。
• 解决方案不能是蛮力尝试。

任务结束。但我仍在思考如何解决这个问题。是否有此类问题的标准术语？我应该阅读什么？

人们是否也使用此类算法在城市中铺设道路？

Answer 1

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

• 计算每对节点之间的距离(X坐标差+Y坐标差)。现在你有了一个完整的图表。
• 找到这个完整图的 MST
• MST 的每个倾斜边(既不垂直也不水平)都可以分成两部分 - 水平部分和垂直部分。
• 每次拆分都可以通过两种方式进行 - 首先是水平拆分，然后是垂直拆分，反之亦然。
• 遍历每个这样的排列并计算出长度最短的路径。这就是答案。