science and technology 科技: The ultimate American road trip, according to science

2015年3月14日星期六

The ultimate American road trip, according to science

The man behind the 'Where's Waldo' algorithm has created a road trip route revealing the best way to visit 50 US states. The resulting 13,699-mile route would take 9.33 days of non-stop driving if you had the road to yourself

HOW WAS IT DONE?

Rather than looking at every possible solution, Randy Olsen used something known as a 'genetic algorithms' which starts with just a few random solutions.

It then manipulates these solutions, while trying something slightly different each time, until it finds one that it can't improve on.

The resulting 13,699-mile route would take 9.33 days of non-stop driving if you had the road to yourself.

In his blog, Mr Olson explains how he used information from Google Maps API and wrote code to discover the optimum distance to drive to all 50 landmarks.

This was the same code he had previously created to discover Waldo – or Wally in the UK.

'With 50 landmarks to put in order, we would have to exhaustively evaluate 3 x 1064 possible routes to find the shortest one,' he wrote.

'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.

'This complication is why Google Map's route optimisation service only optimises routes of up 10 waypoints.'

Rather than looking at every possible solution, he used something known as a 'genetic algorithms' which starts with just a few random solutions.

It then manipulates these solutions, while trying something slightly different each time, until it finds one that it can't improve on.