# 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

• 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 E4 in the queue, but we find a shorter path to node E, where the path cost is 3, then we replace the existing node E4 with E3, 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 zero-cost paths between a set of nodes.