Uniform-Cost Search

Uniform-Cost Search is guaranteed to find an optimal (lowest-cost) path from the start node to a goal node, provided all step costs are non-negative. This guarantee stems from its expansion order: it always expands the node with the smallest cumulative path cost (g(n)) first. If a cheaper path to a node is discovered later, the algorithm updates its cost and parent, ensuring the final solution is the absolute minimum cost.

• Key Condition: Requires non-negative edge weights. A negative cost could create a cycle that reduces total path cost indefinitely, breaking the algorithm's logic.
• Contrast with BFS: Breadth-First Search finds the shortest path in terms of the number of steps in an unweighted graph. UCS generalizes this to find the lowest cumulative cost in a weighted graph.

The algorithm's behavior is governed by its use of a priority queue (often a min-heap) to manage the search frontier (or open list). The priority of a node is its current path cost from the start, g(n).

• Operation: When a node is expanded, its successors are generated. Each successor's path cost is calculated (g(parent) + cost(action)). The successor is then inserted into the priority queue with this cost as its priority.
• Node Selection: The next node to expand is always the one at the front of the priority queue—the node with the smallest g(n). This greedy selection on cumulative cost is what ensures optimality.
• Efficiency: Using a min-heap allows for O(log n) insertions and O(1) access to the minimum element, making the frontier management efficient.

Uniform-Cost Search is complete, meaning it will always find a solution if one exists, given that the graph is finite and all step costs are ≥ ε > 0 (a small positive number).

• Finite Graphs: In a finite state space, UCS will systematically explore all reachable nodes in order of increasing cost, eventually finding a goal if it is reachable.
• Infinite Graphs & Zero Costs: The algorithm remains complete for infinite graphs if all step costs are ≥ ε > 0. This prevents infinite sequences of zero-cost actions that would be expanded before exploring potentially cheaper paths with positive costs. If zero-cost actions are allowed, completeness is not guaranteed without additional mechanisms like graph search with a closed set.

A defining characteristic of UCS is that it uses only the incurred path cost (g(n)) to guide its search. It does not employ a heuristic function (h(n)) to estimate the remaining cost to the goal.

• Blind Search: This makes UCS a form of blind (uninformed) search. It expands nodes based solely on the known cost from the start, with no look-ahead information about the goal's proximity.
• Contrast with A*: A* Search enhances UCS by adding a heuristic h(n) to form the evaluation function f(n) = g(n) + h(n). This allows A* to be optimally efficient under certain conditions, often exploring far fewer nodes than UCS by directing the search toward the goal.
• When to Use: UCS is ideal when no good heuristic is available, but an optimal solution is required on a weighted graph with non-negative costs.

To handle repeated states and ensure termination, UCS is typically implemented as a graph search rather than a tree search. This requires maintaining a closed set (or explored set) of already-expanded nodes.

• Process: When a node is expanded, it is moved from the frontier to the closed set. When generating a successor:
  • If it is already in the closed set, it is ignored (a cheaper path to it cannot be found, as UCS expands in order of increasing cost).
  • If it is already in the frontier with a higher cost, its cost and parent are updated in the priority queue.
• Preventing Redundancy: This mechanism prevents the algorithm from endlessly revisiting states and re-expanding them, which is critical for efficiency and termination in graphs with cycles.
• Memory Trade-off: The closed set consumes O(b^d) memory in the worst case, where b is the branching factor and d is the depth of the optimal solution.

The computational demands of UCS are significant, as it explores all nodes with a path cost less than the optimal solution cost.

• Time Complexity: O(b^(1 + C*/ε)), where b is the branching factor, C* is the cost of the optimal solution, and ε is the minimum step cost. In the worst case, it explores all nodes up to the optimal cost depth, which can be very large if costs are small.
• Space Complexity: O(b^(1 + C*/ε)). The frontier (priority queue) and the closed set must store all nodes in the explored region. This is the primary limitation of UCS for large or complex state spaces.
• Practical Consideration: While optimal, UCS can be prohibitively expensive in terms of memory and time for problems with high branching factors or where many paths have similar, low costs. This often necessitates the use of informed search algorithms like A* when a good heuristic is available.

Dijkstra's Algorithm is the canonical single-source shortest path algorithm for graphs with non-negative edge weights. Uniform-Cost Search is essentially a goal-directed variant of Dijkstra's, where the algorithm stops upon reaching a specified goal node rather than computing paths to all nodes. Both algorithms:

• Use a priority queue (min-heap) to always expand the node with the smallest cumulative path cost (g(n)).
• Guarantee an optimal solution when all step costs are non-negative.
• Have a time complexity of O(E + V log V) with an efficient priority queue implementation, where V is vertices and E is edges.

Breadth-First Search (BFS) is an uninformed search algorithm that explores a graph level by level. Uniform-Cost Search generalizes BFS from unweighted to weighted graphs:

• In an unweighted graph (where all edge costs = 1), Uniform-Cost Search behaves identically to BFS.
• BFS uses a simple queue (FIFO), while Uniform-Cost Search requires a priority queue to handle variable costs.
• BFS guarantees the shortest path (fewest edges) in an unweighted graph; Uniform-Cost Search guarantees the lowest-cost path in a weighted graph.

A Search* is a best-first search algorithm that finds a least-cost path by combining the actual cost from the start (g(n)) with a heuristic estimate to the goal (h(n)). The key comparison with Uniform-Cost Search:

• Uniform-Cost Search uses only g(n) (cost-so-far). A* uses f(n) = g(n) + h(n).
• A consistent heuristic allows A* to also guarantee optimality while typically exploring a much smaller portion of the state space than Uniform-Cost Search.
• Uniform-Cost Search can be seen as a special case of A* where the heuristic function h(n) is always zero.

Best-First Search is a family of algorithms that use an evaluation function to decide which node to expand next. Uniform-Cost Search is a specific, cost-based instance of this family:

• Greedy Best-First Search uses only a heuristic h(n) and is not optimal.
• Uniform-Cost Search uses only the path cost g(n) and is optimal for non-negative costs.
• A* combines g(n) and h(n) for optimal, informed search. The choice of evaluation function directly trades off between optimality, completeness, and search efficiency.

The search frontier (or open list) is the set of generated but unexpanded nodes. In Uniform-Cost Search, this frontier is managed as a priority queue ordered by g(n), the cumulative path cost.

• Node Expansion is the process of removing the lowest-cost node from the frontier, generating its successors, and adding them to the frontier.
• This greedy selection from the frontier based on g(n) is what ensures optimality, as the first time a goal node is selected for expansion, its path is guaranteed to be the cheapest possible.
• This contrasts with algorithms like Depth-First Search, which use a stack for the frontier.

A heuristic function, h(n), estimates the cost from node n to the nearest goal. Uniform-Cost Search is an uninformed (or blind) search algorithm because it uses h(n) = 0 for all nodes.

• This lack of guidance makes it systematically explore all nodes with a path cost less than the optimal solution cost.
• While optimal, this can be computationally expensive in large spaces, leading to the use of informed searches like A*.
• The heuristic's admissibility (never overestimating true cost) is crucial for algorithms like A* to maintain the optimality guarantee that Uniform-Cost Search provides inherently.