Search

Terms: (for definitions & discussions look here)

Search -

State-Space Search

Components::

States -

Initial state(s) -

Goal state(s) -

Actions -

Operator -

State space –

nodes

arcs.

Path –

Goal test -

Path cost function - denoted g.

Solution -

Branching factor -

Effective branching factor -

fringe or frontier -

Measuring Problem Solving Performance::

Effectiveness of search is measured in three ways:

1. Does it find solution?

2. Is it a good solution (low cost path)

3. What is the search cost?

Total cost - sum of path cost and search cost.

Abstraction -

Generating Action Sequences

generating a new set of states

expanding the state.

Search strategy –

Search tree –

Root –

Leaf nodes –

Note: search tree <> state space

Representing a node in the search tree

w state -

w parent -

w action -

w depth -

w path cost -

Criteria for evaluating search strategies

w Completeness -

w Time complexity -

w Space complexity -

w Optimality -

Basic categories of search

w Uninformed search –

blind search.

w Informed search –

heuristic search.