Page 57 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 4: Heuristic Search Techniques

Notes

Notes
1. Like DFS, GBFS follows a single path to the objective, but “backtracks” when it hits
a dead end.

2. Like DFS it is not most favorable and it is incomplete.
Self Assessment

Fill in the blanks:
8. ......................................... is a amalgamation of depth first and breadth first searches.
9. ......................................... is a precedence queue of nodes that have been evaluated by the
heuristic function but which have not yet been extended into successors.
10. ......................................... are nodes that have already been produced and these nodes must
be amassed since a graph is being used in partiality to a tree.
11. The Best First algorithm is an easy form of the .................................. algorithm.

4.5 Constraint Satisfaction

Many troubles in AI can be regarded as problems of constraint satisfaction, where the goal state
pleases a specified set of constraint.

!
Caution Constraint satisfaction problems can be solved by means of any of the search
approaches.
The common form of the constraint satisfaction procedure is as follows:
Until a whole solution is located or until all paths have led to lead ends, do
1. Choose an unexpanded node of the search graph.

2. Apply the constraint inference rules to the chosen node to generate all possible new
constraints.
3. If the set of constraints encloses a contradiction, then report that this path is a dead end.

4. If the set of constraints illustrates a total solution then report success.
5. If neither a constraint nor a complete solution has been located then apply the rules to
produce new partial solutions. Insert these partial solutions into the search graph.

Example: Consider the crypt arithmetic problems.
SEND
+ MORE
—————
MONEY
—————

LOVELY PROFESSIONAL UNIVERSITY 51