Page 50 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence Manish Kumar, Lovely Professional University

Notes Unit 4: Heuristic Search Techniques

CONTENTS
Objectives
Introduction

4.1 Heuristic Search Techniques
4.2 Generate and Test
4.3 Hill Climbing

4.4 Best First Search
4.4.1 Best First Search Algorithm
4.4.2 The A* Algorithm
4.4.3 Greedy Best-first Search (GBFS)
4.5 Constraint Satisfaction

4.6 Means-ends Analysis
4.7 Summary
4.8 Keywords

4.9 Review Questions
4.10 Further Readings

Objectives

After studying this unit, you will be able to:
 Understand the various heuristic search techniques
 Discuss the generate and test, hill climbing, best first search
 Discuss the constraint satisfaction and mean-end analysis

Introduction

Most of the problems are too multifaceted to be solvable by straight techniques. They have to be
solved only by appropriate heuristic search techniques. However the heuristic techniques can
be illustrated separately, they are domain particular. They are known as “ Weak Methods”, as
they are susceptible to combinatorial explosion. Nonetheless, they give the frame work into
which domain specific knowledge can be positioned.

Each search process can be observed as a traversal of a directed graph, in which the nodes
symbolize problem states and the arcs stand for relationships among states. The search process
must locate a path through this graph, beginning at an initial state and ending in one or more
final states. The issues discussed in the unit have to be considered before performing a search.

4.1 Heuristic Search Techniques

Heuristic techniques are known as weak methods, as they are susceptible to combinatorial
explosion. Still these techniques persist to offer framework into which domain specific knowledge

44 LOVELY PROFESSIONAL UNIVERSITY