路径/道路铺设问题

Question

今天，我们在实验室（两个小时内）完成了一项任务。问题是：

• 您给您一个m*n矩阵。
• 矩阵具有“ H”住宅大厅和“ B”主建筑入口。
• 这些“ H”大厅和“ B”入口的位置是已知的（以（x，y）坐标为角度）。
• 您需要铺设路径，以便每个住宅大厅至少有一种进入“ B”入口之一的方法。
• 这种断开的途径最多可以有“ b”。
• 路径的长度必须最小。
• 您只能向上移动，向下，左右移动。
• 该解决方案不得是蛮力的尝试。

作业结束了。但是我仍在考虑如何解决。有这样的问题的标准术语吗？我应该阅读什么？

人们是否也将这种算法也用于城市的道路？

Answer 1

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

• 计算每对节点之间的距离（x坐标的差异 + y坐标的差异）。现在您有了一个完整的图形。
• 找到此完整图的MST
• MST的每个倾斜边缘（不是垂直或水平的）可以分为两个部分 - 水平和垂直。
• 每个分裂都可以通过两种方式进行 - 首先是水平的，其次是垂直的，反之亦然。
• 浏览每个这样的排列，并以最小长度计算路径。这是答案。

Answer 2

无法告诉您解决方案是什么（一个猜测，某种成本路径分析），但是我在道路建模软件方面有一些经验。

在规模的一端，您拥有使用类似（广义）方法的战略建模系统。可以将它们视为重力模型 - 它将使用交通产生和需求的估计值，以高水平对居民的交通流量进行高水平的预测。在重大计划发展的宏观影响下，人口分配或土地利用区的变化。

在另一端，您拥有城市，城镇，交汇处等特定区域的模拟模型。这些是数字模型，它们将每辆车视为具有侵略性，道路知识等因素的自主剂。这是一种非常蛮力的方法，但这是在复杂网络中提供有用的统计数据的唯一方法，具有交通灯，公共汽车等功能。流量模板可以将其插入实际的流量控制数据，为特定设计解决方案运行特定时期的模型，并将其设置为6或7次。最终的数据使您可以很好地评估特定解决方案对另一个解决方案（或现状）的性能。

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

Answer 3

问题描述的一个方面对我来说并不清楚：

• 当您说“您需要铺设路径”时，这是否意味着”只有一个 连接路径？”还是可以有多个断开路径？

但是无论您回答我的问题，这是一个非常棘手的问题：它是NP-HARD，因为它包括 直线坦纳树 问题是特殊情况（只有一个主建筑入口时）。

因此，没有人知道如何在一般情况下有效地解决它！

Answer 4

我认为问题更简单，而不是斯坦纳树，甚至不是最小的生成树。

1. 表示矩阵M为v = {mij | i <= m，j <= n}，e = {（mi1j1，mi2j2）：i1，i2 <= m，j1，j2 <= n，| i1-i2 | = 1-排名或| J1-J2 | = 2}

2. 乘坐B套入口，大厅套H

3. h'= h/b，b'= b/h（标记入口的大厅，在深度0到达，删除所有这些入口，因为这些入口是大厅）

4. 做一个广度第一的遍历。在每个深度标记可以从B到达的大厅，直到所有大厅都被标记为。选择相应的途径。

Answer 5

这是一个搜索问题。您应该在2个小时内完成此操作，对吗？我会 DFS 和 修剪. 。您可以使用 启发式方法 更快地获得更好的解决方案。但是请记住，启发式方法不能保证最佳解决方案，因此您必须 尝试所有可能性. 。似乎是NP-HARD。