Shortest distance to travel 100 largest US cities

[Hacp]

If one took the 100 largest cities in the US and wanted to travel them all, what is the distance of the shortest route? A friend asked me this question and I told him it that he was crazy if he expected me measure the distance between each city, but I'm sure there's a simple answer. Anyone wanna help?

A quick google revealed nothing.

 

[Colt45]

write a script to brute force it for ya, i guess.

 

[Hacp]

write a script to brute force it for ya, i guess.

Yes, I'm sure a computer could solve it very fast. The big problem is getting the list of 100 cities and the distances between them. Manually measuring will take a long time. Perhaps a GPS machine can do it really fast? Just plug in the cities and the GPS has to have an algorithm to solve it. I don't own a gps machine however.

I tried using google maps. You need to order the cities so it doesn't work.

 

[lxskllr]

Distance doesn't always relate to speed. 2 cities may be closer, but take longer to get to due to terrain, or roads. I don't think there's any substitute for doing it manually. Google the cities, then pull out your map and get to work. It shouldn't take longer than an hour.

Edit:
I didn't realize this was a standardized problem.

 

[Schadenfroh]

http://en.wikipedia.org/wiki/Travelling_salesman_problem

 

[Colt45]

http://en.wikipedia.org/wiki/Travelling_salesman_problem

I couldn't remember the name of it!

 

[Hacp]

http://en.wikipedia.org/wiki/Travelling_salesman_problem

So what is the correct algorithm? I knew there had to be an easy solution.

 

[Schadenfroh]

n/m too tired to explain further, might check back in the morning.

 

[eLiu]

So what is the correct algorithm? I knew there had to be an easy solution.

Haha just b/c the problem is named doesn't mean it's easy.

The traveling salesman problem is part of a class of problems that tragically require exponential time (i.e., you have to check every possibility) to find the answer. In fact, if I give you a path, checking if I gave you the right answer is just as complicated.

Brute force is the only way to be sure. But there are a number of approximate algorithms that will give you a good answer. You can search for 'traveling salesman approximation algorithms' to find some... the two famous ones give you the answer within a factor of 2 and a factor of 1.5 respectively, in the worst case. Optimization techniques like simulated annealing can give you a much better answer but not provably so.

-Eric

 

[mfenn]

So what is the correct algorithm? I knew there had to be an easy solution.

The easiest algorithm would be to just try all permutations. However, this would take far too long for even a relatively small number of cities. A fast algorithm is going to be fairly complex (well complex to show that it works, maybe/maybe not complex to implement). Quite a bit of CS research is focused on finding fast solutions to the TSP for theoretical reasons I don't really want to get into.

 

[silverpig]

Once you get a quantum computer, this problem becomes significantly easier

 

[Damn Dirty Ape]

couldn't one take a mapping program, enter 1st city as start, 2nd as destination, all the others as 'stops' or 'via' and ask it to calculate the shortest distance?

 

[Ken g6]

couldn't one take a mapping program, enter 1st city as start, 2nd as destination, all the others as 'stops' or 'via' and ask it to calculate the shortest distance?

Sure. But what order do you put them in? :sneaky:

Probably the first step is to find the distance between each city and all the other cities. This takes 5000 steps; and it would be good to check each route to make sure it doesn't go through another city on the list.

Once you have that you can run a TSP algorithm.

 

[Crusty]

Are you flying to 100 cities or driving?

 

[Damn Dirty Ape]

Sure. But what order do you put them in? :sneaky:

Probably the first step is to find the distance between each city and all the other cities. This takes 5000 steps; and it would be good to check each route to make sure it doesn't go through another city on the list.

Once you have that you can run a TSP algorithm.

well if you started at say Seattle washington you would do a ballpark visual and work from there...

 

[Ken g6]

Are you flying to 100 cities or driving?

Considering Anchorage and Honolulu are in the list, I suggest at least some flying.

well if you started at say Seattle washington you would do a ballpark visual and work from there...

Huh? OK...

What does Safeco Field have to do with anything?

If you're suggesting going to the nearest city at each point (a greedy algorithm), that's not the worst thing you could do, but it could back you into a corner. For instance, if you start in San Diego, you could go up the coast to Washington, then find that the next nearest city is way over in Denver. Or you might miss a city in California entirely, not find out until near the end, and have to go there from Maine.

 

[DrPizza]

Writing a program to solve the problem would take 5 or 10 minutes for an average programmer. However, the amount of time the program would need to run is, well, a LONG LONG LONG time.

There are 9.33 x 10^157 different permutations. The only way to be certain of the final answer is to check all of the permutations. Well, with a little thought though, you'll be quick to point out that there must be TWO solutions - one is simply running the trip in the reverse direction. So, you only need to check 4.666 x 10^157 permutations. Unfortunately, that 10^157 number is still the same. It's a big number. More (far far far far far more) than all the atoms in the known universe. In fact, it's only 3 orders of magnitude from being the number of particles in as many identical universes as there are particles in this universe.

Let's say you could test 1 quadrillion possibilities per second. No computer, and I think that includes super computers, comes anywhere close. But for the sake of argument, 1 quadrillion possibilities per second. That's 10^15 possibilities per second. Divide. That's 10^142 seconds before you're done. Longer than the universe is going to be around. The universe has been around for less than 10^18 seconds (to put it in perspective.)

Of course, you can streamline the process by using something similar to the Greedy algorithm posted above, then once you have a possibly somewhat short answer, you can stop calculating distances once they exceed that value (or a new shortest distance value.)

You might even be able to trim the computation down to something that can be calculated within a few hundred years, but that might be generous.

 

[Evadman]

100! is a lot.

 

[PsiStar]

these tasks are now solved with expert systems or genetic algorithms although I have not seen them applied to the traveling salesman I have to think that it has been ... just not published that I have found

 

[amdhunter]

My Garmin could probably solve this for you.

 

[HardcoreRobot]

My Garmin could probably solve this for you.

probably not

 

[Miramonti]

Its not far if you measure the distance with a small map of the United States and a ruler. That way the combined distance is only a few feet, perhaps a couple yards at the most. It won't take much time to travel a couple yards.

 

[mfenn]

Writing a program to solve the problem would take 5 or 10 minutes for an average programmer. However, the amount of time the program would need to run is, well, a LONG LONG LONG time.

There are 9.33 x 10^157 different permutations. The only way to be certain of the final answer is to check all of the permutations. Well, with a little thought though, you'll be quick to point out that there must be TWO solutions - one is simply running the trip in the reverse direction. So, you only need to check 4.666 x 10^157 permutations. Unfortunately, that 10^157 number is still the same. It's a big number. More (far far far far far more) than all the atoms in the known universe. In fact, it's only 3 orders of magnitude from being the number of particles in as many identical universes as there are particles in this universe.

Let's say you could test 1 quadrillion possibilities per second. No computer, and I think that includes super computers, comes anywhere close. But for the sake of argument, 1 quadrillion possibilities per second. That's 10^15 possibilities per second. Divide. That's 10^142 seconds before you're done. Longer than the universe is going to be around. The universe has been around for less than 10^18 seconds (to put it in perspective.)

Of course, you can streamline the process by using something similar to the Greedy algorithm posted above, then once you have a possibly somewhat short answer, you can stop calculating distances once they exceed that value (or a new shortest distance value.)

You might even be able to trim the computation down to something that can be calculated within a few hundred years, but that might be generous.

Yep, the best known exact algorithms can get the running time down to O(2^n), but that's still pretty unreasonable to calculate on a single machine. To get a reasonable runtime, you have to be OK with an approximation algorithm.

 

[SsupernovaE]

I have a quantum computer I built just for this type of problem. Unfortunately, it was built for 99 cities, so it's a few qubits short. I can build you what you need for $25,000,000,000,000 and 20 million liters of liquid helium.

 

[Anubis]

someone needs to write a distributed computing program to solve this IMO