Cs188AI Wiki
Advertisement

General Info[]

What[]

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

How[]

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

Details[]

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

Properties[]


Completeness[]

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

Optimality[]

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

Advertisement