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

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

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

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

有帮助吗?

解决方案

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

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

其他提示

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

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

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

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

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

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

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

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

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

  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到达的大厅,直到所有大厅都被标记为。选择相应的途径。

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

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top