Exhaustive Search

From Algorithmist
Jump to navigation Jump to 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.