Article Preview
Top2. Local Search
Classical search algorithms explore the space of states systematically. This exploration is made by keeping one or more paths in memory and by recording the alternatives in each choice point. When a final state is found, the path, that is, the sequence of transitions, is considered as the solution of the problem. Nonetheless, in many problems, we are only interested in the found state, not properly in the path of transitions. For example, in job-shop scheduling, vehicle routing or telecommunications network optimization, we are only interested in the final state (a concrete disposition of the objects in the world), not in the way in which this state is achieved.
If the sequence of elementary transitions is not important, a good alternative to classical searching algorithms is local search. This type of search operates using a single state and its set of neighbors. It is not necessary to keep in memory how the current state has been obtained.
Since these algorithms do not systematically explore the states, they do not guarantee that a final state can be found, i.e., they are not complete. Nonetheless, they have two advantages that make them interesting in many situations:
- •
Only a little piece of information is stored, so very little memory (usually constant) is used.
- •
These algorithms can often find a reasonable solution in an extremely large space of states where classical algorithms are unsuitable.