Uniform Cost Search
Published
Completeness    Complete if the branching factor is finite. 
Optimality    Optimal if the costs of all actions are positive nonzero values. 
Time Complexity    O(b^{1 + (C* / Ɛ)}) 
Space Complexity    O(b^{1 + (C* / Ɛ)}) 
Visual Example

The subscript number associated with each node, for example C_{2}, is the cost of the path from the root node A to node C.
 We start from the root node A_{0}.
 We check to see if A_{0} is a goal node. It's not, so we add it's children, nodes B_{1} and C_{2}, to the frontier.

We remove node B_{1} from the frontier and check if it's a goal node. It's not, so we add it's children, nodes D_{2} and
E_{4}, to the frontier.
Because C_{2} and D_{2} have the same cost, we sort them alphabetically in the frontier. 
We remove node C_{2} from the frontier and check if it's a goal node. It's not, so we add it's children, nodes E_{3} and
F_{6}, to the frontier.
Although E_{4} was already on the frontier, E_{3} has a lower path cost, so it replaces E_{4}.  We remove node D_{2} from the frontier and check if it's a goal node. It's not, so we continue.
 We remove node E_{3} from the frontier and check if it's a goal node. It is, so we're done.
Algorithm Notes
 Uses a priority queue for the frontier, where each node is sorted by it's value.
 The value of a node is it's path cost from the root node.
 If there is a node, say E_{4} in the queue, but we find a shorter path to node E, where the path cost is 3, then we replace the existing node E_{4} with E_{3}, rather than adding a second node E to be explored.
 It's possible for this algorithm to get stuck in an infinite loop, but only if there is a loop of zerocost paths between a set of nodes.
Return to Articles