Shortest Road Length

Originally posted by luskin
Very interesting. Never come across that before.

Yeah, I think Steiner tree constructions are kinda cool. I thought of this question because I was reading the following paper which has some background on known-to-be-optimal (minimum) Steiner trees for different nxn arrays: "Steiner Trees on a Checkerboard," F. Chung, M. Gardner, and R. Graham, Mathematics Magazine 62(2), 1989, pp. 83-96.

The minimum tree looks pretty cool for a chessboard (treating, say, the center of each square as one point of an 8x8 array; or you could treat all the square corners as points within a 9x9 array).

Originally posted by AThousandYoung
3. A road from A to B, one from B to C, one from C to D.

The Steiner tree is very interesting. But it seems to me that if the problem were: how to get to all three cities travelling the minimum length of road that the answer would be 3. The Steiner solution is interesting but leads to inefficient use of time and fuel.

Originally posted by thyme
The Steiner tree is very interesting. But it seems to me that if the problem were: how to get to all three cities travelling the minimum length of road that the answer would be 3. The Steiner solution is interesting but leads to inefficient use of time and fuel.

But once you factor in the cost of road building...