—

Artificial Computational Intelligence

Heuristics: Evaluation, Design, and Relaxation

Published: 2026-08-13

Level: postgraduate

Audience: Postgraduate students in Artificial Computational Intelligence

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Greedy best-first search and A* — their evaluation functions and traces — covered in Lecture 3 (Uninformed and Informed Search)
Admissibility and consistency — the two optimality conditions for A* — covered in Lecture 3 (Uninformed and Informed Search)
Heuristic functions and informed search — what a heuristic is and where it guides the search — covered in Lecture 3 (Uninformed and Informed Search)
The 8-puzzle problem formulation — states, actions, and goal test — covered in Lecture 2 (Intelligent Agents and Problem Solving)

This session turns search inside out. Last session we met the algorithms — greedy best-first search and A* — that use educated guesses, called heuristics, to steer a search toward the goal. Now we ask the harder questions: how do we know a heuristic can be trusted, what makes one heuristic better than another, where do heuristics come from, and how do we invent them when nobody can give us one? The answers run from two mathematical checkable properties (admissibility and consistency) through practical design on the N-Queens and tile-puzzle problems, all the way to machines that learn their own heuristics.

4.1 Recapping Informed Search: Greedy Best-First Search and A*

Hook: What is the difference between wandering a maze with your eyes closed and walking it with a compass that always points somewhere useful? That difference is exactly the difference between uninformed and informed search — and the compass is the heuristic.

The previous session ended with the split between uninformed and informed search. Uninformed search is a blind search: only the problem is given, and we have no idea where we are heading. Breadth-first search and depth-first search belong to this family: they grind through the state space layer by layer or branch by branch, treating every direction as equally promising. Recall the cost of that blindness — breadth-first search on a tree with branching factor $b$ and solution at depth $d$ generates $1 + b + b^{2} + \dots + b^{d} = O (b^{d})$ nodes, and remembers all of them. For many practical applications that is not good enough.

Informed search adds intuition and guidance — educated guesses that point the search in promising directions. It is still a search: the problem definition (initial state, actions, transition model, goal test, path cost) stays exactly the same. What changes is that a helper function, the heuristic, attaches a number to each state telling the search how close that state looks to the goal, so the search can spend its effort where the number says the answer probably lies.

4.1.2 Greedy Best-First Search versus A*

Two informed strategies were covered: greedy best-first search and A* (read as "a star"). Greedy best-first search considers only the heuristic. It never uses $g (n)$ , the actual cost so far. That makes it fast, because there is no extra computation — we just trust the heuristic — but it might not always give an optimal solution. A* is more cautious: it combines both, the actual cost spent so far and the heuristic from the current node to the goal:

$f (n) = g (n) + h (n)$

where $f (n)$ is the total estimated cost of a path through node $n$ , $g (n)$ is the actual cost already spent to reach $n$ , and $h (n)$ is the heuristic estimate of the remaining cost from $n$ to the goal. Every symbol is a cost: $g$ says what we have already paid, $h$ says what we still expect to pay, and $f$ is their sum — the estimated price of the whole trip if we continue through $n$ . Both algorithms are best-first searches: at every step they expand the frontier node with the lowest evaluation value, and the only difference is which evaluation they use.

Formalize — two evaluation functions, one family. Greedy best-first search expands the node with the lowest $f (n) = h (n)$ : it ignores the past and races toward whatever looks closest to the goal. A* expands the node with the lowest $f (n) = g (n) + h (n)$ : it will only go toward the goal if the road already traveled does not make the trip too expensive. These two are opposite ends of a sliding scale: uniform-cost search uses $f (n) = g (n)$ (heuristic off), and weighted A* uses $f (n) = g (n) + W \cdot h (n)$ for a weight $W > 1$ , letting you turn the heuristic dial from 0 (pure cost) to $\infty$ (pure greed).

Strategy	Evaluation $f (n)$	Trades	Optimality
Uniform-cost search	$g (n)$	never guided	optimal
A*	$g (n) + h (n)$	cost + guidance	optimal if $h$ is admissible
Weighted A*	$g (n) + W \cdot h (n)$ , $W > 1$	speed vs. solution quality	near-optimal
Greedy best-first search	$h (n)$	pure speed	not guaranteed

Worked recap — Arad to Bucharest. The classic example uses the straight-line distance to Bucharest as the heuristic, $h_{SLD}$ . From Arad, $h_{SLD} = 366$ ; from Sibiu, 253; from Timisoara, 329; from Zerind, 374; from Fagaras, 176; from Rimnicu Vilcea, 193.

Greedy best-first search expands Arad, picks its child with the smallest $h$ — Sibiu (253) — expands Sibiu, picks Fagaras (176), expands Fagaras, and Bucharest (0) is a goal. The path Arad → Sibiu → Fagaras → Bucharest has total road cost $140 + 99 + 211 = 450$ . But the true shortest path is Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest, costing $140 + 80 + 97 + 101 = 418$ . Greedy found a goal fast and never expanded a node off its own path, yet the answer is 32 km too long — greed without a look at the road already traveled.

A* avoids that. At Arad it creates Sibiu with $f = 140 + 253 = 393$ , Timisoara with $f = 118 + 329 = 447$ , and Zerind with $f = 75 + 374 = 449$ ; it expands Sibiu (lowest $f$ ). From Sibiu the best candidate becomes Rimnicu Vilcea with $f = 220 + 193 = 413$ , then Pitesti with $f = 317 + 100 = 417$ . When Bucharest finally appears via Fagaras at $f = 450$ , it is not expanded — a node with $f = 417$ is still on the frontier, and A* keeps searching until the goal is the cheapest node on the frontier. It returns the 418-cost path.

Sense-check: greedy expanded only 4 nodes on its (suboptimal) path, while A* refused a goal at 450 to settle for one at 418 — the extra caution bought the optimal answer.

A bunch of problems were solved with these two algorithms last session, including the classic Arad-to-Bucharest example above.

4.1.3 Where Heuristics Come From and the Closeness Principle

Where do heuristics come from? From domain experts and subject-matter experts (SMEs). A person who has planned hundreds of delivery routes, or solved thousands of sliding-tile puzzles, carries practical rules of thumb about what a good state looks like; we turn those rules into numbers. Are they always right? Not really — they can be wrong, and wrong heuristics mean no optimal solutions. So before trusting a heuristic, we evaluate how good or bad its values are.

Pitfall — trusting an unevaluated heuristic. A heuristic is a guess, not a fact. If the guess is bad — for instance it promises 60 where the truth is 50 — the search follows a path that looks cheap but is actually expensive, and the returned solution can be silently suboptimal. The whole evaluation machinery of this session exists because "it came from an expert" is not a guarantee.

One gentle principle drives that evaluation. If the heuristic values are close to the actual values, the heuristic is good. That sounds simple, but it is powerful. Close heuristic values are promising: they will guide the search well. Values far from the truth are misleading, and they will not take us to the optimal answer. This closeness principle is the yardstick behind everything in this session: the next sections make it precise (admissibility forbids values above the truth, informativeness rewards values near it), and the rest of the course keeps coming back to it.

Recap + bridge: Informed search replaces blind expansion with a numeric compass — greedy best-first follows only the compass, A* pays attention to the road already traveled, and both are only as good as the compass. The compass needs two guarantees before we trust it: it must never point past the truth (admissibility), and it must not contradict itself step by step (consistency). Those two checks are the entire subject of the next section.

In real-world systems this is exactly how navigation works: a routing app on your phone runs an A*-style search over a road graph, with a heuristic derived from the straight-line (great-circle) distance between two points on the globe. The heuristic is cheap to compute, never overestimates the true road distance, and turns a search over tens of millions of junctions into one that explores only a narrow corridor around the best route — informed search working silently behind nearly every turn-by-turn instruction.

4.2 Admissibility and Consistency

Two properties decide whether a heuristic can be trusted: admissibility and consistency. The previous session covered both theoretically; this session puts them to work on a concrete directed graph. Both properties must be computed for every node and every edge of the problem — never once for the whole problem.

Hook: How can you tell whether an expert's guess is safe before betting a whole search on it? The answer is a pair of inequalities you can check with pen and paper: one for every node, one for every edge. If either fails anywhere, the optimality guarantee is off.

4.2.1 Admissibility: The Optimistic Heuristic

An admissible heuristic — one that is optimistic — may underestimate the true cost, but it never exaggerates or overestimates it. For every node, the heuristic value must never overestimate the real cost of reaching the goal. Write the true minimal cost to the goal as $h^{*} (n)$ . Then admissibility says:

$h (n) \leq h^{*} (n)$

for every node $n$ in the problem, where $h^{*} (n)$ (read "h-star") is the exact minimum cost of any path from $n$ to the goal. The property is per node: it is a list of inequalities, one per node, and every single one must hold. If a heuristic promises a cost bigger than the truth, it is misleading: the search will follow a path that looks cheap but is actually expensive.

Why "optimistic"? An admissible heuristic assumes the best — it says "reaching the goal from here will cost at least this much, possibly less." Underestimating is harmless in the sense that the search may explore a little more than needed, but it can never be tricked into discarding the optimal route, because the optimal route never looks worse than it is. Overestimating does the damage: a node whose true remaining cost is 50 but whose heuristic says 60 can be skipped in favor of a node that really costs 120 — the search has been lied to.

Formalize — why admissibility yields optimality. Suppose the optimal path has total cost $C^{*}$ , but A* returned a path with cost $C > C^{*}$ . Then some node $n$ on the optimal path was never expanded — if all optimal-path nodes had been expanded, the optimal path itself would have been found. Let $g^{*} (n)$ be the true cheapest cost from the start to $n$ , and $h^{*} (n)$ the true cheapest cost from $n$ to the goal. Since $n$ was not expanded, its $f$ -value must have exceeded the returned cost: $f (n) > C$ . But $f (n) = g (n) + h (n) \leq g^{*} (n) + h^{*} (n) = C^{*}$ , where the middle inequality uses admissibility $h (n) \leq h^{*} (n)$ and the fact that $n$ sits on the optimal path. Contradiction: $C < f (n) \leq C^{*} < C$ . The supposition is impossible, so A* with an admissible heuristic must return a cost-optimal path. This is the standard proof by contradiction behind the lecture's claim that "the heuristic never misleads you."

4.2.2 Consistency: The Triangular Inequality

Consistency is the edge-level version of the same idea. Take any edge from node $i$ to node $j$ with actual cost $c (i, j)$ , plus the heuristic values of both endpoints. The heuristic value of $i$ must be no larger than the actual cost of the edge plus the heuristic value of $j$ :

$h (i) \leq c (i, j) + h (j)$

for every directed edge $i \to j$ in the graph, where $c (i, j)$ is the positive cost of traveling from $i$ to $j$ . In words: going directly from $i$ to the goal must never look more expensive than the honest route through the neighbor — pay the edge cost, then let $j$ 's estimate take over.

Here is how the formula is derived. On the example graph, take the edge from node 1 to node 2 with actual cost 70. The condition starts as the difference of two heuristic values:

$h (1) - h (2) \leq 70$

With $h (1) = 80$ and $h (2) = 60$ , we get $80 - 60 = 20 \leq 70$ , which holds. Moving $h (2)$ to the other side (it becomes plus) gives $h (1) \leq 70 + h (2)$ , and generalizing the indices $i$ and $j$ produces the triangular-inequality form above:

$h (1) - h (2) h (1) h (i) \leq c (1, 2) \leq c (1, 2) + h (2) \leq c (i, j) + h (j) (start from the difference of the two estimates) (add h (2) to both sides) (generalize the nodes to i and j)$

The name comes from the picture: the direct heuristic guess from a node to the goal must be shorter than or equal to going through a neighbor first — the heuristic value of $i$ , plus the cost of the edge to $j$ , plus the heuristic value of $j$ .

Visual intuition: Draw a triangle whose vertices are node $i$ , node $j$ , and the goal. The direct edge $i \to j$ has cost $c (i, j)$ ; the sides $i \to goal$ and $j \to goal$ are labeled with the heuristics $h (i)$ and $h (j)$ . The triangle inequality says the length of one side cannot exceed the sum of the other two: $h (i) \leq c (i, j) + h (j)$ . The landmark: equality $h (i) = c (i, j) + h (j)$ means the heuristic is perfectly consistent along that edge — the estimate shrinks exactly as fast as the real cost grows, so the search makes smooth progress. In a grid where each step toward the goal costs 1 and shrinks $h$ by exactly 1, $f = g + h$ stays perfectly flat along the optimal path — every node on it scores identically, and A* marches straight along it.

Two facts connect the properties. First, consistency implies admissibility (given the goal's heuristic is 0 and edge costs are positive): chaining the inequality along an optimal path from $n$ to the goal telescopes into $h (n) \leq c (n, \dots) + 0 = h^{*} (n)$ . The reverse does not hold — a heuristic can be admissible at every node yet violate the inequality on some edge, exactly as the failing edge in the example below shows. Second, with a consistent heuristic the evaluation $f (n) = g (n) + h (n)$ never decreases along any path, because $f (j) = g (i) + c (i, j) + h (j) \geq g (i) + h (i) = f (i)$ . So A* expands nodes in nondecreasing $f$ order, finds each state's best path the first time it reaches it, and never needs to reopen a closed node. The lecture states this as: consistency catches a misleading value before the search trusts it, edge by edge.

4.2.3 Worked Example: Checking Admissibility on a Five-Node Graph

Here is the graph used in the session. Five nodes, labeled 1 through 5, with the heuristic values $h (1) = 80$ , $h (2) = 60$ , $h (3) = 0$ , $h (4) = 200$ , $h (5) = 190$ . The goal is node 3, and its heuristic is 0 because we are already at the goal. The directed edges and their costs: $1 \to 3$ costs 125, $1 \to 2$ costs 70, $2 \to 3$ costs 50, $1 \to 4$ costs 100, $2 \to 4$ costs 75, $2 \to 5$ costs 125, $3 \to 4$ costs 100, $4 \to 5$ costs 50, and $5 \to 1$ costs 75.

The admissibility procedure for a node: enumerate every path from that node to the goal, sum the costs of each, take the minimum, and compare it with the heuristic value.

Node 1: two paths exist. Direct $1 \to 3$ costs 125. The other, $1 \to 2 \to 3$ , costs $70 + 50 = 120$ . The minimum actual cost is 120. Is $80 \leq 120$ ? Yes — node 1 is admissible. (80 is also less than 125, so the direct-path reading is not wrong either; more on min versus max below.)

Node 2: only one path, $2 \to 3$ , costing 50. The heuristic says 60, and $60 \leq 50$ is false. Node 2 is NOT admissible. The heuristic overestimates: it claims 60 where the truth is 50. This is the expert's slip the design workflow must catch before deployment.

Node 3: the goal itself; $h (3) = 0$ by definition, so no check is needed.

Node 4: two paths. $4 \to 5 \to 1 \to 3$ costs $50 + 75 + 125 = 250$ . The other, $4 \to 5 \to 1 \to 2 \to 3$ , costs $50 + 75 + 70 + 50 = 245$ . The minimum is 245, and $200 \leq 245$ holds — admissible.

Node 5: two paths. $5 \to 1 \to 3$ costs $75 + 125 = 200$ (one moment of carelessness first gave 195 for this sum, then the correct 200). The other, $5 \to 1 \to 2 \to 3$ , costs $75 + 70 + 50 = 195$ . The minimum is 195, and $190 \leq 195$ holds — admissible.

So in this example, nodes 1, 4, and 5 pass, node 2 fails, and the goal needs no check. Because one node violates admissibility, this heuristic set is not admissible overall. On min versus max: some authors compare the heuristic against the maximum path cost instead; the convention used here — and in the session — is the minimum actual cost. Naming your convention matters, because $80 < 125$ and $80 < 120$ are both true here.

Sense-check on the whole check: the heuristic set fails exactly where intuition says it should — node 2, whose expert-supplied value (60) exceeds the only real cost available (50). Every other node's value sits under the cheapest honest route to the goal. One failure is enough: "admissible" is a property of the entire set, not of most of its values.

4.2.4 Worked Example: Checking Consistency Edge by Edge

Consistency must hold for every edge. For each directed edge $i \to j$ , check $h (i) \leq c (i, j) + h (j)$ :

Edge $1 \to 2$ : $80 \leq 70 + 60 = 130$ — true, consistent.
Edge $5 \to 1$ : $190 \leq 75 + 80 = 155$ — false. This edge violates consistency.
Edge $1 \to 4$ : $80 \leq 100 + 200 = 300$ — true.
Edge $2 \to 4$ : $60 \leq 75 + 200 = 275$ — true.
Edge $2 \to 5$ : $60 \leq 125 + 190 = 315$ — true (the session read this sum as 350; the correct sum is 315, and the verdict is unchanged).
Edge $4 \to 5$ : $200 \leq 50 + 190 = 240$ — true.
Edges $3 \to 4$ and $3 \to 5$ : satisfied immediately, because $h (3) = 0$ , and $0 \leq cost + anything$ always holds for positive costs. These two are often skipped in writing, but they are still part of the check.

Read the failing edge closely. From node 5 the heuristic promises 190 to the goal. But the honest route through node 1 — the actual edge cost 75 plus the heuristic of node 1, 80 — totals only 155. The real estimate is better than the direct guess, so believing the 190 would mislead the search. That is why the check exists: this edge tells the search to distrust its own heuristic value and go through the neighbor instead.

4.2.5 What the Two Properties Guarantee

If every heuristic value is admissible and every edge is consistent, then A* becomes optimal — it is guaranteed to always give the best answer. Otherwise the guarantee is lost. The reason: a heuristic that never overestimates never misleads you, so the search always moves closer to the solution. Consistency applies the same logic per edge: whenever a heuristic value is not less than the path cost through the neighbor, that value is lying, and the check catches it. The two properties are really the same idea at two levels — admissibility checks overestimation of values, consistency checks the identical inequality edge by edge.

Scope — what the properties assume. (1) All edge costs are positive; with negative costs the "shorter via the neighbor" reasoning can reverse, and the search can loop. The session notes negative costs appear only in very unique problems, and the search stops at the first attempt there. (2) A single goal with $h (goal) = 0$ ; multiple zero-heuristic nodes would signal multiple goals. (3) The checks assume a directed graph and path enumeration along the arrows only. (4) Admissibility alone guarantees optimality; consistency additionally guarantees nondecreasing $f$ , no reopening of expanded nodes, and the smooth-contour picture — and it implies admissibility, so checking consistency subsumes it. Nothing here requires ordering of nodes, and the checks are repeated for every node, regardless of node count, because this all happens at design and experimentation time, when the problem is small enough to check.

Pitfalls — the checks in practice. (1) Checking admissibility once for the whole problem instead of once per node — the property is a list of per-node inequalities, and a single violator, like node 2 with $60 \leq 50$ false, fails the set. (2) Confusing the two conventions: min-cost comparison (used here) versus max-cost comparison used by some authors — pick one, state it, stay consistent, since $80 < 125$ and $80 < 120$ are both true and the choice can flip a borderline verdict. (3) Enumerating paths against the arrows: the graph is directed, so paths like $4 \to 3$ are not legal even though the reverse edge $3 \to 4$ exists. (4) Skipping the edges out of the goal in writing is fine, but skipping them in your mind is not — they always pass with positive costs because $0 \leq cost + anything$ . (5) Reporting the failed edge's numbers with a slip: on edge $2 \to 5$ the sum $125 + 190$ is 315, not 350 — always recompute the arithmetic; the verdict survived here, but arithmetic errors can hide real violations.

4.2.6 Student Questions and Answers

Q: Does the direction of the arrows matter for these checks?

A: Yes — everything depends on the direction of the graph. For example, you can go from node 3 to node 4, but you cannot go from node 4 to node 3. Enumerate paths only along the directed edges.

Q: Is it compulsory to satisfy admissibility even when the difference is very minor?

A: Yes — that is the property. If you do not want an optimal solution, then it does not matter. But if you are looking for optimality, the heuristic values must be admissible, with no exceptions.

Q: If nodes are repeated, do we consider all the different paths?

A: In these problems nodes should not be repeated; edges can repeat — there can be bidirectional edges — but why would a node repeat, that would be a self-loop. In a traveling salesman problem, why would the same city appear again and again? A repeated node only adds cost, and it can never be optimal. Take one clean, straightforward path from the node to the goal and stop at the goal; never loop back.

Q: What if the goal is not reachable from a node?

A: Then the actual path cost becomes infinity, and any heuristic value is less than infinity, so that node passes admissibility without any work.

Q: Can a path revisit the starting node, like $1 \to 2 \to 4 \to 5 \to 1 \to 3$ ?

A: No — you stop at the goal, and you do not go back and forth. Backtracking through the same node is never optimal, so you do not consider such paths.

Q: Does consistency help improve performance?

A: It is a necessary condition. With inconsistent edges, A* is not guaranteed to give an optimal solution. With all edges consistent and all values admissible, the guarantee holds.

Q: Why do these properties always lead to an optimal solution?

A: If you never overestimate, the heuristic never misleads you, and you always go closer to the solution. Consistency does the same per edge: whenever a heuristic value is not less than the path cost through the neighbor, that value is misleading, and the check catches it before the search trusts it. (See the proof-by-contradiction in Section 4.2.1 for the formal version.)

Q: Do we check direct incoming edges or indirect incoming edges for consistency?

A: Direct incoming edges — and once you check those, the indirect paths are already covered, because the edge-level checks compose across the graph.

Q: We skipped $3 \to 4$ and $3 \to 5$ — are they really not checked?

A: They are checked, but they always pass, because the goal's heuristic is 0, and $0 \leq cost + anything$ is always true with positive costs. That is why they are not written down.

Q: Is $h (n) = 0$ valid for more than one node?

A: Not really — multiple zero heuristics would mean multiple goals. With a single goal, only the goal node carries the zero. (One standard remark: the "blind" heuristic $h (n) = 0$ for every node is admissible but carries no information — it reduces A* to uniform-cost search. The lecture's point is the opposite direction: an informative heuristic should reach zero only where the goal actually is.)

Q: Should we take the minimum or maximum actual path cost when checking admissibility?

A: Take the minimum — that is the honest comparison, and the convention used here. Some authors take the maximum; that reading is also not wrong. Just be consistent and state your choice.

One more warning: negative edge costs are rare, appearing only in very unique problems. With negative values you can get stuck in loops, so the search stops at the first attempt. For normal search problems all costs are positive.

4.2.7 The Design-Phase Workflow

These checks happen while designing the heuristic, on a sample problem where the actual costs are known — not after deployment. In industry the same discipline applies: take a sample problem, design the heuristic, compare its values with the truth, see which design is more promising, and only then deploy. If a heuristic turns out to be inadmissible, go back to the domain expert — or choose a better SME — and ask for corrected values. The expert supplied 60 where the actual cost is 50; that must be course-corrected before the search ever runs on real data. This is why sample problems matter: for the sample, we know the actual costs, so a bad heuristic cannot hide.

Recap + bridge: Admissibility is per-node optimism ( $h (n) \leq h^{*} (n)$ ), consistency is the same inequality per edge ( $h (i) \leq c (i, j) + h (j)$ ), and together they convert A* from "probably good" into "provably optimal." The failing edge $5 \to 1$ showed a heuristic that is admissible at every node yet still lies on one edge — which is why the session checks both, everywhere. With the trust question settled, the next section asks the harder question: what makes one trusted heuristic better than another?

Exam note: a recurring question type gives a graph with heuristic values and asks you to apply greedy best-first search and A*, then check admissibility and consistency for all values. Expect to compute both properties for every node and every edge — that is the exercise pattern of this session. A related question may hand you a problem and ask for the state representation, the relaxed versions of the problem, which constraint was relaxed, and heuristics for the relaxed versions (Sections 4.6 and 4.7). Practice the five-node checks above until the enumeration becomes mechanical.

Real-world: exactly these checks run before any industry search ships — a logistics planner validating its estimated drive-time heuristic against known depot-to-depot costs, a game studio verifying the pathfinding heuristic on hand-built test maps — because the alternative is an agent that confidently returns routes that are not the best, and users notice.

4.3 What Makes a Good Heuristic

Hook: If two experts both give you an admissible, consistent heuristic, which one do you ship? And if neither wins, can you merge them into a third that beats both? This section turns "good" from a vague feeling into three testable properties and a set of comparison rules.

4.3.1 The Three Properties: Admissible, Consistent, Informative

A good heuristic carries three properties. It should be admissible: it never overestimates the true cost. It should be consistent: the triangular inequality holds across neighboring (adjacent) nodes. And it should be informative: its values are close to the actual costs, which helps A* avoid unnecessary exploration. If the heuristic values are far from the true costs, the search wanders — going here and there — and you end up exploring almost everything. Informativeness is exactly the closeness principle from the recap: the closer the estimate to the actual cost, the stronger it is, and the less the search expands. A good heuristic should also be fast to compute, and its branch factor should be low.

The first two properties are correctness: they keep the optimality guarantee from Section 4.2 intact. The third is efficiency: an admissible heuristic that is wildly optimistic (always estimating near 0) never lies, but it guides almost not at all — A* then degenerates toward uniform-cost search and explores in all directions. A heuristic that is truthful and tight is what makes the search cut corners safely. Computation speed is a practical fourth constraint: a brilliant heuristic that takes longer to evaluate than the nodes it saves is a net loss.

4.3.2 Choosing Among Multiple Heuristics: Dominance and Superset

A problem can have several candidate heuristics from different experts. One case guides the choice directly. Suppose expert A's heuristic contains every piece of information that expert B's gives, plus something extra — A's values dominate B's, meaning the superset-subset relationship holds. Then choose A, because the extra insight is always good in informed search. The textbook covers this small concept under the name dominance; whenever one heuristic dominates another, you can ignore the lower one.

Formalize — dominance. Heuristic $h_{A}$ dominates $h_{B}$ if $h_{A} (n) \geq h_{B} (n)$ for every node $n$ . Why is more always better? Recall from the contour picture of A* that every node with $f (n) < C^{*}$ is surely expanded. With a consistent heuristic this reads $h (n) < C^{*} - g (n)$ . Since $h_{A}$ is at least as large as $h_{B}$ everywhere, the set of nodes satisfying the inequality for $h_{A}$ is a subset of those for $h_{B}$ : A* with $h_{A}$ expands only a subset of the nodes A* with $h_{B}$ would. In the 8-puzzle, the sum-of-Manhattan-distances heuristic $h_{2}$ dominates the misplaced-tile count $h_{1}$ — a misplaced tile contributes at least 1 to $h_{2}$ , so $h_{2} (n) \geq h_{1} (n)$ for every state — and A* with $h_{2}$ never expands more nodes than A* with $h_{1}$ (except for unlucky tie-breaking).

Worked example — dominance with real numbers. A typical random 8-puzzle at solution depth $d = 10$ (averaged over 100 instances): uninformed breadth-first search generates 1,033 nodes, A* with $h_{1}$ (misplaced tiles) generates 116 nodes, and A* with $h_{2}$ (Manhattan sum) generates 48 nodes. At depth $d = 24$ : BFS 290,082 nodes, $h_{1}$ 53,039, $h_{2}$ 5,733. $h_{2}$ dominates $h_{1}$ , and the node counts confirm it — the better heuristic cuts the explored tree by an order of magnitude.

Sense-check: fewer nodes generated means less time and less memory, and the two heuristics are equally cheap per evaluation; the domination argument predicts exactly the ranking the measurements show.

4.3.3 Effective Branch Factor

What if two heuristics are both admissible and consistent, and neither covers the other? Then compare the effective branch factor — how much each one makes us explore. If expert A's heuristic explores 3 nodes at a given state while expert B's explores 5, pick A: more exploration means more cost. The heuristic that prunes harder while still giving correct answers is the better choice. The heuristic should not explore everything possible.

Formalize — the effective branching factor $b^{*}$ . If A* generates $N$ nodes total for a problem whose solution sits 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^{*})^{2} + \dots + (b^{*})^{d}$

Smaller $b^{*}$ means the search behaves like a slimmer tree — the heuristic prunes more. A well-designed heuristic pushes $b^{*}$ close to 1, allowing fairly large problems to be solved at reasonable cost. In the 8-puzzle measurements above, $b^{*}$ for BFS is about 1.85, for A* with $h_{1}$ about 1.43, and for A* with $h_{2}$ about 1.27 — the heuristic with the smaller effective branching factor is the better one.

The effective branching factor is a practical yardstick, not a formula you compute in your head per node: it is measured by running the search on a handful of problem instances and counting generated nodes. Because $b^{*}$ stays fairly constant across instances of the same domain, a measurement on a small sample predicts overall usefulness — the same sample-problem discipline as the admissibility checks of Section 4.2.

4.3.4 Combining Heuristics with Weights

Sometimes the best answer is neither expert — combine both. Give each expert a weight based on trust: someone with great experience and a strong past record earns a bigger multiplication factor. The weighted combination looks like:

$h (n) = α \cdot h_{1} (n) + β \cdot h_{2} (n)$

where $h_{1} (n)$ and $h_{2} (n)$ are the two experts' heuristic values, and $α$ and $β$ are the weights. In the session's example, $α = 2$ for the more trusted expert and $β = 1.2$ or 1.3 for the other. Combining both models can build one more reliable model. The course returns to multi-heuristic guidance later; being guided by several heuristics at once is perfectly valid.

Scope — what the weights buy and cost. The trust-weighted sum is a management decision, not a math guarantee: it reflects belief in the experts. If both component heuristics are admissible, any positive weights keep the sum admissible, because a positive-weighted sum of underestimates is still an underestimate — $h_{1} (n) \leq h^{*} (n)$ and $h_{2} (n) \leq h^{*} (n)$ imply $α h_{1} (n) + β h_{2} (n) \leq (α + β) h^{*} (n)$ , which only lands below $h^{*} (n)$ after normalizing the weights (e.g., $α + β = 1$ ); with unnormalized weights like 2 and 1.2, the combined value can overshoot the true cost, so treat the lecture's trust-weighted form as a guidance blend, and re-check admissibility of the blend if the exam demands the guarantee. The textbook alternative that always preserves admissibility is the max-combination $h (n) = max {h_{1} (n), h_{2} (n)}$ , which dominates each component and stays admissible (and consistent if every component is) — at the price of computing all components at every node.

4.3.5 Min or Max? It Depends on the Problem

Whether a heuristic should be minimized or maximized depends on what it counts. The tile-puzzle heuristics (below) get better as they get smaller, and 0 means the goal. But a heuristic that counts non-conflicting queen pairs gets better as it grows, and its maximum means the goal. There is no blanket rule — in problems about maximization, you may well take the max. The session showed both kinds, so never default to "always take the least".

Pitfall — the min/max reflex. Students who learn on the tile puzzle assume every heuristic is "lower is better." That reflex breaks the moment a heuristic counts something good (non-conflicting pairs, safe queens, matched features) instead of something bad (moves remaining, misplaced items). Read what the quantity counts, decide the direction of "better," and state it — the N-Queens heuristics in Section 4.7 are maximized, the tile-puzzle heuristics in Section 4.8 are minimized, and both sets are correct for what they count.

4.3.6 The Helpful Guide

A thumb rule worth remembering: a good heuristic is like a helpful guide. It does not lie about the distance, but it gives enough direction to avoid exploring everywhere. A heuristic that tells the truth yet still leaves the search free to wander is useless; one that guides while staying honest is the goal.

Recap + bridge: A good heuristic is admissible (never overestimates), consistent (triangle inequality on every edge), and informative (close to the truth). Between candidates, use dominance and the effective branch factor; when experts disagree, blend them with trust weights or take the max. Next, the section steps back to ask where heuristics come from and why the whole machinery exists — the state-space explosion that makes informed search necessary.

Real-world: effective branching factor is the metric reported in most published search research — a paper claiming "our learned heuristic solves 15-puzzles with $b^{*} = 1.05$ " is saying the search behaves like a nearly binary tree; route-planning systems on live road maps measure $b^{*}$ on logged queries to decide whether a heuristic upgrade is worth deploying.

4.4 What Is a Heuristic and Why We Need One

Hook: Why would an AI ever rely on a guess? Because for real problems the "count every possibility" strategy fails before it starts — the state spaces are simply too large to explore. The guess, called a heuristic, is what makes the difference between a search that takes centuries and one that takes milliseconds.

4.4.1 Etymology and Definition

A heuristic is a practical rule of thumb, an educated guess, or an intuition. The word comes from a Greek root meaning "to find" or "to discover". The insight behind it: prioritize the exploration of paths that seem most promising rather than exploring all possibilities. It is like using a compass and a map in a maze instead of wandering aimlessly.

Formalize — the definition and the analogy. A heuristic is a function: it takes a state and returns a number estimating how close that state is to the goal. The term's Greek root, heuriskein ("to find"), is the same root as the famous cry "Eureka!" ("I have found it!") — the word carries the spirit of discovery through insight rather than brute force. The professor's picture: a maze-walker with a compass and a map still explores, but never aimlessly — every fork is judged against a sense of direction. The analogy's limit: a compass always points truly, while a heuristic is only a guess; that is exactly why Sections 4.2 and 4.3 spent their time verifying and comparing guesses. Because heuristic functions determine the search strategy and thereby its complexity, finding better heuristic functions — while keeping admissibility and consistency — is an important task in itself.

4.4.2 The State-Space Explosion Problem

The core task of search is solving complex problems by searching vast, often infinite state spaces. Consider the 15-puzzle: it has about 1.3 trillion possible states, as stated in the session (the exact count is $16! /2 \approx 10.46$ trillion reachable states — half of the $16!$ arrangements are unreachable because every move preserves the parity of the permutation; the lecture rounded to 1.3 trillion). Uninformed search — BFS, DFS — needs tremendous computing power even then, and still follows millions of unnecessary paths. Blind search over such a space is inefficient and takes a very long time. Informed strategies exist precisely because of this explosion.

Worked example — the explosion in numbers. The 8-puzzle has $9! /2 = 181, 400$ reachable states — small enough to hold in memory and search blindly. Its big sibling, the 15-puzzle, has $16! /2 \approx 10.46$ trillion states. At one node per microsecond, plain enumeration of the 15-puzzle's states would take on the order of a year of pure generation, and a breadth-first search must store the frontier as it goes. Chess is far worse: roughly $1 0^{43}$ legal positions, a number so large that no blind search has any hope — yet Deep Blue beat a world champion by searching a sliver of it, guided by heuristics. The growth is exponential: each extra tile multiplies the state count, and exponential problems cannot be solved by uninformed search for any but the smallest instances.

4.4.3 Pruning

Good heuristics eliminate irrelevant branches from exploration. Pruning means cutting down some branches and not exploring them, because they are not promising. In the Arad-to-Bucharest example, at every stage you pick the least-cost node and explore only that one — indirectly you are pruning the rest. The payoff is a performance boost: pruning sharply reduces node explosion, saving time and memory, and it keeps the effective branch factor low.

Formalize — what pruning actually cuts. In the Arad-to-Bucharest A* trace, Timisoara enters the frontier with $f = 118 + 329 = 447$ and Zerind with $f = 75 + 374 = 449$ . Both would be among the first nodes expanded by uniform-cost search, yet A* never expands either — the solution is found at $f = 418$ , and every frontier node with $f > 418$ is pruned without being examined. That is the whole economy of informed search: possibilities are eliminated from consideration without being examined, which is what "pruning" means here. It is not cutting off a promising branch; it is correctly skipping branches that cannot improve the answer.

4.4.4 Real-World Uses of Informed Search

Real-world: pathfinding — maps, games, and navigation — uses informed search. Deep Blue, the chess computer that defeated Garry Kasparov, ran heuristic functions; it was not purely exploring the chess state space. Robotics uses heuristics for motion planning. Logistics and shipping plan routes with informed guidance rather than pure costs.

In each of these settings the pattern is the same: a state space too large to enumerate, a heuristic that encodes domain knowledge (straight-line distance for navigation, piece-safety evaluation for chess, traffic-aware estimates for shipping), and a search that prunes everything the heuristic shows to be unprofitable. Chess makes the point most starkly — Deep Blue evaluated up to 200 million positions per second, but a blind search of $1 0^{43}$ positions would run longer than the age of the universe; every heuristic cut was essential.

4.4.5 Variants of A*

Beyond plain A* there are complex variations. Iterative deepening A* (IDA*) is one — a teaser from the webinar, not a course topic, but worth knowing about. Simplified memory-bounded A* (SMA*) focuses on memory optimization. Combining heuristics (the weighted form above) and learning heuristics are two more directions, explored below.

Formalize — the two memory-focused cousins. IDA* is to A* what iterative deepening is to depth-first search: it repeats a depth-first search with an increasing f-cost cutoff (instead of a depth cutoff), so it keeps only the current path in memory — $O (b d)$ space instead of A*'s full frontier — at the price of regenerating nodes across iterations. SMA* goes further: it bounds the frontier to a fixed memory size and, when the limit is reached, drops the worst node and remembers its backed-up value so the search can recover it later if needed. Both trade the memory of A* against recomputation, and both stay optimal as long as the heuristic is admissible. The weighted combination $f (n) = g (n) + W \cdot h (n)$ from Section 4.1 and the learning-based heuristics of Section 4.6 are the other two directions the session names.

Recap + bridge: A heuristic is an educated guess that turns "search everywhere" into "search promising places" — essential because state spaces explode exponentially, and powerful because pruning skips whole branches without examining them. The section now turns from why heuristics exist to where they come from: how you extract them from domain experts and how you invent them when the experts run dry.

Real-world: GPS navigation systems compute routes over maps with tens of millions of junctions in milliseconds — the practical demonstration that heuristic search, not exhaustive exploration, is what powers everyday navigation; the same informed-search engine also guides the robotic arms in warehouses and the route optimizers in shipping fleets.

4.5 Getting Heuristics from Domain Experts

Hook: You cannot phone an expert and ask "what should my heuristic be?" — the expert will ask you questions first. This section is about which questions you must be able to answer before the expert can help, and what to do when the expert's advice still fails.

4.5.1 What to Tell the Expert

Before an expert can advise on heuristics, they need the full problem story. That means the PEAS description — performance measure, environment, actuators, and sensors. It means the environment types: dynamic or static, stochastic or deterministic, observable or partially observable. It means the problem-solving agent formulation — the initial node, goal node, transitions, and costs. And it may mean the agent architecture you plan to use, such as simple reflexive, utility-based, or goal-based. Give several experts the same story, collect their heuristics, and compare the results.

Formalize — the ingredients of the story. PEAS spells out the agent's world: the performance measure says what counts as success (arrive fast, save fuel, both?), the environment is what the agent senses and acts upon, the actuators are how it changes the world, and the sensors are how it observes it. The environment types sharpen the picture — is the world changing under the agent (dynamic) or frozen (static)? Do actions have guaranteed outcomes (deterministic) or random ones (stochastic)? Can the agent see everything relevant (fully observable) or only part (partially observable)? Then the problem formulation pins down the search itself: initial state, goal test, transition model, and path cost. The expert's heuristic must respect all of this — a heuristic that assumes a static map is useless in a dynamic traffic environment, and a heuristic designed for one goal set may mislead for another.

The discipline of telling several experts the same story matters: heuristics are opinions until measured, and opinions differ. Collecting a small portfolio of candidates from independent experts — rather than one expert's single number — gives the comparison machinery of Section 4.3 something to rank.

4.5.2 The Three Skills of Heuristic Design

Designing heuristics takes three kinds of skill. Foundation: understanding the heuristic properties — admissibility, consistency, and dominance (the superset-subset idea). Design: creating effective heuristic functions for novel AI problems and domains — this is a design art; you experiment, and you build experience on common problems. Implementation: building and analyzing search algorithms like A*, IDA*, and SMA*; implementing them gives the deepest understanding. In your own industry problems you design, implement, and test the heuristic in a test environment, then iterate.

The three skills stack: without the foundation you cannot judge a candidate; without design experience you cannot produce good candidates; without implementation you cannot test either. The session's point is that the deepest understanding comes from building the search algorithm and watching how the heuristic steers it — reading about A* and tracing A* are different levels of skill.

4.5.3 The Iterative Design Loop

Everything so far happens at design stage: design the heuristic, test it, and see how good it performs in a test environment. If the results are bad — even though the values were admissible and consistent — go back to the experts, take a bigger sample, and try new heuristics. It is an iterative process, not a one-shot "pick an algorithm and it works" story. Your role is to become an architect of intelligent search, building more efficient and capable AI systems that can tackle real-world complexity.

Formalize — the loop. The workflow is a cycle: (1) formulate the problem story; (2) collect candidate heuristics from experts; (3) check admissibility and consistency on a sample problem where true costs are known; (4) compare candidates by dominance, effective branching factor, and measured search cost; (5) deploy in a test environment; (6) if performance is bad, return to the experts with more or better data and a new sample — never ship the first heuristic that merely passes the checks, because "passes the checks" is about correctness, not about how little the search explores.

4.5.4 What If the Expert Is Wrong?

Experts make mistakes. When a check fails, return the failure to the expert and ask for course correction, or pick a better SME. And it is not always about chasing optimality: if no admissible and consistent heuristic can be found, you still go with what you have, because something is better than uninformed search that gives you nothing.

Pitfalls of the expert pipeline. (1) Asking the expert without the problem story — you get a guess about a different problem. (2) Treating expert values as facts: Section 4.2's node 2 (60 promised, 50 true) is exactly the expert error the sample-problem checks exist to catch. (3) Stopping at the first admissible candidate — admissible is the floor, not the goal; informativeness decides which of several admissible candidates to ship. (4) Chasing perfect heuristics forever: if the experts cannot produce admissible and consistent values, an informative inadmissible one still beats blind search — weighted A* in Section 4.1 exists precisely for that trade.

Exam note: heuristic design shows up in assignments and in some exam questions — expect to be asked for "all possible heuristics" for a given problem, and the sessions ahead keep adding examples of exactly that.

Recap + bridge: Experts are the first source of heuristics, but they need the full problem story (PEAS, environment, formulation), their work must be checked and iterated, and they can be wrong. When experts run out of ideas entirely — the novel problem nobody has experience with — the next section supplies the systematic replacements: relax the problem, and the easy version's optimal solution becomes a heuristic for the hard one.

Real-world: this is how modern product teams actually build search systems — a route-optimization team interviews its dispatchers (the domain experts), encodes their rules of thumb, validates on historical routes with known best costs, and iterates in a staging environment before the heuristic ever touches live orders.

4.6 Designing Heuristics: Relaxed Problems

Hook: What do you do when a problem is new, nobody has experience with it, and no expert can hand you a heuristic? You cheat — but legally: you make the problem easier on purpose, solve the easy version exactly, and let the easy answer serve as the guess for the hard version.

4.6.1 The Core Idea

When a problem is novel and experts cannot give good heuristics, relax the problem. Create a simpler version by removing some rules — a classic move borrowed from theoretical computer science. For a tile puzzle, if tiles could teleport or move through each other, the puzzle would be easy to solve. The cost of solving the easy version becomes a heuristic for the hard version. You first solve the simpler version, then go for the harder one.

Intuition + analogy: The professor's picture: "if tiles could teleport or move through each other the puzzle would be easy to solve" — the teleporting version takes zero skill, its exact solution is cheap to compute, and its answer (how far every tile still has to travel even with magic) is a perfect lower bound on how far it must travel without magic. The analogy maps cleanly: the real problem's moves are a subset of the easy problem's moves, so the easy problem can never need more moves than the real one. Where the analogy breaks: solving the easy version must itself be cheap — if relaxing makes the problem harder to solve, the "heuristic" becomes more expensive than the search it is meant to speed up.

4.6.2 Why Relaxation Yields Admissible Heuristics

Formally: take the original problem and a relaxed version where a constraint is removed. In the tile puzzle, the constraint "you can only move into the empty cell, and no diagonal moves" can be relaxed in several ways — allow tiles to move anywhere, allow diagonal moves, allow tiles to pass through each other. Each relaxed version has a bigger state space: removing restrictions makes the state space of the relaxed problem a supergraph of the original state space. With fewer constraints, more states become legal, so the space grows.

The relaxed problem's optimal cost becomes the heuristic:

$h (n) = cost of the optimal solution to the relaxed problem from n$

Since the relaxed problem has more options, its optimal cost can never be larger than the original's, so this heuristic cannot overestimate — admissible by construction. A curious side effect: the problem itself becomes simpler to reason about, yet the state space grows, so exploring the solution space takes more computation. Relaxation trades solver simplicity for search-space size.

Formalize — the admissibility argument, completed. Let $P$ be the original problem and $P^{'}$ the relaxed one, so that the state space of $P^{'}$ is a supergraph of the state space of $P$ : every edge of $P$ is also an edge of $P^{'}$ , and $P^{'}$ may add more. Any solution of the original problem is so also a solution of the relaxed problem (the same moves are still legal). So the relaxed problem's optimal cost can only be smaller or equal:

$h (n) = paths in P^{'} min cost \leq paths in P min cost = h^{*} (n)$

for every node $n$ — exactly the admissibility inequality of Section 4.2. Also, because $h$ is an exact cost for the relaxed problem, it obeys the triangle inequality over the relaxed graph's edges, and since every original edge is a relaxed edge, the same inequality holds on the original graph — the heuristic is not only admissible but consistent. One extra condition matters: the relaxed problem must be solvable without search, otherwise the heuristic's values are expensive to get. Relaxing one constraint at a time also gives you the relaxation family the exam asks about — each single removed constraint yields one candidate heuristic.

Worked example — the three relaxations of the 8-puzzle move. Write the real rule as: a tile can move from cell X to cell Y if X is adjacent to Y and Y is blank. Remove conditions one by one:

Relax "Y is blank" → tiles may slide onto occupied cells as long as they move to an adjacent cell. The cheapest way to fix the puzzle under this rule is to walk each tile to its goal cell along grid steps: summing the per-tile shortest walks gives the Manhattan distance heuristic $h_{2}$ .
Relax "X is adjacent to Y" → tiles may hop into the blank from anywhere. The exact cost of this version is the number of tiles that are not already in place: the misplaced-tiles heuristic $h_{1}$ .
Relax both → any tile may go anywhere; the exact cost counts the tiles still not on their goal cells (same as $h_{1}$ in this case) — the coarsest of the three guesses.

Sense-check: each relaxed problem has more legal moves than the last, so its optimal cost is smaller or equal at every node — and indeed $h_{1} (n) \leq h_{2} (n)$ always holds on top of both being $\leq h^{*} (n)$ : the more you relax, the weaker (and cheaper) the heuristic.

4.6.3 Pattern Databases

A second route is pattern databases: solve a small part of the puzzle first — say a 4-tile or 8-tile sub-puzzle — and save every possible configuration and its cost in a database. While the AI searches, it looks up the answer in the table. This is dynamic programming, not plain caching: you solve smaller instances, store the values, and reuse them over and over. In a live system this can run as a scheduled job — a nightly refresh of what the AI has learned — so the running system consults the database instead of relying on the original heuristics alone.

Formalize — subproblems become heuristics. Choose a subset of the tiles (say tiles 1–4 plus the blank in the 8-puzzle) and ignore the rest. The cost of getting just those tiles into their goal positions is a lower bound on the cost of the whole puzzle — every move the subproblem requires is a move the full puzzle also needs. The pattern database stores that exact subproblem cost for every possible arrangement of the chosen tiles: for a 4-tile-plus-blank pattern there are $9 \times 8 \times 7 \times 6 \times 5 = 15, 120$ patterns. The database is built once by searching backward from the goal and recording the cost of each new pattern encountered — that backward construction is the dynamic programming: smaller instances solved, values stored, reused on every future puzzle. Lookup is $O (1)$ per state during search. Combining several pattern-database heuristics by taking their maximum (Section 4.3.4) routinely cuts the nodes expanded on random 15-puzzles by a factor of 1,000.

4.6.4 Landmarks

A third route is landmarks. Imagine routing with GPS: computing a path between every pair of streets is too hard, so the system picks a few landmark points in the area — "come to this mall, come to this signal, then I will guide you" — and pre-computes distances to them. Comparing your current position with the landmarks estimates the distance to your destination. Puzzle solvers work the same way: speed-solvers of Rubik's Cube reach a known landmark configuration, from which they know the goal is, say, 10 to 18 moves away. It is a memory trick — tutorials teach the landmark moves — and computers solve the cube the same way. The technique also appears in Sudoku and colored puzzles. Real-world: GPS navigation is the everyday version of landmark heuristics, and even a Braille Rubik's Cube exists — a visually impaired solver holds a record for solving the cube in under a minute with the same landmark technique.

Formalize — the math of landmarks. Pre-compute, for each landmark $L$ , the exact optimal cost $C^{*} (v, L)$ from every node $v$ to $L$ . Then a quick estimate of the distance from $n$ to the goal through the nearest landmark is

$h_{L} (n) = L \in Landmarks min (C^{*} (n, L) + C^{*} (L, goal))$

The practical power: precomputation happens once and is amortized over billions of user queries — this is how online map services return cost-optimal driving directions on maps with tens of millions of junctions in milliseconds. One caveat the professor's GPS picture glosses over: this simple landmark estimate can overestimate (it assumes you travel through a landmark, which may not be the best route), so it is an informative but not guaranteed-admissible heuristic; the textbook's differential variant $h_{DH} (n) = max_{L} ∣ C^{*} (n, L) - C^{*} (goal, L) ∣$ restores admissibility by subtracting the two landmark distances instead of adding them. For the exam, the key idea is the one the professor stresses: pick a few key points, pre-compute distances to them, and estimate any other distance by comparing with those points.

4.6.5 Learning Heuristics from Experience

The AI itself can learn to search better. Meta-level learning is the AI thinking about its own thinking: it reviews the search paths it took and learns to avoid dead ends and unhelpful states in the future. This is problem-specific — these techniques are not general algorithms usable on any problem. Feature learning is another mode: the AI solves thousands of random puzzles — Sudoku, Rubik's-style cubes, tile puzzles — and looks for patterns. Features such as how many tiles are out of order turn out to be strong predictors of the final cost, and the AI can combine several such features into one mathematical formula that guides the search. Pattern databases are one form of learning heuristics from experience, since the learned values get precomputed and reused.

Formalize — features into formulas. Experience produces examples: for each solved puzzle, the state and its true remaining cost. From those, the learner estimates a formula. The textbook's standard form is a linear combination of features:

$h (n) = c_{1} x_{1} (n) + c_{2} x_{2} (n)$

where $x_{1} (n)$ is one feature (say the number of misplaced tiles) and $x_{2} (n)$ another (say the number of adjacent tile pairs that are not adjacent in the goal); the constants $c_{1}, c_{2}$ are fit to the observed data. Both constants come out positive — more misplaced tiles and more broken adjacencies genuinely mean farther from the goal. The honest caveat: this learned guess is close to the truth on average but is not guaranteed admissible, and if the search is run against a non-admissible heuristic, optimality is traded for speed.

4.6.6 Learned Heuristics as Neural Networks

Modern versions learn the heuristic with a deep neural network. You train the network to predict the cost to the goal from a representation of the current state, and then the network itself plays the role of h(n). The reference paper for this session does exactly that for grid domains — Sokoban, mazes with teleports, and sliding puzzles. A* keeps its formula with the learned network:

$f (n) = g (n) + h (s, θ)$

where $s$ is the current state and $θ$ are the network's parameters; convolutional layers extract features from the grid, and the network's output feeds into $f (n)$ . Greedy best-first search drops $g (n)$ entirely and uses only the network's $h$ . Real-world: learned heuristics matter most in games, where state spaces are enormous and manual heuristic design is tricky. In this course the topic stays at this level — the machine can create heuristics too — while the deep learning machinery itself belongs to other courses. Exam note: even so, assignments and exams expect you to design a heuristic, or several, by hand.

Formalize — what the network replaces. The function $h (s, θ)$ is a learned approximation of the cost-to-goal: the state $s$ (a grid, e.g., a Sokoban level) is fed through convolutional layers that extract spatial features, then a fully connected layer outputs a single number that A* treats exactly like any other heuristic value. The parameters $θ$ are tuned on thousands of already-solved instances of the domain. In the session's reference paper, the network-learned heuristic is plugged into A* (with $α = β = 1$ in the merit function $f = α g + β h$ ) and into greedy best-first search (with $β = 1$ , $α = 0$ ), and the learned values steer the search successfully across Sokoban, mazes with teleports, and sliding puzzles — grid domains whose states are naturally represented as tensors. The trade-off: neural-network heuristics are typically not admissible, so they buy speed in giant state spaces at the price of the optimality guarantee.

Recap + bridge: When experts run dry there are four systematic routes — relax the problem (easy version's exact cost becomes an admissible, even consistent, heuristic), precompute subproblem costs (pattern databases, built like dynamic programming), precompute distances to landmarks (the GPS trick), and learn the heuristic from experience (feature formulas, or a neural network $h (s, θ)$ inside A*). The next two sections take all of this down from the abstract to the concrete: two worked design problems — N-Queens and the tile puzzle — where the session builds and compares actual heuristics by hand.

Real-world: Google Maps and Waze effectively run landmark precomputation over road graphs; Rubik's Cube speed-solvers — human and machine — use landmark configurations; and game studios now train network heuristics for NPC navigation in massive open worlds, exactly the A*-with-learned- $h (s, θ)$ pattern of the session's reference paper.

4.7 Heuristic Design in Practice: The N-Queens Problem

Hook: You have four queens and a 4×4 board. Which states are hopeless and which are one move from the goal? This section turns the abstract machinery — formulation, relaxation, counting heuristics — into a worked design exercise, and it builds the exact bridge to the local search of the next session.

4.7.1 Problem Definition

The N-queens problem: given an N × N chess board and N queen pieces, place the queens so that no queen attacks any other. Two queens attack each other if they share a row, a column, or a diagonal. N can be 4, 8, or 100 — any size; the session worked the 4-queens case (a 4 × 4 board, four queens). A legal goal state has each queen in a cell with nothing else in its row, column, or diagonals. This problem is the bridge to the next session, which starts local search — hill climbing and genetic algorithms — so it matters.

4.7.2 Problem Formulation

Formulate it as a search problem. Initial state: where the queens currently sit — describe it as a vector like $v_{1}, v_{2}, v_{3}, v_{4}$ , where $v_{i}$ holds the row of the queen in column $i$ , or with coordinates, or with cell numbers 0 through 15. Actions: place a queen in any non-occupied cell — you cannot stack two queens in one place. Transition model: a move is valid only if the resulting position is legal — no superimposed queens, no shared row, column, or diagonal. Goal test: no queen attacks any other. Path cost: the transition costs plus the valid queens. The number of possible states in this kind of queen problem is

$N!$

— N factorial.

Formalize — why $N!$ and what the representation buys. The vector form $(v_{1}, v_{2}, v_{3}, v_{4})$ fixes one queen per column, so a state is a choice of one row per column. If rows may not repeat (a queen must not share a row with another), the states are exactly the permutations of the N rows: $4! = 24$ states for the 4-queens case, $8! = 40, 320$ for 8 queens, and $N!$ in general. If rows were allowed to repeat, the count would instead be $N^{N}$ — the "one row per column" constraint is what collapses the count to the factorial. The vector representation also kills two of the three attack conditions automatically: with one queen per column and distinct rows, no two queens share a column or a row, and only diagonal attacks remain to check — the search only ever needs to test $v_{i}$ against $v_{j}$ via $∣ v_{i} - v_{j} ∣ = ∣ i - j ∣$ .

4.7.3 Relaxed Versions of N-Queens

Relaxation applies here too. The original problem has three constraints: two queens may not share a row, a column, or a diagonal. Remove one — say, allow several queens in the same column — and the configuration becomes a legal relaxed state. The state space of the relaxed problem is a supergraph of the original state space because restrictions were removed; the space grows, and that growth is exactly what relaxation means.

Q: Does an increase in state space simplify the problem?

A: In a sense, yes — the problem becomes easier to solve. But because the state space has grown, exploring the solution space takes more computation: more states, a bigger search tree. The problem gets simpler while the search gets costlier.

This is the session's recurring paradox, first seen in Section 4.6: relaxation makes each individual search cheaper to reason about (fewer conditions to respect) but the space you must search grows. The relaxed version is never the algorithm you run — it is the machine that manufactures a valid heuristic for the real problem, because its optimal cost is a lower bound on the real cost.

4.7.4 Designing Heuristics: The Six Conflict Pairs

With four queens there are exactly six unordered queen pairs that could conflict: Q1–Q2, Q1–Q3, Q1–Q4, Q2–Q3, Q2–Q4, Q3–Q4. Saying "Q1 attacks Q2" is the same pair as "Q2 attacks Q1", so duplicates are dropped. For each pair, the conflict may come through a row, a column, or a diagonal — the type does not matter for counting. Three heuristics came up in the session:

H1: the number of non-conflicting pairs of queens.
H2: the number of conflicting pairs of queens.
H3: the number of safe queens — queens that nobody attacks.

For a 4-queen state, H1 can range from 0 to 6. Six means all pairs are non-conflicting — the goal state. Five or four means close to the goal. Zero means every queen attacks every other — a very bad state. So H1 is maximized, H2 is minimized, and H3 is maximized. Whether a heuristic should be min or max depends on what it counts, exactly as discussed in Section 4.3.5.

Formalize — the three counts and their directions. H1 counts the good pairs (not attacking) → maximize, 6 = goal. H2 counts the bad pairs (attacking) → minimize, 0 = goal; note H2 is just the complement of H1, $H 2 = 6 - H 1$ , so the two carry identical information and one can be dropped. H3 counts the safe queens → maximize, 4 = goal. All three are cheap to compute (at most six pair checks) and each is a truthful guide in the closeness sense: a state near the goal has most pairs clean, and the counts grow as the configuration approaches the goal. The directions differ, which is the professor's warning from Section 4.3.5 in action: read what the count measures before deciding min or max.

4.7.5 Worked Example: Three Heuristics on Four Configurations

The session evaluated four configurations (and noted that many more similar ones exist; in all of them Q4 sat in a fixed cell). The counts came out as follows.

Configuration 1: Q1 and Q3 attack each other — the only conflicting pair. That leaves 2 non-conflicting pairs and just 1 safe queen (Q2, which nobody attacks).

Configurations 2, 3, and 4: no conflicting pair at all — 3 non-conflicting pairs and 3 safe queens each.

Scope note on the counting: the counts cover the three non-fixed queens Q1–Q3 (the pairs Q1–Q2, Q1–Q3, Q2–Q3 and the safety of Q1–Q3), because Q4 sat in a fixed cell throughout and its pairs were excluded from the tally. If all six pairs were counted, the raw numbers would shift (a clean state would score 6, not 3), but the rankings the heuristics produce — configuration 1 worst, the other three equal-best — stay identical, which is what the search consumes.

The three designs agree in what they indicate. H1 and H3 say the same thing from two lenses — H1 looks at each pair and asks whether it conflicts; H3 looks at each queen and asks whether it is attacked. The values differ (2 versus 1, or 3 versus 3), but the ranking is identical, so H1 and H3 are really the same heuristic and one of them can be ignored. H2 simply inverts H1: fewer conflicts is better.

Sense-check: on configuration 1 the story hangs together — Q1 and Q3 fight each other, Q2 is untouched, and Q4 sits fixed and irrelevant to the tally; every measure flags this state as bad. On configurations 2–4 all three measures read "best in class," so the heuristic cannot distinguish among them and the search is free to pick any one — a real, visible limit of these counts.

4.7.6 Using the Heuristics to Prune

Why go through all this counting? Without heuristics, from any state you generate many children — move one coin, get a new state — and explore all of them until you hit the goal. With the heuristics, you gain one insight: configuration 1 is bad, with 2 non-conflicting pairs and 1 safe queen, while the other three are promising, with 3 non-conflicting pairs and 3 safe queens each. So configuration 1 gets pruned and never expanded; among the three promising ones, pick any one and keep going. The heuristic converts "explore everything" into "explore the promising branch", which is the entire point of informed search.

4.7.7 Student Questions and Answers

Q: This works for game-like settings where we know the rules. What about real-world problems?

A: You have to create the rules yourself — that is problem formulation. Real-world assignments give you a vague statement and a real-world context; you decide what is possible, what is not, what the goal state should be, and then design heuristics for it. In organizations, customers tell you what their use case allows, what it forbids, and what they want to achieve.

Recap + bridge: N-Queens is the full design loop in miniature — formulate ( $N!$ states as permutations), relax (drop a constraint, the space grows, admissibility follows), count (six pairs → H1/H2/H3, min or max by what they measure), and prune (configuration 1 cut before expansion). This exact problem returns next session as the first playground of local search — hill climbing and genetic algorithms are designed around the same "score every state, prefer better scores" idea — which is why the professor flags N-Queens as important rather than merely illustrative.

Exam note: expect heuristic design questions that ask for all possible heuristics for a given problem — the six-pair decomposition (H1, H2, H3 and their min/max directions) is the model answer pattern for N-Queens. The N-Queens problem is important because local search builds directly on it — if it is not fully understood, revisit it.

Real-world: N-Queens is the textbook face of constraint satisfaction; the same "count what conflicts, prune what scores badly" pattern appears in real systems — placing radio masts so their frequency bands do not interfere, scheduling exam rooms so no student sits two papers at once, and laying out VLSI chip components so no two blocks collide.

4.8 Heuristic Design in Practice: The Tile Puzzle

Hook: A blank square, eight numbered tiles, and a goal you can describe in one sentence. The tile puzzle is the perfect laboratory for the session's design lesson: three different heuristics for the same state, three different costs and powers — and one of them is a trap.

4.8.1 Problem Definition and Formulation

The tile puzzle (the 8-puzzle): a 3 × 3 grid holds eight numbered tiles and one blank. A move slides a neighboring tile into the blank — up, down, left, or right — and the goal state has the numbers 1 through 8 in order, with the blank in its home cell. The session started from a given state and asked for heuristics that score any state by how close it is to the goal.

Formulate it first. Initial state: any random configuration — if none is given, choose one. Actions: move the blank to a neighboring cell; down, left, right, and up are the only moves. Transition model: the diagram of possible children; from a corner the blank has two moves, from an edge cell three. Path cost: the distance traveled. Goal test: below.

Formalize — the shape of the state space. Only the blank actually moves; a tile "slides" only when the blank arrives next to it. The branching factor is the number of neighbors of the blank's cell: 2 in a corner, 3 on an edge, 4 in the center — so the transition model is literally a function of where the blank sits. Of the $9! = 362, 880$ arrangements of nine pieces, exactly half are reachable from any given start ( $9! /2 = 181, 400$ ), because every slide is a transposition of the blank with a tile, and each move flips the permutation parity. The 8-puzzle is small enough for blind search; its big sibling, the 15-puzzle, is not — that was the state-space explosion of Section 4.4.

4.8.2 The Goal Test: Location Plus One

A neat trick defines the goal test. Number the cells −1, 0, 1, 2, 3, 4, 5, 6, 7, with −1 where the blank belongs in the goal. The goal condition: for every cell, the cell number plus one equals the tile value sitting there. Cell −1 must hold the blank, cell 0 must hold tile 1, cell 1 must hold tile 2, and so on up to cell 7 holding tile 8:

$value at cell k = k + 1 for every cell k \in {- 1, 0, 1, \dots, 7}$

Check a random state: cell 0 holds 7, but $0 + 1 = 1$ — fail. Cell 5 holds 4, but $5 + 1 = 6$ — fail. Cell 4 holds 5, and $4 + 1 = 5$ — one cell passes. Only if every cell passes is it the goal. If you label the blank's cell 0 instead of −1, the test shifts accordingly — the labels and the test must agree.

Worked example — the goal test in action. Label the cells −1 to 7 left-to-right, top-to-bottom, with the blank's goal cell at −1. A state with tile 7 in cell 0 fails immediately: $0 + 1 = 1 \neq = 7$ . Tile 4 in cell 5 fails: $5 + 1 = 6 \neq = 4$ . Tile 5 in cell 4 passes: $4 + 1 = 5$ . The test is a loop over all nine cells — one failing cell is enough to reject the state. Sense-check: in the goal state itself, cell −1 holds the blank, cell 0 holds tile 1, ..., cell 7 holds tile 8, so each equation $k + 1 = k + 1$ holds on both sides — the required value and the actual value are the same number — and the test passes exactly for the goal.

4.8.3 The Transition Model and Why Heuristics Matter

From any state you keep generating children, and comparing each child with the goal is uninformed search. The session's example state produced two children at the first move (the blank had two options), then three children each at the next level — six children in total. You do not want to explore all six blindly. A heuristic tells you which children are bad so you can prune them. To get that far you only need to generate one or two levels of children — that itself is the transition model — and then the heuristic design begins.

4.8.4 Three Heuristics for the Tile Puzzle

Three heuristics were proposed in the session.

H1: the number of misplaced tiles. Zero misplaced means the goal state; a large count means far away. Counting the blank or not is a choice — with the blank it can reach 9; without it, at most 8. Either way the count can never exceed the number of cells, so it never overestimates — admissible.
H2: the Manhattan distance of the empty tile only — how many steps the blank needs to reach its goal position, moving only up, down, left, and right (no diagonals).
H3: the Manhattan distance of all labeled tiles, summed. The Manhattan distance between two cells is the number of grid steps separating them: the horizontal difference plus the vertical difference:

$d ((x_{1}, y_{1}), (x_{2}, y_{2})) = ∣ x_{1} - x_{2} ∣ + ∣ y_{1} - y_{2} ∣$

where $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ are the two cells' grid coordinates, and the vertical bars are absolute values, so a 2-column gap and a 3-row gap score $2 + 3 = 5$ regardless of direction. For each tile, compare where it sits in the current state with where it sits in the goal; that step count is its Manhattan distance, and summing over all tiles gives H3. Since each tile's Manhattan distance is the shortest possible route to its goal cell, the sum can never overestimate the real moves — admissible. One student noted a per-tile distance can never exceed 4 on the 3 × 3 board, which is right.

Formalize — why each is admissible, and how they rank. H1: a misplaced tile needs at least one real move, so the count underestimates the true number of moves. H2: the blank needs at least its own Manhattan distance of moves before it can sit home, so the blank's distance is a valid lower bound — admissible, but weak: it ignores every numbered tile. H3: each real slide moves exactly one tile one grid step, so a tile at Manhattan distance $d$ needs at least $d$ slides; summing gives a lower bound on total moves — admissible, and per tile $d \geq 1$ whenever the tile is misplaced, so H3 dominates H1 in the sense of Section 4.3.2: $H 3 (n) \geq H 1 (n)$ for every state $n$ , meaning A* with H3 never expands more nodes than A* with H1. The blank's distance, in turn, is at most the all-tile sum, so H2 is the weakest of the three.

4.8.5 Worked Example: Manhattan Distances for Six Configurations

The empty-tile heuristic (H2) — four configurations. For the empty-tile heuristic, four of the six children were evaluated. The blank was two steps from its goal cell in two of them, four steps in one, and already at its goal cell in one — the values 2, 4, 2, 0. During the counting, one of the 2s was first read as 4 and then corrected to 2 — a good reminder to recount: an arithmetic slip in a heuristic evaluation changes which child the search trusts. The configuration with the blank already home scores 0 and looks most promising under this heuristic — but that promise is false, as Section 4.8.7 shows.

The all-tiles heuristic (H3) — the first configuration. The per-tile distances were: tile 1 → 1 step from its goal cell, tile 2 → 4, tile 3 → 3, tile 4 → 1, tile 5 → 0 (already placed), tile 6 → 4, with tiles 7 and 8 computed the same way. The sum of the known six tiles is $1 + 4 + 3 + 1 + 0 + 4 = 13$ so far, and the full sum adds the distances of tiles 7 and 8. No single tile can exceed 4 on the 3 × 3 board, and the running total already shows this state is far from solved.

The misplaced-tile heuristic (H1) — the same configuration. Only tile 5 sits correctly — 8 of the 9 cells are misplaced (the 7 remaining numbered tiles plus the out-of-place blank; without counting the blank the score is 7, and 9 is the maximum possible when the blank counts). Very far from the goal.

Sense-check: the three heuristics agree on this state — H3 scores it badly because most tiles travel multiple steps, H1 scores it badly because almost every cell is wrong — and H3's per-tile sum can never fall below H1's count, exactly as dominance predicts.

Every configuration gets all three counts the same way, and for all three heuristics the smaller value is better, with 0 meaning the goal — unlike the queens problem, where the non-conflicting-pairs heuristic had to be maximized.

4.8.6 Choosing Among the Three: The Trade-Off

The three heuristics differ in cost and in power. H1 (misplaced tiles) is the cheapest: plain counting. H2 (empty-tile Manhattan) costs a bit more. H3 (all-tile Manhattan) is the most computationally intensive — you sum distances over every tile — and it is also the most informative: it ranks all six children instead of just judging the blank. Time-consuming, but valuable: with only one heuristic available, you compute it for each child and pick the most promising. H3 is a superset of H1 in the information sense — a tile with Manhattan distance 0 is placed, and the misplaced count is implied by the sum. The trade-off is computation against informativeness.

Scope — when the trade-off flips. H3's extra power is worth its cost when the frontier is small and the heuristic is evaluated few times; in a huge search, an expensive heuristic evaluated at every node can slow the search more than it prunes, which is why Section 4.3 listed "fast to compute" as a fourth property of a good heuristic. In practice, real solvers precompute H3-style values (pattern databases of Section 4.6.3) so the expensive computation happens once and lookups are cheap.

4.8.7 The Empty-Tile-Only Heuristic Is a Bad Idea

H2 has a serious flaw, exposed by a student's observation. It looks only at the blank. A configuration where the blank sits at its goal cell scores 0 — but every numbered tile may be wrong, so the puzzle is far from solved. If you then move the blank to fix the other tiles, the heuristic stops being 0, because it must be recomputed at every stage, for every state, until all tiles are placed. "Once it is 0, we won't touch it" does not work. So the empty-tile-only heuristic is not an appropriate one; prefer H3, or at least H1. H3 is the preferred heuristic, with the caveat of its higher computation.

Pitfalls of the tile-puzzle heuristics. (1) The blank-only trap: a home blank can coexist with every tile misplaced, so H2 = 0 can be dead wrong about "nearly solved" — the professor's explicit warning, triggered by a student's observation. (2) Forgetting to recount: heuristic values are functions of the state, not fixed labels; a state that scores well can become bad after a move, so recompute at every stage until every tile is placed. (3) Mixing the counting conventions: decide whether the blank counts in H1 (max 9 with blank, 8 without) and keep the same convention across all states, or comparisons between states become meaningless. (4) Forgetting diagonal moves are forbidden when computing Manhattan distances — a tile two cells diagonally away needs 2 steps, not 1.

4.8.8 Student Questions and Answers

Q: If I use the empty-tile-only heuristic and the empty tile is in the correct place, the heuristic seems complete — but the problem is not solved.

A: Correct — that is exactly the flaw. The blank may be home while every other tile is wrong. If you move the blank to fix the others, this heuristic stops being 0 at the next state. So this heuristic is a bad one; use the all-tile Manhattan or the misplaced count instead.

Q: Can we say that in this problem the all-tile Manhattan is a superset of the misplaced-count heuristic?

A: Yes — you can derive the misplaced count from the Manhattan distances, because a tile with distance 0 is already placed. The superset carries more information.

Q: To find a heuristic, are we actually solving a few steps toward the solution first?

A: Yes. When you explain the problem to an expert, the transition model is part of the story: start from the initial state, take one or two steps, and see where you are heading. Generating one or two children gives you a fair idea, and then the heuristic design starts from there.

Q: Once a heuristic reaches 0, we do not touch it again?

A: No — you recompute at every stage. A state that scores well can become bad after a move, as the empty-tile example shows. Keep recomputing until all heuristics are in their proper place.

Q: In the exam, we will get only the initial state and the goal state, right? The rest we solve?

A: That is right. Sometimes even the initial state is not given — only the goal. Then you assume any random state as the initial state and proceed.

Q: Why does tile 4 need two steps in either direction?

A: Because diagonal moves are forbidden. Tile 4 can reach its goal cell via either route — down then right, or right then down — and both take two steps, so its Manhattan distance is 2.

Recap + bridge: The tile puzzle shows three heuristics for one problem — H1 the cheap count, H2 the cheap-but-blind blank-only distance, H3 the expensive all-tile Manhattan that dominates both — and one hard lesson: a heuristic that scores 0 without meaning "solved" is a trap, and every value must be recomputed at every state. This closes the session's arc: trust (admissibility and consistency), comparison (dominance, $b^{*}$ , weights), sourcing (experts, relaxation, patterns, landmarks, learning), and design practice (queens and tiles). The tile puzzle also returns as the testbed for the learned and pattern-database heuristics of Section 4.6, and its goal-test trick (location plus one) is exactly the kind of neat construction exam questions reward.

Exam note: on the exam you will be given the initial state and the goal state; sometimes only the goal state, in which case you assume a random initial state and proceed. Be ready to compute all three heuristics for a given configuration — the empty-tile distance, the all-tile Manhattan sum, and the misplaced count — and to say which you would use and why.

Real-world: the 8- and 15-puzzles are the standard benchmark families for heuristic search research — every new idea in Sections 4.3 and 4.6 (dominance, pattern databases, learned $h (s, θ)$ ) is shown working on these puzzles before it goes anywhere else; the same grid-with-obstacles geometry powers robot vacuum navigation and warehouse robot planning, where Manhattan-style distances are the everyday admissible heuristics.

Exam Guidance Summary

Exam note: a recurring question type gives a graph with heuristic values and asks you to apply greedy best-first search and A* (a star), then check admissibility and consistency for all values. Expect to compute both properties for every node and every edge — that is the exercise pattern of this session. Drill the five-node example of Section 4.2 until the enumeration is mechanical: list the directed paths to the goal, sum and take the minimum, compare, and then run every edge through $h (i) \leq c (i, j) + h (j)$ .

Exam note: another question type hands you a problem and asks for the state representation, the relaxed versions of the problem, which constraint got relaxed, and heuristics for the relaxed versions. Work those as practice questions before the exam — the 8-puzzle's three relaxations (drop "Y is blank" → Manhattan; drop "X is adjacent" → misplaced count; drop both) and N-Queens' row/column/diagonal removals are the model answers.

Exam note: heuristic design shows up in assignments and in some exam questions — "what are all possible heuristics?" Be ready to propose several for one problem, as done for the queens and tile puzzles, and to state each heuristic's min/max direction and which one dominates.

Exam note: the N-Queens problem is important — if it is not fully understood, revisit it, because local search builds directly on it. The state vector, the $N!$ count, the six conflict pairs, and the H1/H2/H3 scores are the pieces the next session will reuse.

Exam note: on the exam you will be given the initial state and the goal state; sometimes only the goal state, in which case you assume a random initial state and proceed.

Exam note: the webinar series — covering variants like IDA* — is an add-on to the course, not directly exam material, though the videos are worth viewing for context around memory-bounded search.

Study advice: each deck ends with a few self-help exercises covering only that class's material, about 15–20 minutes each. Do them weekly and discuss them in the forum instead of piling everything up. A sample or previous paper will be shared after the 8th session; the syllabus has changed a lot, so use old papers only after preparing, and do not fixate on them. The classes move fast, so revisit the material and, if needed, watch the video at 0.75× speed with paper and pen in hand.

Study advice: if you run out of expert-supplied heuristics, the fallbacks are learned heuristics and relaxed problems — reduce the problem, solve the relaxed version, and turn its solution into a heuristic. Asking an expert is fine, but when the expert also cannot help, this is exactly the path to take.

Key Industry Applications

Real-world: pathfinding — maps, games, and navigation systems — relies on informed search rather than raw exhaustive exploration. Every turn-by-turn route, every game NPC that walks around obstacles, and every fleet-routing decision is an A*-family search with a domain heuristic behind it.

Real-world: Deep Blue, the chess computer that beat Garry Kasparov, used heuristic functions — a famous example of heuristic-guided game search. It evaluated up to hundreds of millions of positions per second, but the heuristics deciding which branches mattered were what made the search tractable — the same pattern powers modern chess and Go engines.

Real-world: robotics uses heuristics for motion planning, and logistics and shipping plan routes with informed guidance rather than pure costs. Warehouse robots navigate grid floors with Manhattan-style heuristics; delivery fleets optimize routes with traffic-informed estimates in the evaluation function.

Real-world: GPS navigation systems use landmarks — pre-computed distances to key points — to estimate routes without solving every street pair; even speed-cubing and Sudoku solvers use landmark configurations the same way. This is the everyday technology of Section 4.6.4: millions of junctions, a few dozen landmarks, milliseconds per query.

Real-world: in industry, heuristics are not deployed directly — teams design them on sample problems, validate admissibility and consistency, test in a test environment, and iterate before production. Pattern databases can be refreshed by scheduled jobs, so a live system keeps improving its heuristic lookups — the design-phase discipline of Section 4.2.7 running continuously.

Real-world: learned heuristics — including neural networks trained to predict cost-to-go from a state representation — matter in games with huge state spaces; the session's reference paper evaluates network-learned heuristics inside A* and greedy best-first search on grid domains such as Sokoban, mazes with teleports, and sliding puzzles. The same recipe (a learned $h (s, θ)$ steering a classic search) is the pattern behind modern game AI and robotics planning stacks.

ACI Lecture 4 notes · Heuristics: Evaluation, Design, and Relaxation

Artificial Computational Intelligence· postgraduate· 2026-08-13

Sections Breakdown

1Recapping Informed Search: Greedy Best-First Search and A*

The two informed strategies — greedy best-first and A* — their evaluation functions, and the closeness principle that drives everything that follows.

2Admissibility and Consistency

The two trust properties — per-node optimism and the per-edge triangle inequality — checked by hand on a five-node graph, with a proof that they make A* optimal.

3What Makes a Good Heuristic

Admissible, consistent, informative; dominance and the effective branching factor; blending experts with trust weights and min-or-max conventions.

4What Is a Heuristic and Why We Need One

Etymology and definition, the state-space explosion, pruning, real-world uses of informed search, and variants of A*.

5Getting Heuristics from Domain Experts

The full problem story experts need, the three skills of heuristic design, and the iterative design-test loop.

6Designing Heuristics: Relaxed Problems

Why relaxing constraints yields admissible heuristics, plus pattern databases, landmarks, and learning heuristics from experience.

7Heuristic Design in Practice: The N-Queens Problem

Formulation, relaxed versions, and three counting heuristics over the six conflict pairs, with a worked ranking and pruning.

8Heuristic Design in Practice: The Tile Puzzle

The goal test, the transition model, and three heuristics with worked Manhattan-distance scores on six configurations.

9Exam Guidance Summary

Recurring question patterns, the examinable skills for queens and tile puzzles, and study advice.

10Key Industry Applications

Pathfinding, Deep Blue, robotics motion planning, logistics, GPS landmark precomputation, and learned heuristics.

Postgraduate students in Artificial Computational Intelligence

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Recapping Informed Search: Greedy Best-First Search and A*

Must-know: Greedy best-first search uses f(n)=h(n) only and is not guaranteed optimal; A* uses f(n)=g(n)+h(n) and is optimal when the heuristic is admissible.

$f (n) = g (n) + h (n)$

⚠️ Top pitfall: Trusting an unevaluated heuristic: an expert-supplied guess that overestimates leads the search to a suboptimal solution (Arad-to-Bucharest greedy path is 450 vs optimal 418).

Self-check: In the Arad-to-Bucharest trace, why did A* not expand Bucharest when it first appeared at f = 450?

Connects to: 4.2, 4.3.

Admissibility and Consistency

Must-know: Admissibility: h(n) <= h*(n) for every node. Consistency: h(i) <= c(i,j) + h(j) for every edge. Both must be checked per node and per edge on directed graphs following the arrows; one failure breaks optimality of A*.

$h (i) \leq c (i, j) + h (j)$

⚠️ Top pitfall: Enumerating paths against the arrow direction, comparing against max instead of min path cost, or skipping edges out of the goal (they always pass with positive costs since 0 <= cost + anything).

Self-check: On the five-node graph, why does edge 5->1 violate consistency while node 5 is still admissible?

Connects to: 4.1, 4.3, 4.4.

What Makes a Good Heuristic

Must-know: Three properties of a good heuristic: admissible, consistent, informative. Dominance: if h_A(n) >= h_B(n) for all n, ignore h_B. Effective branching factor: N+1 = 1 + b* + (b*)^2 + ... + (b*)^d; smaller b* is better.

$h (n) = α \cdot h_{1} (n) + β \cdot h_{2} (n)$

⚠️ Top pitfall: Assuming every heuristic is minimized ('lower is better') — N-Queens heuristics that count non-conflicting pairs must be maximized.

Self-check: Why does h2 (Manhattan sum) dominate h1 (misplaced tiles) in the 8-puzzle?

Connects to: 4.1, 4.2, 4.7, 4.8.

What Is a Heuristic and Why We Need One

Must-know: A heuristic is an educated guess encoded as a function from state to estimated remaining cost. State spaces explode exponentially (15-puzzle: 16!/2 reachable states), which makes informed search and pruning necessary.

⚠️ Top pitfall: Confusing pruning with cutting a promising branch — pruning skips only branches that cannot improve the answer (nodes with f > C*).

Self-check: Why could Deep Blue beat Kasparov without exploring the whole chess state space?

Connects to: 4.1, 4.5, 4.6.

Getting Heuristics from Domain Experts

Must-know: Before asking an expert for a heuristic, provide the full problem story (PEAS, environment types, agent formulation). Heuristic design is iterative: design, test in a test environment, go back to experts with a bigger sample if results are bad.

⚠️ Top pitfall: Treating expert-supplied heuristic values as facts instead of checking them on a sample problem where true costs are known.

Self-check: What must you tell a domain expert before they can propose a heuristic?

Connects to: 4.2, 4.6.

Designing Heuristics: Relaxed Problems

Must-know: The relaxed problem's optimal cost is an admissible (and, being exact for the relaxed problem, consistent) heuristic because the relaxed state space is a supergraph: every original solution is a relaxed solution, so h(n) <= h*(n). Relax one constraint at a time to build a family of heuristics.

$h (n) = cost of the optimal solution to the relaxed problem from n$

⚠️ Top pitfall: Relaxing so much that the relaxed problem is hard to solve — the heuristic becomes more expensive than the search it should speed up.

Self-check: Why is the Manhattan-distance heuristic admissible for the 8-puzzle? (Which relaxation produces it?)

Connects to: 4.2, 4.4, 4.7, 4.8.

Heuristic Design in Practice: The N-Queens Problem

Must-know: N-Queens state space is N! (one queen per column, distinct rows). With four queens there are 6 unordered pairs; H1 = non-conflicting pairs (max), H2 = conflicting pairs (min, complement of H1), H3 = safe queens (max). Configuration 1 (Q1-Q3 conflict) is pruned.

$N!$

⚠️ Top pitfall: Treating every heuristic as minimized: H1 and H3 count good things and must be maximized; H2 counts bad things and is minimized.

Self-check: Why is H1 essentially the same heuristic as H3, and H2 just the complement of H1?

Connects to: 4.3, 4.6, 4.8.

Heuristic Design in Practice: The Tile Puzzle

Must-know: Goal test: value at cell k = k+1 for cells labeled -1..7 (blank home at -1). H1 = misplaced tiles (max 8 without blank, 9 with), H2 = blank-only Manhattan (bad heuristic: blank home does not imply solved), H3 = all-tile Manhattan sum (best, dominates H1). All three are minimized, 0 = goal.

$d ((x_{1}, y_{1}), (x_{2}, y_{2})) = ∣ x_{1} - x_{2} ∣ + ∣ y_{1} - y_{2} ∣$

⚠️ Top pitfall: The empty-tile-only heuristic: blank at its goal cell scores 0 while every numbered tile is wrong; and not recomputing the heuristic after every move (a well-scoring state can become bad).

Self-check: Why is H3 admissible even though it never accounts for tiles blocking each other?

Connects to: 4.3, 4.4, 4.6.

Exam Guidance Summary

Must-know: Question patterns: apply GBFS and A* then check admissibility/consistency per node and per edge; state representation + relaxed versions + which constraint relaxed + heuristics; all possible heuristics for queens and tile puzzles.

Connects to: 4.2, 4.6, 4.7, 4.8.

Key Industry Applications

Must-know: Informed search and heuristic evaluation are what make navigation, game AI, robotics planning, and logistics tractable; industry validates heuristics on sample problems before deployment.

Connects to: 4.4, 4.6.

Previous LectureLecture 03 · Uninformed and Informed Search

Next LectureLecture 05 · Local Search Algorithms and Introduction to Evolutionary Algorithms

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

4.1 Recapping Informed Search: Greedy Best-First Search and A*

4.1.1 From Blind Search to Informed Search

4.1.2 Greedy Best-First Search versus A*

4.1.3 Where Heuristics Come From and the Closeness Principle

4.2 Admissibility and Consistency

4.2.1 Admissibility: The Optimistic Heuristic

4.2.2 Consistency: The Triangular Inequality

4.2.3 Worked Example: Checking Admissibility on a Five-Node Graph

4.2.4 Worked Example: Checking Consistency Edge by Edge

4.2.5 What the Two Properties Guarantee

4.2.6 Student Questions and Answers

4.2.7 The Design-Phase Workflow

4.3 What Makes a Good Heuristic

4.3.1 The Three Properties: Admissible, Consistent, Informative

4.3.2 Choosing Among Multiple Heuristics: Dominance and Superset

4.3.3 Effective Branch Factor

4.3.4 Combining Heuristics with Weights

4.3.5 Min or Max? It Depends on the Problem

4.3.6 The Helpful Guide

4.4 What Is a Heuristic and Why We Need One

4.4.1 Etymology and Definition

4.4.2 The State-Space Explosion Problem

4.4.3 Pruning

4.4.4 Real-World Uses of Informed Search

4.4.5 Variants of A*

4.5 Getting Heuristics from Domain Experts

4.5.1 What to Tell the Expert

4.5.2 The Three Skills of Heuristic Design

4.5.3 The Iterative Design Loop

4.5.4 What If the Expert Is Wrong?

4.6 Designing Heuristics: Relaxed Problems

4.6.1 The Core Idea

4.6.2 Why Relaxation Yields Admissible Heuristics

4.6.3 Pattern Databases

4.6.4 Landmarks

4.6.5 Learning Heuristics from Experience

4.6.6 Learned Heuristics as Neural Networks

4.7 Heuristic Design in Practice: The N-Queens Problem

4.7.1 Problem Definition

4.7.2 Problem Formulation

4.7.3 Relaxed Versions of N-Queens

4.7.4 Designing Heuristics: The Six Conflict Pairs

4.7.5 Worked Example: Three Heuristics on Four Configurations

4.7.6 Using the Heuristics to Prune

4.7.7 Student Questions and Answers

4.8 Heuristic Design in Practice: The Tile Puzzle

4.8.1 Problem Definition and Formulation

4.8.2 The Goal Test: Location Plus One

4.8.3 The Transition Model and Why Heuristics Matter

4.8.4 Three Heuristics for the Tile Puzzle

4.8.5 Worked Example: Manhattan Distances for Six Configurations

4.8.6 Choosing Among the Three: The Trade-Off

4.8.7 The Empty-Tile-Only Heuristic Is a Bad Idea

4.8.8 Student Questions and Answers

Exam Guidance Summary

Key Industry Applications

ACI Lecture 4 notes · Heuristics: Evaluation, Design, and Relaxation

Sections Breakdown

Exam Revision Notes

Recapping Informed Search: Greedy Best-First Search and A*

Admissibility and Consistency

What Makes a Good Heuristic

What Is a Heuristic and Why We Need One

Getting Heuristics from Domain Experts

Designing Heuristics: Relaxed Problems

Heuristic Design in Practice: The N-Queens Problem

Heuristic Design in Practice: The Tile Puzzle

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat