Page 30 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence

Notes Self Assessment

Fill in the blanks:
9. ......................... is an algorithm for navigating or looking for a tree, tree structure, or graph.
10. A ......................................... is a list of the vertices so that they were first visited by the depth-
first search algorithm.
11. A reverse postordering is the reverse of a postordering, which is defined a list of the
vertices in the ......................................... order of their previous visit.

2.5 Heuristic Search

Due to the momentary situation changes and new possibilities arising for further decisions
during the problem solving, new ramifications are needed. For this reason, problem solving the
AI is best represented with the help of a tree. It starts with a beginning condition and after each
decision follows a ramification. The final number of ramifications at the end of a tree can be very
high, if many steps are necessary for solving the problem. Therefore, empiric rules, so called
heuristics, were developed to facilitate the search for the most likely ramifications and also to
limit them.
Heuristic Search resolve multifaceted problems competently, it is essential to negotiate the
needs of the movability and systematically. A control structure has to be constructed that no
longer assures the best solution, but that will almost always discover a very superior answer.
Such a method is said to be heuristic (rule of thumb). A heuristic search enhances competently
the search process, but sacrifices the claims of wholeness. But they perk up the class of the paths
that are discovered.

!
Caution Using good heuristics we can obtain good solutions to tough problems, like the
traveling salesman problem.

Self Assessment

Fill in the blank:
12. A ................................ search enhances competently the search process, but sacrifices the
claims of wholeness.

2.6 Problem & Production System Characteristics and Design of
Search Programs Issues

2.6.1 Problem Characteristics

Heuristic search is an extremely common method pertinent to a large class of problem. It
involves numerous techniques. In order to select a appropriate method, it is essential to examine
the problem concerning the following deliberations.

1. Is the problem decomposable?
A very great and compound problem can be simply solved if it can be wrecked into
smaller problems and recursion could be used. Presume that we want to solve.

24 LOVELY PROFESSIONAL UNIVERSITY