Uniform Cost Search

Tags: #◇Computer Science #◇CSINTSY #◇Uniform Cost Search #◇Problem Solving #◇M2

---

◇Overview

Uniform Cost Search (UCS) is an uninformed search algorithm designed to find the optimal path in a state space with varying step costs. It addresses the issue of backtracking, where the same states might be explored multiple times leading to inefficiencies. By applying Dynamic Programming, solutions to subproblems can be cached, effectively reducing the number of states that must be explored. UCS maintains a frontier list and consistently explores the state with the lowest cumulative cost from the start state, ensuring that the first time a goal is reached, the path is optimal.

Characteristics of Uniform Cost Search:
Cannot handle negative edge costs.
Complete if the state space is finite.
Optimal for finding the shortest path (in terms of cost).
Time and Space Complexity: $O(n \log n)$, where $n$ is the number of states that are closer to the start state than the goal state.

◇Important Formulas

Dynamic Programming Minimum Cost Function
$\text{MinCost}(s) = \begin{cases} 0 & \text{if IsEnd}(s) \\ \min_{a \in \text{Actions}(s)} \left( \text{Cost}(s, a) + \text{MinCost}(\text{Succ}(s, a)) \right) & \text{otherwise} \end{cases}$

◇Worked Examples

Algorithm Walkthrough

1. Add $s_{start}$ to FRONTIER with priority $0$.
2. While FRONTIER is not empty:
   Remove state $s$ with the lowest priority $p$ from FRONTIER.
   If $\text{IsEnd}(s)$, then return the solution.
   Add $s$ to EXPLORED.
   For each action $a \in \text{Actions}(s)$:
   Get successor $s' = \text{Succ}(s, a)$
   If $s'$ is not yet in EXPLORED:
   Update $s'$ in FRONTIER with priority $p + \text{Cost}(s, a)$.

Routing Problem Context
When finding a route from QC to Taguig where edge weights represent traffic, UCS explores paths by incrementally extending the frontier towards nodes with the lowest total traffic cost from QC.

◇References & Navigation

• Previous Topic: ◇State-Based Models
• Next Topic: ◇Heuristics and A-Star Search
• Related Notes: ◇Dijkstra's Algorithm (Advanced), ◇Uninformed Search