# Exhaustive Search

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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).