Informed Search Strategies

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 problem-specific 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

Graph Search Algorithm: We begin by outlining the general graph search algorithm below.

1. Let fringe be a list containing the initial state
2. Let closed be initially empty
3. Loop if fringe is empty return failure Node 􀃅 remove-first (fringe)
4. if Node is a goal
5. then return the path from initial state to Node
6. else put Node in closed
7. generate all successors of Node S
8. for all nodes m in S
9. if m is not in fringe or closed
10. merge m into fringe
11. End Loop

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.

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.