Uniform-Cost Search

search

Definition

Uniform-Cost Search

Uniform-cost search is about expanding the least-code unexpanded node. The frontier is a priority queue sorted by path cost, lowest first.

Properties

Completeness

Uniform-cost search is complete if the step cost $\ge \epsilon$.

Time Complexity

Let $n$ be the number of node with $g(n)\le C^{\ast }$, where $C^{\ast }$ is the cost of an optimal solution. Then:

$$O(b^{1+\lfloor C^{\ast }/\epsilon \rfloor })$$

Note that the solution test happens at expansion time. For step cost = 1, the uniform-cost search has the same cost as breadth-first search.

Space Complexity

Let $n$ be the number of node with $g(n)\le C^{\ast }$, where $C^{\ast }$ is the cost of an optimal solution. Then:

$$O(b^{1+\lfloor C^{\ast }/\epsilon \rfloor })$$

Optimality

Uniform-cost search is optimal since nodes are expanded in increasing order of $g(n)$. Solution test at expansion time ensure optimality.