Heuristic Search Techniques

Introduction:-
Many if the problems are too complex to be solvable by direct techniques. They have to be solved only by suitable heuristic search techniques. Though the heuristic techniques can be described independently, they are domain specific. They are called " Weak Methods", since they are vulnerable to combinatorial explosion. Even so, they provide the frame work into which domain specific knowledge can be placed.

Every search process can be viewed as a traversal of a directed graph, in which the nodes represent problem states and the arcs represent relationships between states. The search process must find a path through this graph, starting at an initial state and ending in one or more final states. The following issues have to be considered before going for a search.

Heuristic techniques are called weak methods, since they are vulnerable to combinatorial explosion. Even then these techniques continue to provide framework into which domain specific knowledge can be placed, either by hand or as a result of learning. The following are some general purpose control strategies (often called weak methods).

-Generate-and-test
-Hillclimbing
-Breadth-Firstsearch
-Depth-Firstsearch
-BestFirstSearch(A*search)
-Problemreduction(AO*search)
-Constraintsatisfaction
-Means-endsanalysis

A heuristic procedure, or heuristic, is defined as having the following properties.
1. It will usually find good, although not necessary optimum solutions.
2. It is faster and easier to implement than any known exact algorithm ( one which guarantees an optimum solution ).

In general, heuristic search improve the quality of the path that are exported. Using good heuristics we can hope to get good solutions to hard problems such as the traveling salesman problem in less than exponential time. There are some good general purpose heuristics that are useful in a wide variety of problems. It is also possible to construct special purpose heuristics to solve particular problems. For example, consider the traveling salesman problem.