Specify most efficient roads connecting Seattle, San Francisco, Los Angeles, New York, and Miami (see details)

Question

I've been puzzled by the idea of building efficient roads based on the following criteria:
1) Minimize total length of roads built (each mile costs 1 point)
2) Minimize distance required to travel between any two cities specified (each mile costs one point, with total distance score = sum of roads required to travel between all distinct pairs of cities)

Notes:
Ignore existing roads in this problem. You are building roads from scratch.

Ignore topography. You can build roads anywhere.

Roads do not need to connect two cities directly... you can have "ghost nodes" between cities that roads connect through, if that makes your system more efficient.

Where would you put the roads to minimize total points? What technique did you use to determine your solution?

No, I'm not in college taking a final exam. I'm just personally curious about this problem.

Answer 1

I would think Steiner Trees might be useful in this situation (link 1).

Using an applet I found on the web (link 2) for heuristically solving Steiner Trees, I estimated the positions of Seattle, San Francisco, Los Angeles, New York and Miami. It connected these nodes as follows.
1) Los Angeles and San Francisco got connected at a node just east of San Francisco.
2) This new node connected to Seattle through a node in eastern Oregon.
3) Miami and New York got connected to a node around West Virginia.
4) The node in Oregon and the node in West Virginia got connected across the country.

I overlaid this on the original map of the US and it looks like the attached picture:

http://img176.imageshack.us/img176/6573/steinermap5nodeshs9.jpg

Now this isn't very exact because we are using flat coordinates on a plane and these cities are really on the surface of a sphere, but you get the idea.

Have fun playing with the applet. I must have spent a good 45 minutes just picking points and watching it connect them with lines.

Answer 2

i will put a 100% straight road between Los Angeles and SF which could take less points because of its straight direction.. 380 miles ( aprox.)is the distance between those cities so if the road goes in straight direction will take less than 380 miles!
I tried to answer your question i dont know if it's make sense to you lol........
Happy holidays
______________
EDIT Ohhh now i figured it out ..i had to join all the cities i thought just a couple of them..
You seee!! the answer of Puzzling has the same idea then mine..STRAIGHT DIRECTIONS! Easy you dont need to give a very formal answer lol
Happy Holidays!!

Answer 3

buy a plane and forget the roads, rewrite history is that what you trying to do? is this to do with computer problem? or an operator problem?