Exhaustive Search

It can be used to reduce the search space. Randomization can be applied to improve runtimes, though there is often little-to-no computational benefit to doing this.

Exhaustive searches are also known as backtracking algorithms, though not all backtracking algorithms are exhaustive. The algorithm looks for every possible way to search for a solution. It is usually combined with pruning to reduce the number of items to search for. It is also known as Backtracking.

A generalized pseudocode algorithm for the exhaustive search can be defined thusly:

backtrack(int sol, int depth)
{
   if (issolution(sol))
      printsolution(sol)
   else{
      solgenerated = generatesolution()
      backtrack(solgenerated, depth+1)
   }
}

The exhaustive algorithm for sorting an array of integers in ascending order can be defined thusly (in prolog syntax):

/* is a the list sorted?*/
isSorted([]).          /*an empty list is sorted*/
isSorted([_|[]]).      /*a list of one element is sorted*/
isSorted([[First|Second]|Rest]) :- First<=Second , isSorted([second|rest]).

/*is one list a permutation of another?*/
permutation([],[]).
permutation([A],[A]).
permutation(List1,[List2H|List2T]) :- sameLength(List1,[List2H|List2T]),
        member(List2H,List1),removed(List1,List2H,Others),permutation(Others,List2T)

/* support functions */
sameLength([],[]).
sameLength([_|Tail1],[_|Tail2]) :- sameLength(Tail1,Tail2).
removed([Head|Tail],Head,Tail).
removed([Head|Tail],X,[Head|Tail2]) :- removed(Tail,X,Tail2).

/* sample call */
?- isSorted([5,9,6,2,1,3,4,8,7,0],X).  /* sort the array and put the result in X */

    X = [0,1,2,3,4,5,6,7,8,9]          /* sample output */

This sort produces a permutation of the array, checks to see if it is sorted, and continues is produced, and if it is incorrect the algorithm backtracks and tries a different permutation

The linear search algorithm is another example of an exhaustive algorithm.