UNINFORMED (or BLIND) SEARCH uses no information about the problem beyond its definition — it cannot tell whether one non-goal state is more promising than another. EVERY SEARCH STRATEGY IS EVALUATED ON FOUR CRITERIA. Learn these, because every algorithm below is described by them: COMPLETENESS is it guaranteed to find a solution if one exists? OPTIMALITY does it find the LEAST-COST solution? TIME how many nodes are generated? COMPLEXITY SPACE how many nodes are stored at once? COMPLEXITY Expressed in terms of: b the BRANCHING FACTOR d the DEPTH of the shallowest goal m the MAXIMUM DEPTH of the state space (possibly ∞) BREADTH-FIRST SEARCH (BFS) Expand the shallowest unexpanded node. Implemented with a FIFO QUEUE as the frontier. · GOAL TEST APPLIED WHEN A NODE IS GENERATED, not when it is selected — which saves one whole level of expansion · COMPLETE: yes, if b is finite · OPTIMAL: only if every step costs the same. BFS finds the SHALLOWEST goal, which is the cheapest goal only when depth and cost coincide. · TIME: O(b^d) · SPACE: O(b^d) THE NODE COUNT, precisely: 1 + b + b² + … + b^d, which for b = 10, d = 5 gives 111,111 nodes. AND THE MEMORY IS THE PROBLEM. At b = 10 with 1 KB per node and a million nodes generated per second: d nodes generated time memory ────────────────────────────────────────────────── 2 111 0.0 s 111 KB 4 11,111 0.0 s 11 MB 6 1,111,111 1.1 s 1 GB 8 111,111,111 2 min 111 GB 10 11,111,111,111 3 hours 11 TB 12 1,111,111,111,111 13 days 1,111 TB 14 111,111,111,111,111 4 years 111,111 TB ────────────────────────────────────────────────── READ THE d = 8 ROW: TWO MINUTES OF COMPUTATION AND 111 GIGABYTES OF MEMORY. The time is trivial and the memory is impossible on an ordinary machine. THAT IS THE CENTRAL PRACTICAL FACT ABOUT BFS: exponential time is survivable for a while, exponential SPACE is not. Memory is the binding constraint, and it binds several levels earlier than time. UNIFORM-COST SEARCH (UCS) Expand the node with the LOWEST PATH COST g(n). Frontier is a PRIORITY QUEUE ordered by g. · TWO DIFFERENCES FROM BFS that are easy to miss and commonly examined: the goal test is applied when a node is SELECTED for expansion, not when generated — because a cheaper path to the goal may still be found a test is added in case a better path is found to a node already on the frontier · COMPLETE and OPTIMAL, provided every step cost ≥ ε > 0 (zero-cost steps permit an infinite path of no cost) · COMPLEXITY: O(b^(1 + ⌊C*/ε⌋)) where C* is the cost of the optimal solution — which can be much worse than b^d when steps are cheap relative to the solution cost · BFS IS THE SPECIAL CASE of UCS where all step costs are equal. WHY IT MATTERS: BFS finds the fewest-actions route; UCS finds the cheapest. On a road network those differ — the route with three long motorway legs beats the one with five short town roads.

DEPTH-FIRST SEARCH (DFS) Expand the DEEPEST unexpanded node. Frontier is a LIFO STACK, or equivalently the recursion stack. · COMPLETE: NO in general. It fails on infinite-depth spaces and on spaces with loops, because it can descend forever. The GRAPH-SEARCH version (with an explored set) is complete in a finite space; the TREE-SEARCH version is not. · OPTIMAL: no. It returns the first solution found, at whatever depth. · TIME: O(b^m) — and m can be much larger than d, so DFS can be dramatically worse than BFS on time · SPACE: O(b·m) — and THIS IS WHY IT IS USED. Linear space. THE SPACE COMPARISON MADE CONCRETE: at b = 10, d = 5, BFS stores about 100,000 nodes (≈100 MB at 1 KB each) while DFS stores b·m = 50 nodes — about 50 KB. A FACTOR OF 2,000 IN MEMORY, and the ratio grows as b^d/(b·d), so it worsens rapidly with depth. That single fact is why DFS remains the workhorse despite having neither completeness nor optimality. BACKTRACKING SEARCH is a variant using even less memory: only ONE successor is generated at a time rather than all of them, so space is O(m) instead of O(bm). It also allows the state to be modified in place and undone, avoiding copying. DEPTH-LIMITED SEARCH (DLS) DFS with a depth limit ℓ: nodes at depth ℓ are treated as having no successors. · solves the infinite-path problem · COMPLETE: only if ℓ ≥ d. If ℓ < d the algorithm returns failure although a solution exists — an INCOMPLETE answer that looks like a definitive one, which is the dangerous failure mode. · TIME O(b^ℓ), SPACE O(bℓ) · Sometimes a good limit is known from the problem: with 20 cities on a map, any city is reachable in at most 19 steps, so ℓ = 19 works. The DIAMETER of the state space is the principled limit. ITERATIVE DEEPENING DEPTH-FIRST SEARCH (IDS) Run depth-limited search with ℓ = 0, 1, 2, … until a solution is found. · COMPLETE: yes (when b is finite) · OPTIMAL: yes, when step costs are all equal · TIME: O(b^d) · SPACE: O(b·d) ← the point of the whole algorithm IT COMBINES BFS'S GUARANTEES WITH DFS'S MEMORY. That is a genuinely remarkable result, and the obvious objection is "surely re-generating the tree every iteration is wasteful?" THE ANSWER, AND IT IS THE KEY INSIGHT: the nodes at the BOTTOM level dominate the count, so the repeated work on the upper levels is a small overhead. IDS generates the depth-d nodes once, the depth-(d−1) nodes twice, …, the root d+1 times: N(IDS) = (d+1)·1 + (d)·b + (d−1)·b² + … + 1·b^d For b = 10, d = 5: N(IDS) = 123,456 N(BFS) = 111,111 A 11% OVERHEAD IN NODES, in exchange for reducing memory from O(b^d) to O(bd) — from about 100 MB to about 50 KB in this instance. As b grows the overhead shrinks further: the ratio tends to b/(b−1), so at b = 10 it is 1.11 and at b = 100 it is 1.01. IDS IS THEREFORE THE PREFERRED UNINFORMED METHOD when the depth is unknown and the space is large — which is the usual case. BIDIRECTIONAL SEARCH Search forward from the initial state and backward from the goal simultaneously, stopping when the frontiers meet. · TIME and SPACE: O(b^(d/2)) each direction · THE ARITHMETIC IS STRIKING: at b = 10, d = 5, b^d = 100,000 2·b^(d/2) = 2 × 10^2.5 ≈ 632 and at d = 6 it is 1,000,000 against 2,000. · REQUIREMENTS that limit its use: the goal state must be explicitly known (not merely testable — "checkmate" cannot be searched backward from) the actions must be REVERSIBLE, or predecessors computable a way to test whether the frontiers intersect, which needs the frontier of at least one direction in memory — so the space requirement is real

THE COMPARISON TABLE — memorise this; it is asked directly. CRITERION BFS UCS DFS DLS IDS BIDIR ─────────────────────────────────────────────────────────────────────────── Complete? Yes(a) Yes(a,b) No No(c) Yes(a) Yes(a,d) Optimal? Yes(e) Yes No No Yes(e) Yes(d,e) Time O(b^d) O(b^(1+C*/ε)) O(b^m) O(b^ℓ) O(b^d) O(b^(d/2)) Space O(b^d) O(b^(1+C*/ε)) O(bm) O(bℓ) O(bd) O(b^(d/2)) ─────────────────────────────────────────────────────────────────────────── (a) b is finite (b) step costs ≥ ε > 0 (c) complete if ℓ ≥ d (d) both directions use BFS (e) step costs all equal THE THREE THINGS THIS TABLE ACTUALLY TELLS YOU: 1. BFS and IDS have the SAME time complexity, and IDS uses EXPONENTIALLY LESS SPACE. There is almost never a reason to prefer BFS when memory matters. 2. DFS is the only one with linear space, which is why it survives despite lacking both guarantees. 3. Bidirectional search is the only one that reduces the EXPONENT, and exponent reductions dwarf constant-factor improvements — but its preconditions often do not hold. THE REPEATED-STATE PROBLEM — and the reason GRAPH-SEARCH exists: A search that does not remember where it has been can revisit states endlessly. The waste is not marginal: IN A RECTANGULAR GRID, moving in four directions: the number of DISTINCT states within depth d grows POLYNOMIALLY — about 2d² for a 4-connected grid the number of PATHS of length d grows as 4^d At d = 20: distinct states ≈ 800 paths = 4^20 ≈ 1.1 × 10^12 TREE SEARCH THEREFORE DOES A TRILLION TIMES MORE WORK THAN NECESSARY ON A PROBLEM WITH 800 STATES. This is the single strongest argument in the topic for maintaining an explored set. GRAPH-SEARCH adds the explored set: function GRAPH-SEARCH(problem) returns a solution or failure initialise the frontier with the initial state initialise the explored set to empty loop if the frontier is empty then return failure choose a leaf node and remove it from the frontier if the node contains a goal state then return the solution add the node's state to the explored set expand the node, adding the resulting nodes to the frontier ONLY IF not already in the frontier or the explored set THE TRADE-OFF: graph search needs O(|states|) memory for the explored set, so it converts a time problem into a space problem. For DFS this destroys the linear-space advantage, which is why IDS is usually run as TREE search with only cycle-checking along the current path — a compromise catching the common case at O(d) extra space. THE PRACTICAL SELECTION RULE: known shallow depth, memory available → BFS step costs vary → UCS deep or infinite space, memory tight → DFS depth unknown, want guarantees → IDS ← default goal explicit and actions reversible → bidirectional any structured information available → informed search, which is the next topic and a far larger win THAT LAST LINE MATTERS: uninformed search is what you use when you know nothing. A single good heuristic beats every improvement in this topic.