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 .

Time Complexity

Let be the number of node with , where is the cost of an optimal solution. Then:

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 be the number of node with , where is the cost of an optimal solution. Then:

Optimality

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