Uninformed Search
AIMA 3.3-3.4; Appendix A.1
CMPSC 442
Week 2, Meeting 7, Segment 2 of 4: Tree versus Graph
Search
Dilemma: Repeated States, or Redundant Paths
Paths with repeated states are non-optimal: see slides 29-30 of Wk 2, Mtg
6; Arad appears at root and at depth 2 of Romanian map navigation
Three solutions
● Update a list of reached/visited states: practical when the set of all
states fits easily in memory (aka graph search)
● Ignore: practical when likelihood of revisiting a state is very low
(tree-like search)
● Compromise and check for cycles for limited number of steps (parent,
grandparent): keeps memory needs to constant time
13Tree Search vs. Graph Search
Best First Search: Example of Graph Search
14Tree Search vs. Graph Search
See AIMA Appendix B.2 for Explanation of
Pseudo Code
● Starts with the problem definition problem
● And an evaluation function f
Best First Search: Example of Graph Search
15Tree Search vs. Graph Search
See AIMA Appendix B.2 for Explanation of
Pseudo Code
● Initialize node to start state
● Initialize frontier to a queue containing node
● Initialize reached to, e.g., a Python dict
Best First Search: Example of Graph Search
16Tree Search vs. Graph Search
See AIMA Appendix B.2 for Explanation of
Pseudo Code
● A while loop continues as long as frontier is non-empty
● Pop the first node on frontier and check if the next node
contains the goal state
Best First Search: Example of Graph Search
17Tree Search vs. Graph Search
See AIMA Appendix B.2 for Explanation of
Pseudo Code
● If the most recently popped node does not contain the
goal state, a for loop expands that node
○ Adds all its children to the frontier for each child
state not in reached unless there is a new way to
reach the state with a lower path cost
● Failure if the while loop reaches an empty frontier
Separation Property of Graph Search
● Graph search: no state occurs on more than one path
● During the search, states are in one of three disjoint subsets
○ States associated with expanded nodes
○ States associated with nodes in the frontier (reached but not expanded)
○ States associated with nodes that have not been reached
18Tree Search vs. Graph Search
Pseudo Code Comparison
19Tree Search vs. Graph Search
Graph search algorithm is the
same as tree search, with the
addition of the explored set