Uniform Cost Search

Published
Completeness - Complete if the branching factor is finite.
Optimality - Optimal if the costs of all actions are positive non-zero values.
Time Complexity - O(b1 + (C* / Ɛ))
Space Complexity - O(b1 + (C* / Ɛ))

Visual Example

Current Node Frontier
A0 B1, C2
B1 C2, D2, E4
C2 D2, E3, F6
D2 E3, F6
E3 F6
Goal Node Found

The subscript number associated with each node, for example C2, is the cost of the path from the root node A to node C.

  1. We start from the root node A0.
  2. We check to see if A0 is a goal node. It's not, so we add it's children, nodes B1 and C2, to the frontier.
  3. We remove node B1 from the frontier and check if it's a goal node. It's not, so we add it's children, nodes D2 and E4, to the frontier.
    Because C2 and D2 have the same cost, we sort them alphabetically in the frontier.
  4. We remove node C2 from the frontier and check if it's a goal node. It's not, so we add it's children, nodes E3 and F6, to the frontier.
    Although E4 was already on the frontier, E3 has a lower path cost, so it replaces E4.
  5. We remove node D2 from the frontier and check if it's a goal node. It's not, so we continue.
  6. We remove node E3 from the frontier and check if it's a goal node. It is, so we're done.

Algorithm Notes


Return to Articles