Uniform-Cost Search

Uniform-cost search is similar to breadth-first search. We associate with each node n a cost g(n) that measures the cost of getting to node n from the start node. g(start) = 0. If ni is a successor of n, then g(ni) = g(n) + c(n,ni) , where c(n,ni) is the cost of going from node n to node ni .

Instead of considering the first node on open, as in breadth-first search, the least-cost node on open is expanded.


  1. Guaranteed to find the least-cost solution.


  1. Exponential storage required.

  2. open list must be kept sorted (as a priority queue).

  3. Must change cost of a node on open if a lower-cost path to it is found.

Uniform-cost search is the same as Heuristic Search when no heuristic information is available (heuristic function h is always 0 ).

Contents    Page-10    Prev    Next    Page+10    Index