Althouse: "Computing the optimal road trip across the U.S."

२२ मे, २०१५

"Computing the optimal road trip across the U.S."

"[W]e needed to look up 2,500 directions to get the 'true' distance between all 50 landmarks... Now with the 2,500 landmark-landmark distances, our next step was to approach the task as a traveling salesman problem: We needed to order the list of landmarks such that the total distance traveled between them is as small as possible if we visited them in order. This means finding the route that backtracks as little as possible...."

३२ टिप्पण्या:

J2 म्हणाले...: 1. "Wallyworld"; २२/५/१५, ७:३० AM
MadisonMan म्हणाले...: Why pick Taliesin when you can pick The House on the Rock?; २२/५/१५, ७:३५ AM
paminwi म्हणाले...: If you like road trips - awesome!
Some places I'd leave out, others I'd add but it would be a good staring point for someone so inclined.

As far as Taliesin - I think others are more impressed with FLW than I will ever be after reading a biography of him. He was an ass.; २२/५/१५, ७:३८ AM
pm317 म्हणाले...: Cool! In the comments people are questioning some of the choices for the landmarks though.; २२/५/१५, ७:३८ AM
john म्हणाले...: Don't focus on the stops, focus instead on the method. You can design your own optimal trip with these instructions, then you can fit in all the Nebraska cornfields you wish.; २२/५/१५, ७:३८ AM
jimbino म्हणाले...: The drive from San Antonio to Carlsbad will be longer and more boring than one through Nebraska cornfields.

Do me the favor of keeping track of all the Black, Brown and Red American faces you see in those vaunted national parks, forests and monuments. I bet you find about 1 minority face to 1000 white faces. You would find the same variety if you toured Florida golf clubs and gated communities.

The difference is that our minorities are not charged for acquiring and maintaining those gated white communities and white golf clubs.; २२/५/१५, ७:५२ AM
pm317 म्हणाले...: The order of the states to visit without too much backtracking does not need a Genetic TSP alg..; २२/५/१५, ७:५७ AM
WillowViney म्हणाले...: Given that TSP is NP-Complete, solving it for N=25,000 might take a while. Years maybe?; २२/५/१५, ८:०३ AM
Etienne म्हणाले...: With 40,000 deaths on the roads every year, I encourage everyone to get out there and participate.; २२/५/१५, ८:०३ AM
Roger Sweeny म्हणाले...: If you're going to drive a lot, the driving should be part of the pleasure. Forget this and get a copy of The [120] Most Scenic Drives in America (which includes a lot of destinations along the way).; २२/५/१५, ८:१० AM
Jaq म्हणाले...: Out of the top 400 recommended cities to visit on TripAdvisor, none were from North Dakota, Vermont, nor West Virginia. This is especially interesting because TripAdvisor reviewers recommend cities like Flint, MI — the 7th most crime-ridden city in the U.S. — over any city in North Dakota, Vermont, and West Virginia. I’ll leave the interpretation of that fact to the reader.

Color me unsurprised. I was wondering when I saw this were they would go in our great state. Maybe the site of the St Albans raid, where Confederate soldiers robbed a bank near the Canadian border?

IDK, Shelburn Farms? I guess... There are lots of national forests here, but no national parks. Burlington is cute, but so is Ithaca, State College, etc... Vermont is more a federation of small things joined together along the idea of being an English speaking version of the French countryside. There is no *one* place to visit here. But at Shelburn Farms, there is a view of the lake and across it the Adirondacks, specifically the Adirondack park on the far side, and the view is unspoiled on the Vermont side by development beyond hay fields and the occasional barn. It really does look like a painting right out of the "Hudson Valley School." So they should take a nice camera, a tripod, and a lot of time to wait for the light to be just right.; २२/५/१५, ८:१२ AM
Jaq म्हणाले...: @jimbino,
We got your message. White people should stop reproducing, we should raze the National Parks and sell the land for condos.; २२/५/१५, ८:१३ AM
Etienne म्हणाले...: ...we should raze the National Parks and sell the land for condos.

It would help pay off the Reagan years of the debt :-); २२/५/१५, ८:२४ AM
Clyde म्हणाले...: Shouldn't it be 2,450 rather than 2,500? 50 destinations times the other 49?; २२/५/१५, ८:२७ AM
Jaq म्हणाले...: It would help pay off the Reagan years of the debt :-)

What are we going to to sell off to pay for the fact that Obama doubled it?; २२/५/१५, ८:३१ AM
Ignorance is Bliss म्हणाले...: Willow Viney said...

Given that TSP is NP-Complete, solving it for N=25,000 might take a while. Years maybe?

The number of routes they give is 2,500, not 25,000. And, as Clyde points out, it should be 2450.

But that is the number of routes. When discussing the complexity of the TSP, N is the number of cities, not the number of routes. Thus, N = 50.; २२/५/१५, ८:३२ AM
Etienne म्हणाले...: What are we going to to sell off to pay for the fact that Obama doubled it?

I'd sell Wyoming to the ranchers who are squatting on federal land already.; २२/५/१५, ८:३४ AM
lgv म्हणाले...: Someone like me thinks this is totally awesome and deserves a Nobel Prize. But then again, I once thought every decision in my life could be represented in a multiple regression or linear programming model.

Now, where the application that allows us to pick and choose all the landmarks and spits out the optimum route for our selected landmarks and starting point? Better hurry if he wants to monetize this puppy.; २२/५/१५, ८:४२ AM
Eric the Fruit Bat म्हणाले...: (1) They played that kind of nodal analysis for laughs on The Big Bang Theory. Had something to do with the guys using a dry erase board to figure out where to get dinner before a movie or something like that.

Sheldon made the project more complicated than it had to be, of course.

(2) Watched a bit of Cowboys & Aliens, last night. Too much CGI jiggy stuff zipping across the screen for my middle-aged tastes, but Olivia Wilde may quite possibly be the most beautiful woman ever in the entire history of the human species.

A compensation.; २२/५/१५, ८:४७ AM
Jaq म्हणाले...: It only takes one hot woman to make a movie bearable.; २२/५/१५, ९:०२ AM
Ignorance is Bliss म्हणाले...: With 50 landmarks to put in order, we would have to exhaustively evaluate 3 x 1064 possible routes to find the shortest one.

To provide some context: If you started computing this problem on your home computer right now, you’d find the optimal route in about 9.64 x 1052 years — long after the Sun has entered its red giant phase and devoured the Earth.

Silly alarmism.

They're talking about the brute force approach. If they use a smarter algorithm they can get a perfect solution in ~300,000 years. Plenty of time to plan your trip before the Sun goes red-giant.; २२/५/१५, ९:२५ AM
rhhardin म्हणाले...: When a town with rental housing annexes surrounding territory, the roads in the surrounding territory disintegrate.

The town voters prefer their programs to paving roads they never use, but they like the tax revenue from the annexation.

So my store bike route is longer to avoid direct roads with potholes in them.

In short, distance is not the only thing to consider.; २२/५/१५, ९:४० AM
MadisonMan म्हणाले...: Who in their right mind is going to take this trip, anyway?

The whole thing is clickbait and I am sorry to have succumbed.

I did like the link at the story from the person who took his kids to visit all the County Seats/Courthouses of Colorado. That's something that is a better goal -- get to know your own state. I don't think I've ever been in Oconto County (or even Door County!); २२/५/१५, ९:५७ AM
George Grady म्हणाले...: The number of routes they give is 2,500, not 25,000. And, as Clyde points out, it should be 2450.

Actually, it should be only 1225, since the distance should be (essentially) the same regardless of which direction you go.; २२/५/१५, ९:५८ AM
Michael K म्हणाले...: A nice road trip is a week in a motor home in Alaska. I did it with my kids 25 years ago and suggested it for the grandkids this summer but they are probably a couple of years too young. Not sure I'll be around when the time is right.; २२/५/१५, १०:०९ AM
Jaq म्हणाले...: Actually, it should be only 1225, ...

Not to mention that a simple bounding box twice the size of, say, Texas, of latitude and longitude for each location could probably remove hundreds of absurd candidate routes. Did they *really* need to know the exact distance to Yellowstone from the Statue of Liberty?; २२/५/१५, १०:३९ AM
Jason म्हणाले...: Start with the "Eight Queens" problem. Then work your way up.; २२/५/१५, १०:५९ AM
KLDAVIS म्हणाले...: The solution can't be optimal. It drives through my home town (a place that couldn't even qualify as the middle of nowhere in Montana), which is inexcusable.; २२/५/१५, ३:२९ PM
अनामित म्हणाले...: We did a similar sort of road trip last fall. Left Upstate New York and took the northern route (sort of) to Montana, and then down towards San Clemente, CA. Came back the southern route to TN for a wedding, and then back home. Had some time and location constraints, as well as hotel room constraints. Took 7 weeks and 10,000 miles.

Saw IU, the Mustard Museum, Lake Superior, the Corn Palace, Mt Rushmore, Custer's Last Stand, Glacier NP, National Bison
Range, Yellowstone NP, Grand Tetons NP, Jackson Hole, Bryce Canyon NP, and Zion NP.

Trip back was less exciting--saw Lake Mead, Boulder Dam (now called Hoover Dam), the Grand Canyon NP, the Codetalker Museum in the Navajo Nation, Durango, the Aztec Ruins, Taos, NM, the Alamo and the Riverwalk, Lafayette, LA, Mississippi Gulf Coast (Pass Christian), Mobile, Chattanooga, Pigeon Forge, TN and then home.

We now know what we want to see more of, and it's all out west.; २२/५/१५, ४:२० PM
readering म्हणाले...: What--2 versions of the road trip and neither stops in Southern California?; २२/५/१५, ५:०१ PM
Carol म्हणाले...: Tim, couldn't one visit the home of Calvin Coolidge? Isn't there a monument of some sort there?

Seemed like it would be a pretty area.; २२/५/१५, ५:०३ PM
Largo म्हणाले...: Not just a hard road trip -- an NP-hard road trip!; २३/५/१५, ३:५४ AM