铺设路径/道路问题

Question

铺设路径/道路问题

algorithmoptimizationvariable-assignmentgraph-algorithm

12

今天我们在实验室里拿到了一份作业（两个小时内完成）。问题如下：

给出一个m*n的矩阵。
该矩阵有'h'个住宅大楼和'b'个主要建筑入口。
已知这些'h'个住宅大楼和'b'个入口的位置（以(x,y)坐标表示）。
你需要铺设通道，使得每个住宅大楼都至少有一条到达'b'个入口中的一个的路径。
最多可以有'b'条不连通的路径。
路径长度必须最小化。
你只能向上、下、左、右四个方向移动。
解决方案不能是暴力尝试。

作业已经结束，但我还在思考如何解决。这类问题有没有标准术语？我该去哪里寻找相关信息？

人们是否也会使用这样的算法来规划城市道路呢？

- Utkarsh Sinha

5个回答

2

我不确定解决方案是什么（可能是某种最小成本路径分析），但我有一些道路建模软件的经验。

在一个极端，你有战略建模系统，它们使用类似的方法。可以将其视为重力模型-它将使用交通产生和需求的估计值来进行高级预测，例如城镇和城市之间的交通流量、工业区到住宅区等。这主要用于研究重大计划开发、人口分布或土地利用区域的宏观影响。

另一方面，你有特定区域的模拟模型，例如城市、城镇、交换机等。这些是数字模型，将每辆车看作自主代理，考虑了诸如侵略性、道路知识等因素。这是一种非常粗暴的方法，但它是提供复杂网络中实际交通行为有用统计数据的唯一方法，包括交通信号灯、公交车等功能。例如，交通模拟者可以将其插入实际交通控制数据，运行特定期间的模型，为特定设计方案设置运行6或7次。得出的数据可以很好地评估特定解决方案与另一个（或现状）的性能。

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

- Hamish

有趣！你用了什么软件？我想试试看。 - Utkarsh Sinha

1

问题描述中有一个方面我不太清楚：

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

但无论你如何回答我的问题，这都是一个非常棘手的问题：它是NP难问题，因为它包括直角斯坦纳树问题作为特殊情况（当只有一个主要建筑入口时）。

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

- Gareth Rees

我刚刚修复了这个问题。你可以有多条路径。感谢提供术语 - 直角斯坦纳树...我会去了解一下！ - Utkarsh Sinha

1

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

将矩阵 M 表示为图 G，其中 V = {Mij | i ≤ m, j ≤ n}，E = {(Mi1j1，Mi2j2)：i1，i2 ≤ m，j1，j2 ≤ n，| i1-i2 | = 1异或| j1-j2 | = 2}
取入口集合 B，大厅集合 H
H' = H / B，B' = B / H（标记作为入口的大厅，它们在深度 0 处到达，删除所有这些入口，因为它们是大厅）
进行广度优先遍历。在每个深度上，标记可以从 B 到达的大厅，直到所有大厅都被标记。选择相应的通道。

- Om Deshmane

1

这是否是路径的最小长度？例如：H1 =（5,5）H2 =（6,9）B1 =（12,5）B2 =（10,10）。H2非常靠近B2，但没有路径。H1直接连接到B1。而H2连接到该路径。 - Utkarsh Sinha

我明白你的意思了，我的回答是基于最小长度路径集合的理解。但看了你的评论后，我发现你是在寻找一组路径，使它们的长度之和最小。那么我需要重新尝试一下。 - Om Deshmane

这是我的第一反应，一种类似洪水填充算法的方法。我同意问题不够清晰。 - Matthieu M.

1

这是一个搜索问题。你原本预计要在2小时内完成，对吧？我会使用深度优先搜索和剪枝。你可以使用启发式算法来更快地找到更好的解决方案。但请记住，启发式算法不能保证最优解，所以你必须尝试所有可能性。看起来是NP难问题。

- Jungle Hunter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Utkarsh Sinha · Accepted Answer

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

计算每对节点之间的距离（X坐标差加上Y坐标差）。现在你有了一个完整的图。
找到这个完整图的MST
MST的每个倾斜边（那些不是垂直或水平的边）可以分成两部分 - 水平和垂直。
每个拆分可以用两种方式进行 - 先水平后垂直或先垂直后水平。
遍历每个排列并计算最短长度的路径。这就是答案。