What do you do to find the optimal solution to a problem that has an overwhelmingly large amount of equally appealing solutions? Well, it turns out that mathematicians and computer scientists haven’t even really been able to answer the problem either.
In the book Combinatorial Optimization, Christos H. Papadimitriou admits that for most complex problems there is no easy way to find an optimal solution given a finite amount of computation time. He recommends Local Search as a good starting point.
Local Search is actually a very simple algorithm which humans have been using for years. It goes as follows:
- Start off with your best guess, if you have no best guess then start off with a set of random solutions
- Modify your initial solution set slightly. I.e. move about a small neighborhood of your initial solution set.
- If solution get’s better, keep on pursuing the direction you moved in, else try another neighboring solution.
- Keep proceding until a sufficiently optimal solution is found
Imagine the problem in this way, your friend told you he was going hiking next week, but didn’t tell you a day, time or location. 1 full week from now you’ve not heard from him, and are getting worried. You call in the search and rescue team but where to start? Colorado has thousands of trails.
Well, the best place to start is probably his house, then the 5 most frequently hiked or mentioned trails by your friend. After that, go with the most popular, then the most available to hike. If you haven’t found him at the initial places, then look at the trails closest to the ones just searched.
Good ol’ combinatorial optimization!