道路/道路铺设问题

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

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

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

在规模的一端,您有使用类似(广义上说)方法的战略建模系统。它们可以被看作是一个重力模型——它将使用交通生成和需求的估计来对城镇之间或工业区到住宅区之间的交通流进行高水平的预测。这对于研究主要规划开发的宏观影响非常有用,人口分布或土地利用区的变化。。那种事。

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

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

我不清楚问题描述的某个方面:

• 当你说“你需要铺设一条道路”时,这是否意味着 只有一个 连接路径?“或者可以有多条断开连接的路径?(例如,从H1厅到B1号楼入口的通道,以及从H2厅到B2号楼入口的单独通道)

但是不管你怎么回答我的问题,这是一个非常棘手的问题:它是NP难的,因为它包括 rectilinear Steiner tree 特殊情况下的问题(只有一个主建筑入口)。

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

我认为问题比较简单,不是Steiner树,甚至不是最小生成树。

1. 用V={M i j | i<=M,j<=n},E={(M i1 j1,M i2 j2):i1,i2<=M,j1,j2<=n,| i1-i2 |=1-异或| j1-j2 |=2}将矩阵M表示为图G

2. 走B组入口,H组大厅

3. H’=H/B,B’=B/H(标出入口大厅,它们在0深度处到达,移除所有这些入口,因为它们是大厅)

4. 做一个广度优先遍历。在每一个深度标记可以从B到达的大厅,直到标记所有大厅。选择相应的路径。

这是一个搜索问题。你应该在两小时内完成,对吧?我会的 外勤支助 和 修剪 . 你可以用 启发式 以便更快地找到更好的解决方案。但是记住,启发式方法不能保证最优解,所以你必须 尽一切可能 . 似乎是NP难。