12

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

  • 你得到一个 m*n 矩阵。
  • 矩阵有'h'住宅大厅和'b'主楼入口。
  • 这些“h”大厅和“b”入口的位置是已知的（根据 (x,y) 坐标）。
  • 您需要铺设路径，以便每个住宅大厅至少有一种方式可以到达“b”入口之一。
  • 最多可以有“b”个这样的不连贯的路径。
  • 路径的长度必须最短。
  • 您只能向上、向下、向左或向右移动。
  • 解决方案不能是蛮力尝试。

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

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

4

5 回答 5

3

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

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

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

在规模的一端，您拥有使用类似（广义上）方法的战略建模系统。它们可以被认为是一个重力模型——它将使用对交通产生和需求的估计来对城镇和城市之间或工业区到住宅等之间的交通流量进行高级预测。这对于寻找在重大计划发展的宏观影响，人口分布或土地使用区的变化……诸如此类的事情。

在另一端，您有城市、城镇、交汇处等特定区域的模拟模型。这些数字模型将每辆车视为具有攻击性、道路知识等因素的自主代理。这是一种非常暴力的方法，但它是在具有交通灯、公共汽车等特征的复杂网络中提供有关实际交通行为的有用统计数据的唯一方法。例如，交通建模者可以将其插入到实际交通控制数据，针对特定设计解决方案在特定时期运行模型并将其设置为运行 6 或 7 次。生成的数据可以很好地评估特定解决方案相对于另一个解决方案（或现状）的性能。

希望这提供了一些有用的上下文。

于 2010-11-25T21:00:37.433 回答
1

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

  • 当您说“您需要铺设一条路径”时，这是否意味着“只有一条连接的路径”？或者可以有多个断开的路径？（例如从 H1 大厅到 B1 入口的路径和从 H2 到 B2 入口的单独路径）

但是，无论您如何回答我的问题，这是一个非常棘手的问题：它是 NP 难题，因为它包括作为特例的直线施泰纳树问题（当只有一个主建筑入口时）。

所以在一般情况下没有人知道如何有效地解决它！

于 2010-11-25T21:34:50.633 回答
1

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

  1. 将矩阵 M 表示为图 G，其中 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 到达的大厅，直到所有大厅都被标记。选择相应的路径。

于 2010-11-26T02:25:08.433 回答
1

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

于 2010-11-29T02:59:50.860 回答