local search

Local Search is a meta heuristic that is commonly used for solving computationally hard problem such as the traveling salesman problem (TSP). Suppose given a (typically very large) space of candidate solutions of a given problem instance and a neighbourhood relation on this space. The basic principle underlying local search is to start from an initial candidate solution and then, iteratively, to make moves from one candidate solution to another of the candidate solution from its direct neighbourhood. The moves are based on local information, and continue until a termination condition is met. A typical example of a local search method is the 2-opt algorithm for the TSP. Local search algorithms are widely applied to numerous hard computational problems, including problems from computer science (particularly artificial intelligence), mathematics, operations research, engineering, and bioinformatics.

Word Browser