JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech IV Year ARTIFICIAL INTELLIGENCE Previous Question Paper (July/August - 2022 - R18)

Depth-First Search (DFS) and Iterative Deepening Depth-First Search (IDDFS) differ primarily in their approach to completeness and memory efficiency:

• Completeness: DFS is not complete in infinite state spaces or graphs with cycles, as it may get stuck in an infinite path. IDDFS is complete because it systematically increases the depth limit, ensuring that a goal at any finite depth is eventually found.
• Memory Complexity: Both algorithms are memory-efficient, requiring only O(bm) space, where b is the branching factor and m is the maximum depth. This is significantly better than Breadth-First Search (BFS).
• Optimality: DFS is not optimal, as it returns the first path found regardless of cost. IDDFS is optimal if the path cost is a non-decreasing function of the depth of the node.
• Redundant Computation: DFS visits nodes once per search. IDDFS re-visits nodes at shallower levels multiple times as the depth limit increases; however, this overhead is usually negligible because the number of nodes in a tree grows exponentially with depth.

Uniform Cost Search (UCS) is an informed search strategy used for traversing a weighted graph to find the path with the lowest cumulative cost from the start node to a goal node. Unlike BFS, which expands nodes based on depth, UCS expands nodes based on the path cost from the root.

The algorithm maintains a priority queue of paths, ordered by their total cost g(n). At each step, it selects the node with the lowest path cost for expansion. The process continues until the goal node is selected for expansion.

Key characteristics of UCS include:

• Completeness: It is complete provided that the cost of every step is greater than or equal to a small positive constant ε.
• Optimality: It is optimal because it explores paths in increasing order of cost, ensuring that the first time the goal is reached, the path taken is the cheapest.
• Complexity: The time and space complexity are O(b^(1 + floor(C*/ε))), where C* is the cost of the optimal solution and ε is the minimum edge cost.

UCS is essentially a special case of Dijkstra's algorithm applied to search trees, making it highly effective for scenarios where edge weights represent distance, time, or resource consumption.