CITS3011 - Lecture 2

← Back to Home

CITS3011 - Lecture 1
Uninformed Search - Slides

State Space Graph

• State space graph is a formal representation of a search problem

  • Nodes are states
  • Edges are successor functions

  

Search Tree

• Search tree is a tree of plans, searching on a state space graph
  • Represents paths in the state space graph
  • In the tree, each state can appear multiple times

• Nodes represent states

  • Starting state is the root
  • Children are from the successor function

• Path cost is the accumulative cost along the path

See more: Trees

Uniformed Search Strategies

Breadth-First Search

• Breadth-First Search (BFS) is a traversal technique that explores rooted trees and graphs layer by layer
  • Vertices are separated in different levels
  • Begins at a starting vertex

As BFS explores, edges get classified:

• Discovery edge $-$ leads to an unexplored vertex
• Cross edge $-$ connects two already-visited vertices at the same or adjacent level

---

Link to original

Uniform Cost Search

• Expand the lowest-cost node next

  

Analysis:

• Complete: yes, if all step-costs $\ge 0$
• Optimal: as above
• Time: $O(n)$, where $n$ is # of nodes with cost less than optimum
• Space: as above

---

Depth-First Search

• Depth-first search (DFS) is a traversal technique used commonly for rooted trees and graphs
  • It explores as deeply as possible before backtracking
  • For rooted trees, it starts at the root and traverses to a leaf

As DFS explores, edges get classified:

• Discovery edge $-$ leads to an unexplored vertex
  • Forms the DFS spanning tree
• Back edge $-$ leads to an already-visited vertex
  • Indicates a cycle in the graph

DFS of a graph $G$, must start at a vertex, known as $v$

• If we encounters every vertex in the graph, then $G$ is a connected graph
• Otherwise, DFS must be called for every connected component of $G$

---

Link to original

Depth-Limited Search

• Variant of depth-first search, but with a cut-off depth
• Works well when you have limited resources

Iterative Deepening Depth-First Search

• Repeated depth-limited search, with increasing cut-offs
• Generally, a good default search algorithm

Bi-Directional Search

• Search from both ends (initial state and goal state)
• Usually expands many fewer modes than unidirectional
• Raises many other difficulties (e.g. goal state may be unknown)

---