Tuesday, July 20, 2010

Heuristic Search Techniques.

Introduction:- Many of 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 combinational 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 Search Techniques.


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


- Hill climbing


- Breadth - First search


- Depth - First search


- Best First Search (A* search)


- Problem reduction(AO* search)


- Constraint satisfaction


- Means - ends analysis


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.

5 comments:

  1. could u know about chaining in heuristic search with reduce cost of function unit give me breaf details plz.


    ravi khatwal
    research scholar
    embedded system ,mlsu, udaipur

    ReplyDelete
  2. Breadth - First search


    - Depth - First search are not Heuristic Searches. They are Uninformed/Blind search techniques.

    ReplyDelete