Page 65 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 4: Heuristic Search Techniques

Greedy Best-first Search (GBFS): Develop node closest to the goal; choose path with lowest h(n) Notes
and evaluate nodes by using heuristic function – that is, f(n) = h(n).
Heuristic Techniques: Heuristic techniques are known as weak methods, as they are susceptible
to combinatorial explosion.
Hill Climbing Technique: In this, a feedback is utilized here to decide on the course of movement
in the search space. In the depth-first search, the test function will just accept or reject a solution.
Means-ends Analysis: This process centers about locating the difference among current state and
goal state.

4.9 Review Questions

1. What are Heuristic techniques? Illustrate why the Heuristic techniques are considered as
weak methods.
2. Enlighten various properties of heuristic process.

3. Explain the steps used in Generate and Test technique.
4. Depict the working of Hill Climbing technique.
5. Best First Search is a amalgamation of depth first and breadth first searches. Comment.

6. Make distinction between A* Algorithm and Greedy Best-first Search (GBFS) algorithm.
7. Illustrate the process of solving constraint satisfaction problems.
8. Explain the functioning of Means-ends Analysis technique with examples.
9. Discuss the steps used in solving Means-ends Analysis problem.
10. Explain the advantages and disadvantage of A* algorithm.

Answers: Self Assessment

1. weak 2. Heuristic
3. generate and Test 4. problem space
5. hill climbing 6. plateau
7. ridge 8. Best First Search

9. OPEN 10. CLOSED
11. A* 12. constraint satisfaction
13. search 14. means-ends analysis
15. human planning

4.10 Further Readings

Books Antonelli, D. 1983. The application of artificial intelligence to a maintenance and diagnostic
information system (MDIS). Proceedings of the Joint Services Workshop on Artificial
Intelligence in Maintenance. Boulder, CO.

LOVELY PROFESSIONAL UNIVERSITY 59