![]() ![]() I've included a visualization of a genetic algorithm solving a similar routing problem below. Instead of exhaustively looking at every possible solution, genetic algorithms start with a handful of random solutions and continually tinkers with these solutions - always trying something slightly different from the current solutions and keeping the best ones - until they can't find a better solution any more. If we're willing to accept that we don't need the absolute best route between all of the landmarks, then we can turn to smarter techniques such as genetic algorithms to find a solution that's good enough for our purposes. ![]() Thankfully, the traveling salesman problem has been well-studied over the years and there are many ways for us to solve it in a reasonable amount of time. The traveling salesman problem is so notoriously difficult to solve that even xkcd poked fun at it:Ĭlearly, we need a smarter solution if we want to take this epic road trip in our lifetime. This complication is why Google Map's route optimization service only optimizes routes of up 10 waypoints, and the best free route optimization service only optimizes 20 waypoints unless you pay them a lot of money to dedicate some bigger computers to it. 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 10 52 years - long after the Sun has entered its red giant phase and devoured the Earth. With 50 landmarks to put in order, we would have to exhaustively evaluate 3 x 10 64 possible routes to find the shortest one. If you read my Where's Waldo article, you're already aware of how difficult it can be to solve route optimization problems like this one. This means finding the route that backtracks as little as possible, which is especially difficult when visiting Florida and the Northeast. Now with the 2,450 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. Thankfully, the Google Maps API makes this information freely available, so all it took was a short Python script to calculate the distance and time driven for all 2,450 routes between the 50 landmarks. Except this time, we needed to look up 2,450 directions to get the "true" distance between all 50 landmarks - a monumental task if we had to do it by hand. If you've ever used Google Maps to get the directions between two addresses, that's basically what we had to do here. Since we can't just drive a straight line between every landmark - driving by car has this pesky limitation of having to stay on roads - we needed to find the shortest route by road between every landmark. With the list of landmarks in hand, the next step was to find the "true" distance between all of the landmarks by car. Image credit: Dean Franklin Computing the optimal road trip across the U.S. All that was left was to figure out the path that would minimize our time spent driving and maximize our time spent enjoying the landmarks. ![]() The result was an epic itinerary with a mix of inner city exploration, must-see historical sites, and beautiful natural landscapes. Tracy wrote about that process on Discovery News here. landmarks - one in each state excluding Alaska/Hawaii and including D.C., and two in California. With those objectives in mind, Tracy compiled a list of 50 major U.S. The trip must be taken by car and never leave the U.S.The trip would only make stops at National Natural Landmarks, National Historic Sites, National Parks, or National Monuments.The trip must make at least one stop in all 48 states in the contiguous U.S.To stand a chance at making an interesting road trip, Tracy and I laid out a few rules from the beginning: is, it's especially difficult to make a road trip that will appeal to everyone. One of the hardest parts of planning a road trip is deciding where to stop along the way. Note: If you're not interested in the technical details of the project, skip down to the Road trip stopping at major U.S. state has long been on my bucket list, so I jumped on the opportunity and opened up my machine learning tool box for another quick weekend project. Last week, Tracy Staedter proposed an interesting idea to me: Why not use the same algorithm from my Where's Waldo article to compute the optimal road trip across every state in the U.S.? Visiting every U.S.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |