Pathway/road laying problem

Question

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?

Answer 1

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.

• Calculate the distance between each pair of nodes (difference of X coordinates + difference of Y coordinates). Now you have a complete graph.
• Find the MST for this complete graph
• Each inclined edge of the MST (those that are not vertical or horizontal) can be split into two parts - the horizontal and the vertical.
• Each split can be made in two ways - either horizontal first followed by vertical or vice versa.
• Go through each such permutation and calculate the path with the least length. This is the answer.

Answer 2

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.

Answer 3

There's an aspect of the problem description that isn't clear to me:

• When you say, "You need to lay a pathway", does that mean "just one connected path?" Or can there be multiple disconnected paths? (e.g. a path from hall H1 to building entrance B1 and a separate path from hall H2 to building entrance B2)

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!

Answer 4

I think the problem is simpler and not Steiner tree or not even minimum spanning tree .

1. 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}

2. Take set B of entrances, set H of halls

3. 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)

4. 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.

Answer 5

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.