UNIT II

Searching Techniques

Introduction

We have outlined the different types of search strategies. In the earlier chapter we have

looked at different blind search strategies. Uninformed search methods lack problemspecific

knowledge. Such methods are prohibitively inefficient in many cases. Using

problem-specific knowledge can dramatically improve the search speed. In this chapter

we will study some informed search algorithms that use problem specific heuristics.

Review of different Search Strategies

1. Blind Search

a) Depth first search

b) Breadth first search

c) Iterative deepening search

d) Bidirectional search

2. Informed Search

Informed Search and Exploration

Graph Search Algorithm

We begin by outlining the general graph search algorithm below.

Graph search algorithm

Review of Uniform-Cost Search (UCS)

We will now review a variation of breadth first search we considered before, namely

Uniform cost search.

To review, in uniform cost search we enqueue nodes by path cost.

Let g(n) = cost of the path from the start node to the current node n.

Version 1 CSE IIT, Kharagpur

The algorithm sorts nodes by increasing value of g, and expands the lowest cost node of

the fringe.

Properties of Uniform Cost Search

• Complete

• Optimal/Admissible

• Exponential time and space complexity, O(bd)

The UCS algorithm uses the value of g(n) to select the order of node expansion. We will

now introduce informed search or heuristic search that uses problem specific heuristic

information. The heuristic will be used to select the order of node expansion.