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.