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

Uniform cost search (UCS) is an uninformed search function that always expands the lowest-cost node next in a weighted graph. It uses a priority queue.

If it encounters a node it has already discovered and the new path to it is cheaper, it updates it with the lower cost in the queue.

The goal node is only checked when it is popped from the queue, which ensures that the cheapest path to the goal is found. Thus, UCS is complete and optimal (as long as all step-costs $\ge 0$).

UCS has the trade-off of being expensive:

Time Complexity	Space Complexity
$O(b^{1+[C^{\ast }/ϵ]})$	$O(b^{1+[C^{\ast }/ϵ]})$
$[C^{\ast }/ϵ]$ is the maximum amount of steps and $b$ is the branching factor. Alternatively, the time/space complexity can be described as $n$, where $n$ is the number of tree nodes with cost less than optimum.

---

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

Time Complexity	Space Complexity
$O(b^d)$	$O(bd)$

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)

Time Complexity	Space Complexity
$O(b^{d/2})$	$O(b^{d/2})$

---

CITS3011 - Lecture 3