道路/道路铺设问题

Question

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

• 你得到了一个m*n矩阵。
• 该矩阵有“h”住宅大厅和“b”主建筑入口。
• 这些'h‘大厅和'b’入口的位置是已知的(以(x，y)坐标表示)。
• 你需要铺设通道，这样每个住宅大厅都至少有一条路可以到达“b”入口。
• 最多只能有这样的“b”条不相连的路径。
• 通路的长度必须是最小的。
• 你只能向上、向下、左或右移动。
• 解决办法绝不能是蛮力的企图。

任务结束了。但我还是在想如何解决这个问题。这些问题是否有一个标准的术语？我该读些什么？

人们是否也使用这样的算法在城市铺设道路？

Answer 1

这是我想出的解决方案。它不会生成“b”断开连接的路径。它产生了一条穿过所有住宅大厅和入口的道路。

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

Answer 2

无法告诉您解决方案是什么(某种最小成本的路径分析，猜测)，但我有一些经验的道路建模软件。

在规模的一端，您有使用类似(广义地说)方法的战略建模系统。它们可以被认为是一种重力模型--它将使用交通生成和需求的估计值，对诸如城镇或工业区到居民区等之间的交通流量进行高水平预测。这主要用于研究重大规划发展、人口分布变化或土地利用地带的宏观影响。这类事。

另一方面，你有城市、城镇、立交等特定区域的模拟模型。这些是数字模型，把每辆车当作一个具有攻击性、道路知识等因素的自主代理。这在很大程度上是一种蛮力式的方法，但它是提供复杂网络中实际交通行为的有用统计数据的唯一方法，如交通灯、公共汽车等。例如，交通建模者可以将其插入实际的交通控制数据，为特定的设计解决方案运行特定时期的模型，并将其设置为运行6或7次。得到的数据可以很好地评估特定解决方案相对于另一个解决方案(或现状)的性能。

希望这能提供一些有用的背景。

Answer 3

在问题描述的一个方面，我不太清楚：

• 当你说“你需要铺设一条路”时，这是否意味着“只有一条连接的路径？”或者可以有多条断开的路径？(例如，从霍尔H1到建筑物入口B1的一条小路，以及从霍尔H2到建筑物入口B2的一条单独的道路)

但是不管你怎么回答我的问题，这是一个非常棘手的问题:它是NP难的，因为它包括直线Steiner树问题作为一个特例(当只有一个主要的建筑物入口)。

所以在一般情况下，没有人知道如何有效地解决这个问题！