Uniformed Search

Search

Searching through a state space involves the following:

• A set of states

• Operators and their costs

• Start state

• A test to check for goal state

We will now outline the basic search algorithm, and then consider various variations of

this algorithm.

The basic search algorithm

Let L be a list containing the initial state (L= the fringe)

Loop

if L is empty return failure

Node   select (L)

if Node is a goal

then return Node

(the path from initial state to Node)

else generate all successors of Node, and

merge the newly generated states into L

End Loop

We need to denote the states that have been generated. We will call these as nodes. The

data structure for a node will keep track of not only the state, but also the parent state or

the operator that was applied to get this state.

 In addition the search algorithm maintains a list of nodes called the fringe. The fringe keeps track of the nodes that have been generated but are yet to be explored. The fringe represents the frontier of the search tree generated.

The basic search algorithm has been described above.

Initially, the fringe contains a single node corresponding to the start state. In this version

we use only the OPEN list or fringe. The algorithm always picks the first node from

fringe for expansion. If the node contains a goal state, the path to the goal is returned. The

path corresponding to a goal node can be found by following the parent pointers.

Otherwise all the successor nodes are generated and they are added to the fringe.

The successors of the current expanded node are put in fringe. We will soon see that the

order in which the successors are put in fringe will determine the property of the search

algorithm.

Evaluating Search strategies

We will look at various search strategies and evaluate their problem solving performance.

What are the characteristics of the different search algorithms and what is their

efficiency? We will look at the following three factors to measure this.

1. Completeness: Is the strategy guaranteed to find a solution if one exists?

2. Optimality: Does the solution have low cost or the minimal cost?

3. What is the search cost associated with the time and memory required to find

a solution?

a. Time complexity: Time taken (number of nodes expanded) (worst or

average case) to find a solution.

b. Space complexity: Space used by the algorithm measured in terms of

the maximum size of fringe