INFORMED (or HEURISTIC) SEARCH uses PROBLEM-SPECIFIC KNOWLEDGE beyond the problem definition, so it can judge which non-goal state looks more promising. A HEURISTIC FUNCTION h(n) estimates the cost of the cheapest path from the state at node n to a goal state. h(n) ≥ 0, and h(n) = 0 for a goal node. It is an ESTIMATE, supplied by the designer, and its quality determines everything. BEST-FIRST SEARCH is the general family: expand the node with the best value of an EVALUATION FUNCTION f(n). The choice of f gives the different algorithms. GREEDY BEST-FIRST SEARCH f(n) = h(n) Expand the node that APPEARS CLOSEST TO THE GOAL. · COMPLETE: no, in the tree-search version — it can get stuck in a loop. The graph-search version is complete in a finite space. · OPTIMAL: NO. It follows the locally most promising route and never reconsiders the cost already incurred. · TIME and SPACE: O(b^m) in the worst case, though a good heuristic reduces this substantially. THE FAILURE MODE, and it is instructive: greedy search ignores g(n) entirely, so it will happily take a step that looks like progress toward the goal even when it has already travelled an enormous distance. Going to Iasi to reach Fagaras, the classic Romania example, sends the search to Neamt because Neamt looks closer — and Neamt is a dead end. A* SEARCH — the central algorithm of this topic f(n) = g(n) + h(n) where g(n) is the cost to reach n and h(n) the estimated cost from n to the goal. So f(n) is the ESTIMATED COST OF THE CHEAPEST SOLUTION THROUGH n. · Identical to uniform-cost search except for the added h. UCS is A* with h = 0. · COMPLETE and OPTIMAL, provided the heuristic satisfies the conditions below. THE TWO CONDITIONS — this is the most examined content in the topic: ADMISSIBILITY h(n) NEVER OVERESTIMATES the true cost to reach the goal: h(n) ≤ h*(n) where h* is the true optimal cost An admissible heuristic is OPTIMISTIC. WHY IT MATTERS: if h overestimates, A* may reject the optimal path because it looks too expensive, and return a worse one. ADMISSIBILITY GUARANTEES OPTIMALITY FOR TREE-SEARCH A*. CONSISTENCY (also called MONOTONICITY) For every node n and every successor n′ generated by action a: h(n) ≤ c(n, a, n′) + h(n′) This is a form of the TRIANGLE INEQUALITY: going via n′ cannot make the estimate cheaper than the direct estimate. WHY IT MATTERS: consistency guarantees optimality for GRAPH-SEARCH A* — the version with an explored set. With a merely admissible but inconsistent heuristic, graph search can close a node at a suboptimal cost and never revisit it. EVERY CONSISTENT HEURISTIC IS ADMISSIBLE, but not the reverse. In practice almost every natural admissible heuristic is also consistent. A KEY CONSEQUENCE OF CONSISTENCY: f(n) is NON-DECREASING along any path, so A* expands nodes in order of non-decreasing f. It therefore expands CONTOURS of equal f, like uniform-cost search expanding circles of equal g — but the contours are stretched toward the goal. THE BETTER THE HEURISTIC, THE MORE ELONGATED THE CONTOURS AND THE NARROWER THE SEARCH. OPTIMAL EFFICIENCY: A* is OPTIMALLY EFFICIENT among optimal algorithms using the same heuristic — no other such algorithm expands fewer nodes. That is a strong theoretical result, and it means improvements must come from a better heuristic rather than a cleverer algorithm. THE REMAINING PROBLEM: A* KEEPS EVERY GENERATED NODE IN MEMORY. It usually runs out of space long before it runs out of time — the same wall as BFS in the previous topic — which is why the memory-bounded variants below exist.

TWO HEURISTICS FOR THE 8-PUZZLE, and this comparison is the standard worked example: h₁ = the number of MISPLACED TILES (Hamming distance) h₂ = the sum of MANHATTAN DISTANCES of the tiles from their goal positions (also called the city-block distance) BOTH ARE ADMISSIBLE: h₁ — every misplaced tile must move at least once, so h₁ never overestimates h₂ — each tile must move at least its Manhattan distance, and moves are one tile at a time WORKED on the state 7 2 4 goal: _ 1 2 5 _ 6 3 4 5 8 3 1 6 7 8 h₁: tiles 7,2,4,5,6,8,3,1 are all out of place → h₁ = 8 h₂: tile 7 at (0,0) → goal (2,1): 2+1 = 3 tile 2 at (0,1) → goal (0,2): 0+1 = 1 tile 4 at (0,2) → goal (1,1): 1+1 = 2 tile 5 at (1,0) → goal (1,2): 0+2 = 2 tile 6 at (1,2) → goal (2,0): 1+2 = 3 tile 8 at (2,0) → goal (2,2): 0+2 = 2 tile 3 at (2,1) → goal (1,0): 1+1 = 2 tile 1 at (2,2) → goal (0,1): 2+1 = 3 h₂ = 3+1+2+2+3+2+2+3 = 18 The true optimal solution for this state is 26 moves, so both are admissible and h₂ is far more informed. DOMINANCE: if h₂(n) ≥ h₁(n) for every n, and both are admissible, then h₂ DOMINATES h₁ and A* with h₂ never expands more nodes than with h₁. A DOMINATING HEURISTIC IS ALWAYS PREFERABLE, provided it is not too expensive to compute. THE MEASURED EFFECT — the standard published comparison, averaged over random instances: depth IDS nodes A*(h₁) A*(h₂) ───────────────────────────────────────────── 12 3,644,035 227 73 16 too many 39,135 1,641 24 too many too many unmanageable (for h₁ at 24 and beyond) ───────────────────────────────────────────── AT DEPTH 12: iterative deepening generates 3.6 MILLION nodes where A* with Manhattan distance generates 73 — a factor of about FIFTY THOUSAND. At depth 16 the two heuristics differ from each other by a factor of 24. THIS IS THE SINGLE MOST IMPORTANT ARITHMETIC IN THE SEARCH SECTION. A better algorithm within uninformed search bought 11% (IDS versus BFS in nodes) or a change of exponent (bidirectional). A GOOD HEURISTIC BUYS FOUR ORDERS OF MAGNITUDE. MEASURING HEURISTIC QUALITY — the EFFECTIVE BRANCHING FACTOR b*: if A* generates N nodes and the solution is at depth d, then b* is the branching factor a uniform tree of depth d would need to contain N+1 nodes: N + 1 = 1 + b* + (b*)² + … + (b*)^d A WELL-DESIGNED HEURISTIC HAS b* CLOSE TO 1. COMPUTED FROM THE TABLE ABOVE: h₁ at d = 12, N = 227 → b* = 1.42 h₂ at d = 12, N = 73 → b* = 1.26 h₁ at d = 16, N = 39,135 → b* = 1.84 h₂ at d = 16, N = 1,641 → b* = 1.48 Compare the uninformed branching factor of about 2.8 for the 8-puzzle. b* is the standard way to compare heuristics because it is roughly constant across problem sizes, which raw node counts are not.

WHERE DO HEURISTICS COME FROM? Four systematic sources. 1. RELAXED PROBLEMS The cost of an OPTIMAL SOLUTION TO A RELAXED PROBLEM — one with fewer restrictions on the actions — is an admissible heuristic for the original. WHY IT IS ADMISSIBLE, and this is the elegant part: the optimal solution to the original problem is also A solution to the relaxed problem, so the relaxed optimum can only be cheaper. ADMISSIBILITY IS AUTOMATIC. APPLIED TO THE 8-PUZZLE: rule: a tile moves from A to B if A is adjacent to B and B is blank relax "B is blank" → each tile moves to its goal independently → h₂, Manhattan relax both conditions → a tile can teleport anywhere → h₁, misplaced tiles SO BOTH STANDARD HEURISTICS ARE RELAXATIONS, and the technique generates them mechanically rather than by inspiration. Straight-line distance for route finding is the same trick: relax the requirement to follow roads. 2. SUBPROBLEMS AND PATTERN DATABASES The cost of solving a SUBPROBLEM — say, getting tiles 1–4 into place and ignoring the rest — is admissible for the whole. Store the exact costs for every configuration of the subproblem in a PATTERN DATABASE, computed once by backward search from the goal, then look them up during search. DISJOINT pattern databases, whose subproblems share no tiles, can have their costs ADDED and remain admissible. This is what makes optimal 15-puzzle and Rubik's cube solving practical. 3. LEARNING FROM EXPERIENCE Solve many instances, record features of each state and the actual cost to the goal, and fit a predictor. Such a heuristic is NOT guaranteed admissible, so optimality is lost — a real trade-off rather than a free improvement. 4. COMBINING HEURISTICS Given several admissible heuristics with none dominating, take the MAXIMUM: h(n) = max{ h₁(n), h₂(n), …, hₖ(n) } The maximum of admissible heuristics is admissible and dominates each of them. (The SUM is not admissible in general — only for disjoint subproblems.) MEMORY-BOUNDED VARIANTS — because A*'s space use is the practical limit: ITERATIVE-DEEPENING A* (IDA*) Iterative deepening with the cutoff on f rather than depth. Each iteration's limit is the smallest f-cost exceeding the previous limit. ✔ space O(bd) — linear, like IDS ✘ with real-valued costs, each iteration may add only one new node, so the number of iterations explodes. Best on problems with few distinct f values, such as unit-cost puzzles. RECURSIVE BEST-FIRST SEARCH (RBFS) Linear space; keeps the f-value of the best alternative path from any ancestor, and unwinds when the current path exceeds it, remembering the best f found so that it can be revisited. ✘ suffers excessive node REGENERATION. SMA* (SIMPLIFIED MEMORY-BOUNDED A*) Uses all available memory, and when full DROPS THE WORST LEAF (highest f), backing its value up to its parent so the subtree can be regenerated if needed. ✔ complete if any solution is reachable within memory ✔ optimal if the optimal solution is reachable ✘ on hard problems it can spend all its time regenerating dropped nodes — memory pressure converts into time cost WEIGHTED A* f(n) = g(n) + W·h(n) with W > 1. Weights the heuristic more heavily, so the search is more focused and faster, at the price of optimality: the solution found is at most W times the optimal cost. A BOUNDED-SUBOPTIMALITY GUARANTEE, which is often exactly the right engineering trade — a route 10% longer found 100× faster. THE SUMMARY OF THE WHOLE TOPIC: A* is optimally efficient for a given heuristic, so THE HEURISTIC IS WHERE THE ENGINEERING EFFORT BELONGS. Relaxation gives admissible heuristics mechanically; pattern databases give sharp ones; taking the maximum combines them; and if optimality can be traded, weighted A* buys speed with a stated bound.