Cs188AI Wiki

General Info[]


Uniform Cost Search (UCS) strategy recommends exploring nodes that have lower cost before nodes that have higher cost


  • Maintain a priority queue data structure
  • Exploration will naturally favor nodes that have lower cost because the priority queue enforces that order


  • The UCS strategy can be used as the exploration strategy both in the context of tree search and graph search



UCS is complete in that if there is a solution, UCS will find it


UCS is cost optimal in that it finds the least cost solution every time

Time Complexity[]

Assuming that the solution with the lowest cost is and each arc (getting to the next state) costs at least , then we have an upper bound on the number of levels which is

Then, it just turns into a breadth first search organized on costs instead of levels and so we get the time complexity is

Space Complexity[]

Using the same assumption as above, we see that we need to save the last cost level, which is just