The Stack Overflow podcast is back! Listen to an interview with our new CEO.

For questions involving search algorithms and their use in artificial intelligence

Searching is a technique for problem solving commonly used in AI systems.

The searching may be conducted in a discrete solution space, whereby the permutations for possible discrete solutions are investigated in some way to determine a good solution based on some stated criteria for selection. Alternately the search may be conducted in a continuous search space, whereby the goal of the search is to converge on an optimum. The space may be a hybrid of continuous and discrete dimensions.

The acceptable reliability and accuracy of the search are elements of the search requirements. For instance, in the case of a discrete solution space, there may be an acceptable number of incorrect solutions from among a large set of problems solved. There may be answers that in some way are defined as close enough to correct. A typical example is when a certain percentage of error is allowed in IEEE floating point output of the search in continuous dimensions.

The problem may be static in that the problem does not change during the course of the search or dynamic as in the case of control systems for robotics or other kinds of interactive systems.

Early search AI work was targeted at gaming, using cames ranging in complexity from Tic-tac-toe and checkers to Sudoku, Chess, and Go.

Searching algorithms can be compared for effectiveness based on any set of criteria. Common evaluation criteria include these.

  1. Accuracy
  2. Reliability
  3. Speed
  4. Computing resource utilization

Search algorithms can be informed or uninformed, meaning that the search may be guided by information known about the probability distribution of success within the search space or not.

Examples of fundamental tree searches taught in undergraduate computer science curricula are breadth first search, depth first search, best first search. There are many algorithmic approaches, ways to parallelism searching to improve speed, architectures to support searching, and variants of these.

history | excerpt history