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.