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 n_i is a successor of n, then g(n_i) = g(n) + c(n,n_i) , where c(n,n_i) is the cost of going from node n to node n_i .

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

Advantage:

1. Guaranteed to find the least-cost solution.

Disadvantages:

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