Next: Example Previous: Maze Example

Uniform Cost Search (Branch and Bound Search)

queueing-fn is sort-by-cost-so-far

Cost from root node to current node n is g(n), which adds up individual action costs along path from root to n

Because cheapest path length is always picked until solution is reached, first solution found is least-cost (optimal) solution

Space and time complexities can be exponential, because large subtrees with inexpensive steps can be explored before useful paths with costly steps.

If costs are equal, space and time are $O(b^d)$ . Otherwise, exponent is related to cost of optimal solution.