通路/道路铺设问题
今天我们有一项作业要在实验室完成（两小时内）。问题是：
- 给你一个 m*n 矩阵。
- 该矩阵有“h”个宿舍楼和“b”个主楼入口。
- 这些“h”大厅和“b”入口的位置是已知的（以（x，y）坐标表示）。
- 您需要铺设通道，使每个宿舍楼至少有一条路可以到达“b”入口之一。
- 最多可以有“b”条这样的断开路径。
- 路径的长度必须是最短的。
- 您只能向上、向下、向左或向右移动。
- 解决方案不能是暴力尝试。
任务结束了。但我还在想如何解决这个问题。此类问题有标准术语吗？我应该读什么？
人们也在城市中使用这样的算法来铺设道路吗？
Today we got an assignment to complete in lab (in two hours). The question was:
- You're given an m*n matrix.
- The matrix has 'h' residential halls and 'b' main building entrances.
- The location of these 'h' halls and 'b' entrances is known (in terms of (x,y) coordinates).
- You need to lay pathways such that every residential hall has at least one way to reach one of the 'b' entrances.
- There can be at most 'b' such disconnected pathways.
- The length of the pathway must be minimum.
- You can only move up, down, left or right.
- The solution must not be a brute force attempt.
The assignment is over. But I'm still thinking how this would be solved. Is there a standard term for such problems? What should I read up?
Do people use such algorithms to laying roads in cities as well?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
这是一个搜索问题。你应该在 2 小时内完成，对吗？我会DFS和修剪。您可以使用启发式更快地找到更好的解决方案。但请记住，启发式方法不能保证最佳解决方案，因此您必须尝试所有可能性。看起来是NP难的。
It is a search problem. You were expected to do it in 2 hours, right? I would DFS and prune. You could use heuristics to get to the better solutions faster. But keep in mind heuristics can not guarantee optimal solutions so you will have to try all possibilities. Seems to be NP-hard.
这是我想出的一个解决方案。它不会生成“b”断开的路径。它生成一条穿过所有宿舍楼和入口的路径。
Here's a solution I came up with. It doesn't generate 'b' disconnected paths. It generates one path that goes through all residential halls and entrances.
无法告诉您解决方案是什么（猜测是某种最低成本路径分析），但我对道路建模软件有一些经验。
一方面，您拥有使用类似（广义上）方法的战略建模系统。它们可以被认为是一个重力模型 - 它将使用交通产生和需求的估计来对城镇和城市、工业区到住宅区等之间的交通流量进行高级预测。这主要用于查找重大规划开发的宏观影响、人口分布或土地利用区域的变化……诸如此类的事情。
在另一端，你有城市、城镇、立交桥等特定区域的模拟模型。这些数字模型将每辆车视为具有攻击性、道路知识等因素的自主代理。这在很大程度上是一种蛮力式的方法，但它是在具有交通信号灯、公共汽车等功能的复杂网络中提供有关实际流量行为的有用统计数据的唯一方法。例如，流量建模者可以将其插入根据实际的交通控制数据，针对特定的设计方案运行模型一段特定的时间，并设置其运行6或7次。生成的数据可以让您很好地评估特定解决方案相对于另一个解决方案（或现状）的性能。
希望这提供了一些有用的背景。
Couldn't tell you what the solution is (some sort of least cost path analysis, at a guess), but I have some experience with road modelling software.
At one end of the scale you have strategic modelling systems that use a similar (broadly speaking) approach. They can be thought of like a gravity model - it will use estimates of traffic generation and demand to make high level predictions of traffic flows between, for example, towns and cities, or industrial areas to residential, etc. This is mostly useful for looking at the macro effects of major planned developments, changes in population distribution or land-use zones.. that sort of thing.
At the other end you have simulation models of specific areas of a city, town, interchange, etc. These are numeric models that treat each car as an autonomous agent with factors like aggression, road knowledge, and so on. This is very much a brute force style approach, but it is the only way to provide useful statistics on actual traffic behaviour in a complex network with features like traffic lights, buses, etc. A traffic modeller can, for example, plug it into the actual traffic control data, run the model for a specific period for a specific design solutions and set it to run 6 or 7 times. The resulting data gives you a very good assessment of the performance of a particular solution against another (or the status quo).
Hope this provides some useful context.
我不清楚问题描述的一个方面：
但是无论您如何回答我的问题，这是一个非常棘手的问题：它是 NP 困难的，因为它包含 直线斯坦纳树问题作为一种特殊情况（当只有一个主建筑入口时）。
所以没有人知道如何在一般情况下有效地解决它！
There's an aspect of the problem description that isn't clear to me:
But however you answer my question, this is an extremely tricky problem: it's NP-hard as it includes the rectilinear Steiner tree problem as a special case (when there's just one main building entrance).
So no-one knows how to solve it efficiently in the general case!
我认为问题更简单，不是斯坦纳树，甚至不是最小生成树。
将矩阵 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 可以到达的大厅，直到标记所有大厅。选择相应的路径。
I think the problem is simpler and not Steiner tree or not even minimum spanning tree .
Represent matrix M as a graph G with V ={Mij | i <=m, j <= n}, E= {(Mi1j1,Mi2j2) : i1,i2 <=m, j1,j2<=n, |i1-i2| = 1-exclusive OR |j1-j2| = 2}
Take set B of entrances, set H of halls
H' = H/B, B' = B/H (mark the halls that are entrances, they are reached at depth 0, remove all these entrances as those are halls)
Do a breadth-first traversal. At each depth mark the halls that can be reached from B until all halls are marked. Pick corresponding pathways.