## Definition **Uninformed (or blind) search** explores the state space using only the problem definition — no domain-specific knowledge about which states are closer to a goal. The order of node expansion is governed purely by structural properties (depth, insertion order, path cost). ## Main Variants | Algorithm | Frontier ordering | Complete? | Optimal? | Time | Space | | --- | --- | --- | --- | --- | --- | | [[Breadth-First Search]] | FIFO queue | Yes (finite branching) | Yes (uniform costs) | $O(b^d)$ | $O(b^d)$ | | [[Depth-First Search]] | LIFO stack | No (infinite spaces) | No | $O(b^m)$ | $O(bm)$ | | Depth-Limited Search | DFS with cutoff $\ell$ | No (if $\ell < d$) | No | $O(b^\ell)$ | $O(b\ell)$ | | [[Iterative Deepening Search]] | Repeated DLS | Yes | Yes (uniform) | $O(b^d)$ | $O(bd)$ | | [[Uniform Cost Search]] | Priority queue by $g(n)$ | Yes (positive costs) | Yes | $O(b^{1 + \lfloor C^*/\epsilon \rfloor})$ | same | Where $b$ = branching factor, $d$ = depth of shallowest solution, $m$ = maximum depth, $C^*$ = optimal cost. ## When Each Wins - **BFS** when the solution is shallow and memory permits. - **DFS** when memory is tight and any solution suffices. - **IDS** combines BFS's optimality with DFS's space efficiency — the workhorse for completeness without heuristics. - **UCS** when path costs vary; it's BFS generalized to weighted edges. ## Limits Without a heuristic, all uninformed methods scale exponentially. For non-trivial problems they become impractical past ~$10^{6}$ states. That's the boundary where [[Heuristic Search]] becomes necessary. ## Related - [[State Space Search]] - [[Heuristic Search]] - [[A Star Algorithm]]