07-02-2013, 10:26 AM
Heuristic search
Heuristic search.pptx (Size: 369.13 KB / Downloads: 27)
We normally apply heuristic in the situation
The problem does not have any exact solution because of the inherent ambiguity in the problem
A problem having exact solution but cost of finding solution is very high
In blind search only production rules are defined, besides production rule any other information is not included
The additional information or clue is called heuristics
The additional information reduces the search space and solution of the problem obtained efficiently
The additional information are given in terms of heuristic function
The additional task domain knowledge is heuristic knowledge
Heuristic knowledge is obtained byconsulting experts of concerned fields
Expert of a particular field gain heuristic knowledge with experience
Generate and test
As the name suggest this approach simply to generate the result and test whether it is a desired solution to the given problem
Algorithm
Generate a possible solution
Test to see whether it is a solution
If solution has been found quit and return to step1
Best First Search
It is a general heuristic based search technique
in the graph of the problem presentation, one evaluation function is attached with every node
The value of evaluation function may depend upon cost or distance of current node from goal node
Algorithm for best First search
Put the initial node on a list say open
If open=empty or open=goal terminate search else
Remove the first node from open
If a=goal terminate the search with success else
Generate all successor of a node a and send node ‘a’ to a list called CLOSED. Find out the value of the heuristic function to all nodes .Sort all children generated so far on the basis of their utility value. select the node of minimum heuristic value for their expansion
Go back to step 2
A* Algorihm
Place the starting node on ‘s’ on open list
If open is empty ,stop and return failure
Remove from open node n that has the smallest value of f*(n).if node n is a goal node,return success and stop otherwise
Expand n generating all of its successors n’ and place n on closed. For every successor n’ if n’ is not on open, attach a back pointer to n. compute f*(n) and place it on open