Local search

Definition

Local search is a general approach for finding points of local extremum of a function through an iterative algorithm. The idea is to start with a particular guess and then improve it iteratively. It is an anytime algorithm, because at any intermediate stage, we can return the best guess so far and terminate the algorithm (albeit we hope that the more iterations we manage, the better our result).