Computer Science 456: Artificial Intelligence and Expert Systems
Unit 4: Heuristic Search Algorithms
Heuristics play a fundamental role in the AI problem-solving approach. As AI has a focus on problems that are not suitable for algorithmic solutions, heuristics are usually used in order to determine the plan or choose the path that most likely lead to an acceptable solution. This unit explains and illustrates the use of heuristics to search the state space of a problem in order to come up with an acceptable solution. The key algorithms in this domain such as the hill-climbing, A*, and minimax are analyzed, and related issues such as admissibility, monotonicity, and complexity discussed.
Activities
Assignment 2
Complete Assignment 2, and submit it to your tutor for evaluation and feedback.
Section 4.1: Hill-climbing, Dynamic Programming, and Best-first Search
This section introduces the concept of heuristic measure and presents the main AI algorithms that use heuristics to search the state space. The following algorithms implement a heuristic search: hill-climbing, dynamic programming, and best-first search.
Learning Objectives
- Discuss the concept of heuristic measure.
- Develop AI solutions for problem solving using heuristic strategies.
- Implement heuristic strategies using the presented algorithms.
Key Terms
heuristic measure, hill-climbing algorithm, dynamic programming, forward stage, backward stage, best-first search, confidence measure, certainty factor
Readings
Read the sections “Introduction,” “Hill Climbing and Dynamic Programming,” and “The Best-First Search Algorithm” from Chapter 4, Heuristic Search.
Tasks
Practice the following exercises from Chapter 4 of the textbook:
- Exercises 1, 2, and 3. You may want to use the Personal Workspace wiki on the course home page and/or share your observations with classmates in the COMP 456 General Discussion forum.
Section 4.2: Heuristic Search Issues and Applications
This section presents some of the theoretical issues related to use of heuristic search algorithms such as admissibility and monotonicity measures. It also examines the complexity issue in heuristic search algorithms and discusses its role in intelligent problem solving. Using application examples, this section discusses other techniques used for heuristic search such as minimaxing and alpha–beta pruning.
Learning Objectives
- Analyze the issues related to heuristic search.
- Compare the heuristic search algorithms using different measures such as admissibility, monotonicity, and complexity.
- Outline the use of techniques such as minimaxing and alpha–beta pruning.
- Present some application examples for heuristic search.
Key Terms
admissibility, monotonicity, informedness, complexity, minimaxing, alpha–beta pruning
Readings
Read the sections “Admissibility, Monotonicity, and Informedness,” “Using Heuristics in Games,” and “Complexity Issues” from Chapter 4, Heuristic Search.
Tasks
Practice the following exercises from Chapter 4 of the textbook:
- Exercises 5, 7, 13, and 14. You may want to use the Personal Workspace wiki on the course home page and/or share your observations with classmates in the COMP 456 General Discussion forum.