X hits on this document

Powerpoint document

Lecture 2: Problem Solving using State Space Representations - page 44 / 49

126 views

0 shares

0 downloads

0 comments

44 / 49

Slide Set 2: State-Space Search 44

ICS 271, Fall 2007: Professor Padhraic Smyth

State Spaces versus Search Trees

State Space

Set of valid states for a problem

Linked by operators

e.g., 20 valid states (cities) in the Romanian travel problem

Search Tree

Root node = initial state

Child nodes = states that can be visited from parent

Note that the depth of the tree can be infinite

E.g., via repeated states

Partial search tree

Portion of tree that has been expanded so far

Fringe

Leaves of partial search tree, candidates for expansion

   Search trees = data structure to search state-space

Document info
Document views126
Page views126
Page last viewedThu Dec 08 08:41:52 UTC 2016
Pages49
Paragraphs815
Words3134

Comments