search (slides3)

Question 1

tree search basic idea

Answer 1

offline, simulated exploration of state space by generating successors of already explored states (a.k.a ~expanding states)

Question 2

tree-search general pseudocode

Answer 2

function Tree-Search(problem, strategy)
returns a solution, or failure
initialize the search tree using the initial state of problem
loop do
-if there are no candidates for expansion then   return failure

• choose a leaf node for expansion according to strategy
• if the node contains a goal state then return the corresponding solution
• else expand the node and add the resulting nodes to the search tree

Question 3

state

Answer 3

representation of physical configuration

Question 4

node

Answer 4

data structure constituting part of a search tree includes state, parent node, action, path cost g(x), sometimes the depth

Question 5

expand function

Answer 5

creates new nodes, filling in the various fields and using the Successor Function of the problem to create the corresponding states
-frontier is usually organized as FIFO, LIFO, or Priority Queue

Question 6

general tree search implementation (Tree-search)

Answer 6

function Tree-Search(problem, fringe) returns a solution, or failure
  fringe<-- InsertAll(Expand(node,problem), fringe)

Question 7

general treesearch implementation (Expand)

Answer 7

function Expand(node, problem) returns a set of nodes
successors<–Depth[node] + 1
add s to successors
return successors