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.
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
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.