State Space Search

the basic algorithm

CIS347

The basics of implementing state space search are fairly simple. Of course, applying the technique to specific problems can be quite complicated.

Basic Steps

w Start

v Get initial state

v Get goal state

v Initialize global variables

w The basic search loop

v Choose next node

X Depending on how search information is organized, this will usually be the

node at the head of the list of nodes waiting to be expanded (nodelist).

v Check to see if it is the goal node

X If it is, return the solution that was produced during the search process.

X Otherwise, continue . . .

v Expand the node, placing the resulting nodes onto nodelist.

X To expand a node,

Y Take all actions available

Y Each will result in a new state

Y Create a node for each state

Y If nodelist is being ordered, place new nodes onto nodelist according to the

ordering principle in effect.

Y Note: if a "filtering process" is being used, apply it at this point.