Searching for Solutions

Question 1

searching

Answer 1

just thinking about trying each possible action in every possible state and stopping early if you find the goal

Question 2

problem state

Answer 2

data structure describing the configuration of all the elements of the problem that can change or be affected by actions in the problem environment

Question 3

What are vertices in the state space?

Answer 3

problem states

Question 4

search node

Answer 4

data structure containing search info, including (but not only) a problem state

Question 5

node expansion

Answer 5

generating new legal search nodes from a parent node

Question 6

frontier

Answer 6

a collection of dearch nodes to be explored

Question 7

search strategy

Answer 7

the rule that determines which node to remove from the frontier

Question 8

search tree / search space

Answer 8

a tree of search nodes whose exact shape depends on both the state transition model and the search strategy

Question 9

graph search

Answer 9

modification to tree search: we store all the states we have previously seen and check for repeats when expanding nodes

Question 10

partial graph search

Answer 10

• each search node stores a reference to its parent
• we check all ancestors for repeats when expanding a node

Question 11

How to determine if you should use graph search?

Answer 11

• calculate the number of possible states
• if it is small: repeat states are likely, graph search could save a lot of work
• if it is big: repeat states are unlikely, graph search adds cost for little gain