A heuristic function h(n) is defined to be ADMISSIBLE if for all nodes n:
Admissibility requires that the heuristic never overestimates the true remaining cost to reach the goal.
Which uninformed search algorithm guarantees finding the optimal path when all step costs are equal and positive?
When step costs are equal, shallowest goal node is optimal, so BFS guarantees optimality.
Uniform Cost Search (UCS) expands nodes in increasing order of:
UCS uses a priority queue ordered strictly by cumulative path cost g(n) from the start node.
In $\Alpha-\Beta pruning$ for Minimax search, pruning occurs at a MIN node ($\Beta cutoff$) when:
A $\Beta cutoff occurs$ at a MIN node when $\beta <= \alpha, meaning MAX already has a better choice elsewhere$.
In Iterative Deepening DFS (IDDFS), if the branching factor is b and depth is d, the total number of node expansions at the deepest level is bounded by:
IDDFS has worst-case time O($b^d)$ and space O(bd) (often written O(b*d)); repeated shallow iterations do not change the asymptotic time bound.