Exploiting commonality in heuristic search

点击翻译按钮获取中文摘要

Heuristic search techniques are systematic methods to explore a large set of possible solutions for the one solution that best achieves some objective. For example, there are many ways to arrange guests at a wedding reception, but it can still take newlyweds a long time to find one that they can both agree on. For this problem, most couples would use a form of iterative improvement - start with one solution, make changes to it to create a new solution, make additional changes, etc, until a final acceptable solution is found. Heuristic search techniques such as genetic algorithms, simulated annealing, tabu search, etc are all methods that perform iterative improvement. Specifically, these search techniques all employ "change operators" (methods to create new solutions) and "control strategies" (methods to control which new solutions are accepted). For example, you might suggest swapping two tables, and your partner might say "no, that's worse" or "yes, but this still needs to be addressed".