Heuristic search

From Glossary

Jump to: navigation, search

In mathematical programming, this is any (purposeful) search procedure to seek a solution to a global optimization problem, notably to combinatorial programs. In AI, this is a (partially) informed search (vs. blind search), using a heuristic function for guidance.

Two types of (blind) search methods are:

  1. Breadth-first: expanding a node of least depth;
  2. Depth-first: expanding a node of greatest depth (requiring backtracking).
(See branch and bound.)

A specific class of local heuristic search algorithms is the greedy algorithm. Another type is the 1-Opt for the TSP.

Here are heuristic search strategies that are based on some biological metaphor:

  1. Ant colony optimization, based on how ants solve problems;
  2. Genetic algorithm, based on genetics and evolution;
  3. Neural networks, based on how the brain functions;
  4. Simulated annealing, based on thermodynamics;
  5. Tabu search, based on memory-response;
  6. Target analysis, based on learning.

Personal tools