Uniform-cost search (UCS)

Uniform-cost search (UCS)

• Description:
  • Uniform-cost is guided by path cost rather than path length like in BFS, the algorithms starts by expanding the root, then expanding the node with the lowest cost from the root, the search continues in this manner for all nodes.
  • Hints about UCS implementation can be found here.
  • You should not be surprised that Dijkstra’s algorithm, which is perhaps better-known, can be regarded as a variant of uniform-cost search, where there is no goal state and processing continues until the shortest path to all nodes has been determined.
• Performance Measure:
  • Completeness:
    • It is obvious that UCS is complete if the cost of each step exceeds some small positive integer, this to prevent infinite loops.
  •  Optimality:
    • UCS is always optimal in the sense that the node that it always expands is the node with the least path cost.
  • Time Complexity:
    • UCS is guided by path cost rather than path length so it is hard to determine its complexity in terms of b and d, so if we consider C to be the cost of the optimal solution, and every action costs at least e, then the algorithm worst case is O(b^C/e).
  • Space Complexity:
    • The space complexity is O(b^C/e) as the time complexity of UCS.
• Conclusion:
  • UCS can be used instead of BFS in case that path cost is not equal and is guaranteed to be greater than a small positive value e.