Heuristics, greedy search, beam search, A*, admissibility, consistency, creating heuristics by relaxation, and Iterative Deepening A* (IDA*).
Printed copy: all task answers below are revealed. On screen they are hidden behind a click, which is how you should use them first.
it's very important to realize that in this type of problem a note in this tree actually represents an entire path um you took from the starting node.(Lecturer, T2). The transcripts are machine-transcribed, so "note" is "node" and, further down, "horistic" is "heuristic". Quotes are reproduced exactly as transcribed.
Uniform cost search (UCS) is complete and optimal, and the deck says so on p.4. Its defect is stated on the same slide: it "explores options in every direction" and has "no information about goal location". It grows equal-cost rings outward from the start. If your goal happens to lie east, UCS still spends effort going west, because nothing in g(n), the cost already paid, says anything about where the goal is.
Deck p.6 gives the one-line contrast that the whole Part hangs on:
That last point is not decoration. A heuristic is problem-specific by construction. Change the problem formulation and you must redesign the heuristic.
The right-hand picture is the shape we want. Suppose you build a heuristic so aggressive that the expanded region becomes a thin line straight to the goal. Which of the four properties (complete, optimal, time, memory) is the one you are most likely to have destroyed, and which algorithm from this Part behaves exactly like that?
Optimality. A thin cone means the search is following h alone and never reconsiders cheaper alternatives it walked past. That is greedy search (deck pp.10-16), which is not optimal. Narrowing the cone by discarding frontier entries, as beam search does, costs you completeness as well (p.18).
Why: A* keeps the cone wide enough to "hedge its bets to ensure optimality", which is the wording on p.35.
Notation used for the rest of this Part, taken from deck pp.21 and 24:
| Symbol | Meaning |
|---|---|
| g(n) | Backward cost: the cost of the path from the root to n. This is what UCS sorts on. |
| h(n) | Forward cost: your estimate of the remaining cost from n to the nearest goal. This is what greedy sorts on. |
| h*(n) | The true optimal cost from n to the closest goal. You almost never know it. Deck p.24: "We seldom know h*(n) but might have a heuristic approximation h(n)". |
| f(n) | g(n) + h(n). This is what A* sorts on. |
Constructed, in the sample paper's format (true/false, +0.5 / −0.25 / 0)
For the Romania problem with straight-line distance to Bucharest as the heuristic, the path Arad, Sibiu has f = 393.
The boxed column is straight-line distance to Bucharest. Arad reads 366; the road distance Arad to Bucharest along the best route is 418. Why is straight-line distance guaranteed never to overestimate, for every city on this map at once?
Because a road is a path in the plane between the same two points, and no path between two points is shorter than the straight line between them. So straight-line distance ≤ road distance for every city, which is exactly 0 ≤ h(n) ≤ h*(n), the definition of admissible on p.28.
Small internal detail worth noticing so it does not confuse you in the exam: the table on this slide (p.7) lists Fagaras as 178, while the beam-search tree on p.17 prints 176 next to Fagaras. (The greedy tree on p.11 prints numbers only under the nodes it did not select, and Fagaras is a selected node there, so it carries none.) Nothing in either trace turns on the difference; use whatever number the question prints.
Deck p.8 gives the Pac-Man version: Manhattan distance (the number of grid steps if you ignore walls, |Δx| + |Δy|) and Euclidean distance (straight line). The slide's example is 10 + 5 = 15 for Manhattan and 11.2 for the straight line. Deck p.25 poses the comparison ("Is Manhattan better than straight-line distance?") without settling it on that slide; the answer arrives with the dominance rule on p.44 and the relaxation argument in Section 10 below.
For the second puzzle on this slide (1 5 2 / 8 _ 4 / 3 6 7), the slide gives h2 = 1 + 2 + 0 + 3 + 1 + 1 + 1 + 1 = 10. What is h1, the number of misplaced tiles, for that same second puzzle, and which tile is responsible for the "0" term in the h2 sum?
h1 = 7. Tile 2 is already in its goal square (top right), so it contributes 0 to the Manhattan sum and is the one tile not counted as misplaced. All seven others are wrong, giving 7. For the top puzzle (7 2 4 / 5 _ 6 / 8 3 1) every tile is wrong, so h1 = 8 and h2 = 3+1+2+2+3+2+2+3 = 18.
Note that the blank square is never counted in either heuristic.
Deck p.12: "Strategy: expand a node that you think is closest to a goal state. Priority queue ordered by heuristic, that estimates distance to nearest goal for each state." Structurally, greedy is UCS with g replaced by h. Everything else, the frontier of paths, the priority queue, the expansion loop, is unchanged.
The slide states both faces of it: "Common case: Best-first takes you straight to a goal. Worst-case: like a badly-guided DFS." The worst case is the important one. Greedy commits to whatever looks nearest and never asks what that commitment already cost.
The slide asserts "No! Resulting path to Bucharest is not the shortest." Using the road distances printed on the map on this same slide, compute the cost of the path greedy found and the cost of the optimal path, and say in one sentence which piece of information greedy ignored.
Greedy returns Arad → Sibiu → Fagaras → Bucharest = 140 + 99 + 211 = 450.
The optimal route is Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest = 140 + 80 + 97 + 101 = 418. (Verified against the full map by shortest-path computation: 418 is the true optimum from Arad.)
Greedy ignored g. At Sibiu it compared h(Fagaras), printed as 178 in the p.7 table and as 176 on the p.17 beam-search tree, with h(Rimnicu Vilcea) = 193, and took Fagaras either way, without noticing that the Fagaras branch then needs a single 211 km leg while the Rimnicu Vilcea branch needs 97 + 101 = 198 km.
This 450 versus 418 gap is the standard "give a counterargument if something is not optimal" answer for greedy, and the lecturer named that skill explicitly (see the exam-signal box at the end).
Greedy is a priority queue ordered by h; DFS is a stack (LIFO). They are different data structures. So why does the slide say greedy's worst case is "like a badly-guided DFS"? What has to be true of h for the two to coincide?
If h decreases as you go deeper along a wrong branch, then each newly generated child of the deepest node looks best and is selected next. Selection by minimum h then produces exactly the same expansion order as a stack: it dives. The queue is still a priority queue, but the priorities happen to reproduce LIFO behaviour.
Why it matters: greedy inherits DFS-like failure modes (very deep, very poor paths) without inheriting DFS's small memory footprint, since greedy still stores the full frontier.
Exercise session 3, question 1.1 (path finding), verbatim
"Given the figure on the last page, find a path from the square labeled with 'S' to the square labeled with 'G', without passing through any of the black squares. Legal steps (in order of importance) are: up, left, right, down (each to an adjacent square). Apply the following tree search algorithms with loop detection." The two algorithms listed are depth-first search and "Greedy search with a suitable heuristic."
The suitable heuristic is Manhattan distance from the square to G, ignoring the black squares. The session's own solution slide is headed "Heuristic: Manhattan Distance".
Justify it, do not just name it. Every legal step changes x or y by exactly one, so any path needs at least |Δx| + |Δy| steps, and a blocked square can only force extra steps. So h ≤ h*: admissible, by the same argument the deck uses for Pac-Man on p.28.
What earns the marks: (i) the heuristic named and justified in one sentence; (ii) the frontier written as paths with h beside each entry; (iii) the loop detection stated, since the question asks for tree search with loop detection; (iv) the step order up, left, right, down used as the tie-break. That order is given "in order of importance", so it is the tie-break rule, not decoration.
The pairing with DFS is the point of the question: both algorithms dive, but DFS dives by structure (last in, first out) while greedy dives toward whatever square has the smallest Manhattan distance, which is the "badly-guided DFS" of p.12 seen from the good side.
Deck p.17 describes beam search as a variant of greedy and breadth-first search: "just like Breadth-first search, but after every level, keep only the k best paths, prune away the others", "first build next level, then prune", "just like greedy search, keep the paths in an ordered priority queue".
Order matters and is examinable: expand the entire level first, then cut down to k. If you prune before the level is complete you get a different, wrong trace.
Level 1 from Arad gives Sibiu 253, Timisoara 329, Zerind 374, so Zerind is struck. Level 2 is then built from both survivors. Which five paths exist at level 2, which two survive, and which three are struck?
Level 2 contains, from Sibiu: Arad 366, Fagaras 176, Oradea 380, Rimnicu Vilcea 193; and from Timisoara: Lugoj 440. That is five paths.
Survive (k=2 best by h): Arad-Sibiu-Fagaras (176) and Arad-Sibiu-Rimnicu Vilcea (193).
Struck: Arad-Sibiu-Arad (366), Arad-Sibiu-Oradea (380), Arad-Timisoara-Lugoj (440).
The trap: Timisoara survived level 1, so it must be expanded before any level-2 pruning happens. Lugoj is generated and only then discarded. Expanding Fagaras next reaches Bucharest, and beam search stops early because it has no optimality guarantee to protect.
Deck p.18 gives the properties. Memory: the queue always has size k, but expanding it needs room for O(k·b) children. Time: O(k·b·s) if a solution at depth s is found, otherwise O(k·b·m) for maximum depth m. Complete? No. Optimal? No. And: "Hill-climbing: k = 1".
It cuts some information for efficiency but you lose the property of completeness and optimality.(Lecturer, T3), answering a student who asked how beam search differs from greedy. He drew the contrast this way:
whereas in greedy search you still keep track of all the possible uh options(Lecturer, T3). Beam search throws options away permanently, and a discarded path can never be recovered. That is why both guarantees go at once.
Exercise session 3, question 1.2 (water jugs), archetype A5, verbatim
"Solve the water jugs problem. Given two jugs of 4 liter and 3 liter respectively, fill the 4 liter jug with 2 liter of water. Find a good heuristic and perform hill-climbing. This algorithm is effectively the depth-first algorithm with loop detection, but successor nodes are added to the frontier after sorting them by increasing heuristic cost. Explain how the behaviour of this algorithm is distinct from that of greedy search."
The distinction that earns the mark: hill-climbing sorts locally, among the children of the node it just expanded, and pushes them onto a stack; greedy sorts globally, in one priority queue holding every path currently on the frontier. So hill-climbing can never jump back to a promising path in a different branch, greedy can. The deck reaches the same object from the other side: hill-climbing is beam search with k = 1 (p.18).
Classic mistake: writing that hill-climbing "is greedy search". It is not. It differs in the scope of the sort, and that is the entire content of the question.
On the heuristic half: the sheet says "Find a good heuristic", so the choice is yours. Write it down explicitly before you start tracing, because every ordering decision further down is graded against whatever you wrote.
Deck p.19 poses it as a question: "Can we do informed search, like greedy search, but with optimality guarantees like Uniform Cost Search?" Deck p.21 answers with the definition:
Deck p.24 states the intent behind that sum: expand a node n most likely to be on an optimal path, that is, one with lowest g(n) + h*(n). Since h* is unknown, substitute the estimate h. The slide's summary line is: "A* = tree search with priority queue ordered by f(n) = g(n) + h(n)".
Edge costs: S-A 3, S-D 4, A-B 4, A-D 5, B-C 4, B-E 5, D-E 2, E-F 4, F-G 3. Heuristics: S 11, A 10.4, B 6.7, C 4, D 8.9, E 6.9, F 3, G 0.
Compute f(SA) and f(SD). Which does A* expand second, and which would greedy expand second?
f(SA) = 3 + 10.4 = 13.4. f(SD) = 4 + 8.9 = 12.9. A* expands SD.
Greedy compares h(A) = 10.4 with h(D) = 8.9 and also takes D. On this particular graph the two agree at the first branch, which is a useful reminder that a single agreeing step proves nothing about optimality. The heuristic here is unusually good: checked against the true costs, it is admissible and consistent at every arc.
The trace below is the same one drawn on the slide, written out as you would have to write it in the exercise exam. It was produced by executing A* on the p.22 graph, not estimated.
| Step | Selected | Frontier after this expansion (path : f) |
|---|---|---|
| 0 | - | S : 11.0 |
| 1 | S | SD : 12.9 | SA : 13.4 |
| 2 | SD | SDE : 12.9 | SA : 13.4 | SDA : 19.4 |
| 3 | SDE | SDEF : 13.0 | SA : 13.4 | SDEB : ? | SDA : 19.4 |
| 4 | SDEF | SDEFG : 13.0 | SA : 13.4 | SDEB : ? | SDA : 19.4 |
| 5 | SDEFG | goal path selected from the frontier, return S D E F G, cost 13 |
(a) What is f(SDEB)? Show g and h separately.
(b) At step 4 the goal path SDEFG is already on the frontier with f = 13.0. Why is it still correct to say A* "stops" here, and under what small change to the numbers would stopping at that moment have been wrong?
(a) g(SDEB) = 4 + 2 + 5 = 11, h(B) = 6.7, so f(SDEB) = 11 + 6.7 = 17.7. That is the 17.7 printed on the slide.
(b) A* stops when a goal path is selected from the frontier, not when it is generated. Here SDEFG has f = 13.0, which is the frontier minimum (SA is 13.4), so it is selected immediately and the two events coincide. If h(A) had been, say, 8 instead of 10.4, then SA would sit at f = 11.0 and would have to be expanded first; stopping at generation would have returned a path before checking a cheaper alternative.
This is the single most common trace error in this archetype: stopping when the goal is generated instead of when it is expanded.
2023 sample exercise exam, Q1 (2 points), verbatim
"The following image depicts a simple search space. S represents a start node. G1, G2, and G3 are all possible goal nodes. The numbers shown in parentheses are the heuristic estimate at their associated node, the edge weights are the costs of the transition. Execute each of the following search algorithms until termination and write down their frontier at every step. Where appropriate employ the familiar left-to-right order or lexicographic order as tie-breaker." The four listed are "1. Depth-first search: 2. Breadth-first search: 3. Greedy-search: 4. A*:". Traces 3 and 4 are the Part 5 half; traces 1 and 2 are Part 4.
The figure, read off the paper: S (9) has three children drawn left to right, A (2) along an edge of cost 7, G2 (0) along an edge of cost 12, and G3 (0) along an edge of cost 11. A has one child, G1 (0), along an edge of cost 3.
3. Greedy search, frontier ordered by h:
Frontier: [S] H: [9]
Frontier: [SG2], [SG3], [SA] H: [0, 0, 2]
select SG2, it is a goal → return S G2, cost 12
G2 and G3 tie at h = 0, and the tie-break puts G2 first because it is drawn to the left of G3.
4. A*, frontier ordered by f = g + h:
Frontier: [S] F: [0 + 9 = 9]
Frontier: [SA], [SG3], [SG2] F: [7 + 2 = 9, 11 + 0 = 11, 12 + 0 = 12]
Frontier: [SAG1], [SG3], [SG2] F: [10 + 0 = 10, 11, 12]
select SAG1, it is a goal → return S A G1, cost 10
The trap the question is built around: two goal paths, SG3 at f = 11 and SG2 at f = 12, are already sitting on the frontier after the very first expansion. Apply the goal test at generation and you hand in 11 or 12; A* applies it at selection and returns 10, the true optimum. Greedy, which never looks at g, walks into the worst of the three goals at cost 12, and that 12 against 10 is the counterargument for "greedy is not optimal" on this very paper.
What earns the marks: the frontier written at every step as complete paths, the sort key printed beside each entry, and the tie-break rule named. Checked by execution: this heuristic is admissible and consistent at every arc (S to A is tight, 9 − 2 = 7 = cost; the other three arcs have slack), so A* is guaranteed optimal here and one line saying so is worth writing.
Step the same trace forward and backward in viz-informed.html, which shows g, h and f for every path on the frontier.
The question above is the archetype. The recipe that makes it mechanical:
Classic mistakes: writing nodes instead of paths; omitting the h column so the grader cannot follow your sort; forgetting the tie-break rule; stopping at goal generation in A*.
Edges: S→A costs 1, A→G1 costs 3, S→G2 costs 5. Heuristics: h(S)=7, h(A)=6, h(G1)=h(G2)=0. Run two steps in your head, then name the exact inequality that is violated and by how much.
Trace: frontier [S : 0+7 = 7], expand S, frontier becomes [SG2 : 5+0 = 5, SA : 1+6 = 7]. SG2 has the lower f, is selected, is a goal, and A* returns it with cost 5. But SAG1 costs 1 + 3 = 4, so the answer is suboptimal.
The property that fails is admissibility, at node A. The true remaining cost is h*(A) = 3, but h(A) = 6. The heuristic overestimates by 3, which makes the good branch look worse than it is. The slide phrases the failure as: actual bad solution cost SG2:5 < estimated good solution cost SA:7.
Note what did not go wrong: there is no loop, no graph, no repeated state. Pure tree search with an inadmissible heuristic is already enough to break optimality.
Deck p.28: a heuristic h is admissible (optimistic) if
0 ≤ h(n) ≤ h*(n)
where h*(n) is the true cost to a nearest goal. The exercise sheet writes the same thing as 0 ≤ h(x) ≤ c(x), with c(x) the actual cost from x to the goal. Both wordings are examinable; they are the same statement.
"Optimistic" is the useful mental handle: an admissible heuristic never claims the rest of the journey is worse than it really is. It may be far too cheerful (h = 0 is admissible for every problem), but it is never pessimistic.
The Pac-Man example is annotated 15, the Manhattan distance to the food. Complete this sentence so that it proves admissibility, and say what would have to be true of the maze for the inequality to become an equality.
"Manhattan distance ignores the walls. Every legal Pac-Man move changes x or y by one, so any real path must make at least |Δx| + |Δy| = 15 moves, and walls can only force extra moves. Therefore h = 15 ≤ h*, so h is admissible."
It becomes an equality exactly when no wall blocks a monotone staircase route, that is, when there exists a shortest path that only ever moves toward the goal in x or in y. In an empty corridor-free maze, Manhattan distance is exact.
The general principle is on p.40 and in Section 10 below: this heuristic is the exact solution cost of a relaxed problem (Pac-Man with no walls).
Constructed, in the sample paper's format (true/false, +0.5 / −0.25 / 0)
On the graph of deck p.22 (edges S-A 3, S-D 4, A-B 4, A-D 5, B-C 4, B-E 5, D-E 2, E-F 4, F-G 3, goal G), replacing h(A) = 10.4 by h(A) = 15 would leave the heuristic admissible.
Deck pp.29-34 give a three-line proof. Set-up (p.30): A is an optimal goal node, B is a suboptimal goal node, h is admissible. Claim: A will exit the frontier before B.
The proof never argues about A directly. It argues about "some ancestor n of A that is on the frontier (maybe A itself)". Why is that detour necessary, and why is the parenthetical "maybe A itself" not just a throwaway remark?
At an arbitrary moment during the search, the optimal goal path A may not be on the frontier yet, so you cannot compare f(A) with f(B) as frontier entries. What is guaranteed is that some prefix of the optimal path sits on the frontier: if no ancestor of A were on the frontier and A were not either, A would already have been expanded and returned. So the proof shows the weaker, always-available statement "n is expanded before B", then repeats it.
"Maybe A itself" covers the boundary case where the prefix is the whole path, which is what makes the induction close: all ancestors of A expand before B, therefore A expands before B.
The three steps, in the deck's own numbering (pp.31-34):
| Step | Statement | Justification the slide prints |
|---|---|---|
| 1 | f(n) ≤ f(A) | Definition of f-cost, then admissibility of h, then h = 0 at a goal. In full: f(n) = g(n) + h(n) ≤ g(A) because h(n) never overestimates the remaining cost along the optimal path, and g(A) = f(A) because h(A) = 0. |
| 2 | f(A) < f(B) | B is suboptimal, so g(A) < g(B); and h = 0 at both goals, so f(A) = g(A) < g(B) = f(B). |
| 3 | n is expanded before B | Chaining 1 and 2 gives f(n) < f(B), and A* always selects the frontier entry with the lowest f. |
Three facts feed this proof: (i) the definition f = g + h, (ii) admissibility, (iii) h = 0 at a goal. Which step uses which? And what breaks in the p.26 counterexample?
Step 1 uses all three: the definition to write f(n) = g(n) + h(n), admissibility to get f(n) ≤ g(A), and h = 0 at a goal to turn g(A) into f(A). Step 2 uses only (iii) plus the meaning of "suboptimal". Step 3 uses only the selection rule of the priority queue.
In the p.26 counterexample admissibility fails at A, so step 1 collapses: f(SA) = 7 is larger than f(SAG1) = 4, and the frontier entry on the optimal path no longer looks cheap. Everything downstream fails with it.
Note the slide's own typo, "A* tee search is optimal". It is tree search. The proof as given assumes tree search, that is, no repeated-state handling, which is exactly the assumption Section 12 removes.
Deck p.35 puts UCS and A* side by side. UCS "expands equally in all directions". A* "expands mainly toward the goal, but does hedge its bets to ensure optimality". The bands are f-contours: the set of paths whose f value falls in a given band. In UCS, f = g, so contours are equal-cost rings around the start. In A*, adding h pulls the rings into ovals aimed at the goal.
Take a fixed problem and shrink the heuristic toward zero everywhere, h → 0. What happens to the A* picture, and what algorithm do you end up running? Now push it the other way: h = h* exactly. What does the picture become?
With h = 0 the ovals relax back into circles and A* becomes uniform cost search, since f = g + 0 = g. Deck p.44 asks exactly this: "The zero heuristic is pretty bad (what does A* do with h=0?)". Answer it with the specific algorithm, uniform cost search, not the vague "it becomes uninformed".
With h = h* the contour collapses onto the optimal path itself: every node on an optimal path has f = C*, and everything else is strictly worse, so A* walks straight to the goal. Deck p.44: "The exact heuristic is pretty good, but usually too expensive!", and computing h* means solving the search problem you were trying to solve.
So the two extremes of the heuristic scale are exactly UCS at one end and a free lunch you cannot have at the other. Everything useful lives in between.
Cover the labels. One maze has almost the whole board shaded; one has a narrow shaded band; one has a wide band aimed at the food. Which is which, and which single fact lets you separate the two banded ones?
Nearly everything shaded = uniform cost search (it ignores where the goal is). Narrow band = greedy (it follows h alone). Intermediate, goal-directed but wider than greedy = A*.
The separating fact: A* must also expand everything whose f is below the optimal solution cost, so it cannot be as thin as greedy. That extra width is precisely the price of the optimality guarantee, which is the "hedge its bets" phrase on p.35.
Deck p.38 lists where this is actually used: video games, pathing and routing, resource planning, robot motion planning, language analysis, machine translation, speech recognition, protein design, chemical synthesis.
Deck p.40 states the design rule and the theorem behind it:
The reasoning is short: extra actions can only help, so the optimal cost in the relaxed problem is no larger than in the original. And a quantity that is never larger than the true optimal cost is, by definition, admissible. This is why relaxation is the standard heuristic factory rather than a trick: it produces admissibility for free, without a separate proof each time.
(a) At 12 steps from the goal, UCS expands 3.6 × 106 nodes on average and A*TILES expands 227. What is the factor? (b) The slide asks "Why is it admissible?" for the misplaced-tiles count. Give the relaxation that makes it admissible in one sentence.
(a) 3 600 000 / 227 ≈ 15 900, about four orders of magnitude. The same comparison at 4 steps is 112 / 13 ≈ 8.6 and at 8 steps 6300 / 39 ≈ 162, so the advantage grows sharply with depth. This is the practical argument for spending effort on heuristic design.
(b) Relax the puzzle so that any tile may be lifted out and dropped directly into its goal square in one move. Then every misplaced tile needs exactly one move, so the relaxed optimal cost equals the misplaced count, and by the p.40 theorem that count is admissible for the real puzzle. A useful image for this relaxation: it is how a child "solves" the puzzle, by pulling the tiles out and pushing them back in the right places.
Careful with the table's rows: this deck's rows are UCS and A*TILES here, and A*TILES and A*MANHATTAN on p.43. There is no iterative-deepening row anywhere in this table.
The slide's relaxation is "any tile could slide any direction at any time, ignoring other tiles". (a) Which constraint of the real 8-puzzle has been dropped, and which has been kept? (b) The start state is 7 2 4 / 5 _ 6 / 8 3 1 and the goal is _ 1 2 / 3 4 5 / 6 7 8. Verify h(start) = 18 by listing the eight per-tile distances.
(a) Dropped: a tile may only slide into the blank square (so no other tile may be in the way). Kept: a tile still moves one square at a time, horizontally or vertically. Because one constraint is kept, this relaxation is tighter than the misplaced-tiles relaxation, so it gives larger values while remaining admissible.
(b) Reading left to right, top to bottom, and skipping the blank: tile 7 needs 3, tile 2 needs 1, tile 4 needs 2, tile 5 needs 2, tile 6 needs 3, tile 8 needs 2, tile 3 needs 2, tile 1 needs 3. Sum = 3+1+2+2+3+2+2+3 = 18, matching the slide. (Checked by computing every tile's goal coordinates.)
Payoff in the table: A*MANHATTAN expands 12 / 25 / 73 against A*TILES' 13 / 39 / 227. At 12 steps that is a further factor of about 3.1.
Deck p.44 defines dominance: h1 ≥ h2 if h1(n) ≥ h2(n) for all n. "Roughly speaking, larger is better as long as both are admissible." Larger is better because a larger admissible h is closer to h*, so fewer nodes have f below the optimal cost, so fewer nodes get expanded. That is exactly the effect measured in the pp.42-43 tables.
And the combination rule: "What if we have two heuristics, neither dominates the other? Form a new heuristic by taking the max of both: h(n) = max(h1(n), h2(n)). Max of admissible heuristics is admissible and dominates both!" The slide's example is the number of knight's moves from A to B, with three candidate heuristics, each rounded up to the correct parity: h1 = Manhattan distance / 3, h2 = Euclidean distance / √5, h3 = (max x or y shift) / 2.
Let h1 and h2 both be admissible and let h = max(h1, h2). Prove (a) h is admissible, (b) h dominates both. Then say why "max" and not "sum".
(a) For any n, h(n) equals either h1(n) or h2(n). Each of those is ≤ h*(n) by admissibility. So h(n) ≤ h*(n). Admissible.
(b) h(n) = max(h1(n), h2(n)) ≥ h1(n) and ≥ h2(n) by the definition of max. Dominates both.
Why not sum: the sum can exceed h*. Concretely, if h1 = h2 = h* then h1 + h2 = 2h*, which overestimates whenever h* > 0. The max is the largest combination that is guaranteed to stay under the ceiling, which is why it is the one the slide recommends.
Exercise session 3, question 1.4 (pancake problem), verbatim
"There are four pancakes with different sizes. These should be flipped such that the largest pancake is on the bottom, and all pancakes on top of it are decreasing in size. A spatula can flip any stack of pancakes by choosing any point between two pancakes in the current stack. Assume that the cost for each flip is 1, regardless of the number of pancakes on the spatula." Then: "Find a suitable heuristic for this problem. Is your heuristic suitable for an A* algorithm? Why?"
A heuristic that works: count the breakpoints, that is, the places in the stack where two neighbouring pancakes are not consecutive in size, counting the plate as a neighbour of the bottom pancake (so a bottom pancake that is not the largest contributes one breakpoint).
Why it is admissible, which is the half of the question that carries the marks: a flip cuts the stack at one point and reverses everything above it, so it changes exactly one neighbouring pair. One flip can therefore remove at most one breakpoint, and a state with k breakpoints needs at least k flips. That is h ≤ h*. It is the relaxation argument of this section in a different costume: the count is the exact cost of the relaxed problem in which a single move repairs any one adjacency you like.
The trap: "number of pancakes not in their final position" is the obvious first answer and it is not admissible. Take the four-pancake stack 4 3 2 1 read from the top down: all four are out of place, so that heuristic says 4, but one flip of the whole stack finishes the problem. Checked by exhaustive search over all 24 stacks of four pancakes with unit flip cost: the misplaced count overestimates on 11 of them, while the breakpoint count never does.
So the answer to "is your heuristic suitable for A*" is not a bare yes. Say: yes for tree search because it is admissible, and also for graph search because it is consistent, since one flip changes one adjacency and therefore moves h by at most 1 while costing 1, which is exactly h(x) ≤ h(x′) + c(x, x′), with h = 0 on the sorted stack. (Both properties checked over the full 24-state space.)
This is exercise-session archetype A4 and it is also the Part 5 item on the sample theory exam. Both questions are embedded below, after the verdict table they are answered from: the exercise-session version asks you to judge five combinations of admissible heuristics (the sum, the product, the max, the min and the average), and the sample theory item takes one of them and asks it as true or false.
The table below states each verdict with the reason. Every "no" is backed by an explicit counterexample and every "yes" by a one-line proof; the counterexamples were checked numerically (a state with h* = 10 and three admissible heuristics f = 6, g = 7, h = 8), and 200 000 randomly generated admissible triples produced zero violations for max, min and average.
| Combination | Admissible? | Reason, and the counterexample where it fails |
|---|---|---|
| f + g + h | No | 6 + 7 + 8 = 21 > 10. The exercise solution states it generally: if f = g = h then the sum equals 3·f(s), which may overestimate. Adding admissible quantities adds their slack together. |
| f · g · h | No | 6 × 7 × 8 = 336 > 10. Solution wording: if f = g = h the product is f(s)3, which may overestimate. Note the word "guaranteed" in the question: the product happens to stay below h* for values under 1, but it is not guaranteed, so the answer is No. |
| max(f, g, h) | Yes | max = 8 ≤ 10. Proof: the max equals one of the three, and each is already ≤ h*. Solution wording: "the heuristic can be at most one of the three already admissible heuristics". This is also the best of the five: it dominates all three inputs. |
| min(f, g, h) | Yes | min = 6 ≤ 10. Same proof. But it is admissible and worse: it is dominated by each input, so it expands no fewer nodes than any of them. Admissible does not mean good. |
| f/3 + g/3 + h/3 | Yes | (6+7+8)/3 = 7 ≤ 10. Proof: an average of three numbers cannot exceed the largest of them, so it is at most max(f, g, h), which is admissible. Solution wording: "a linear interpolation of the three other functions, meaning it can not be higher than the highest heuristic". |
2023 sample theory exam, MC 1.3 (the Part 5 slot), verbatim
If h1 and h2 are both admissible heuristics, then max(h1, h2) is also admissible and equally good or better than h1 as well as h2.
Exercise session 3, question 1.3 (admissible heuristics), archetype A4, verbatim
"If f(s), g(s) and h(s) are all admissible heuristics, are the following heuristics guaranteed to be optimistic? Why?"
No, No, Yes, Yes, Yes, in the printed order. The reasons are the third column of the table above, and the word that settles the first two is guaranteed: one state where the combination exceeds h* is enough to answer No.
What earns the marks is the reason, not the verdict, and one line each is enough. For the two No answers give the session's own argument: if f = g = h then the sum is 3·f(s) and the product is f(s)3, either of which may overestimate. For the three Yes answers say that the result can never exceed max(f, g, h), and that the max is at most h* because each input is.
The follow-up to expect: which of the three admissible ones is best. Max, and the reason is dominance (p.44), not admissibility: min and the average are exactly as admissible and expand at least as many nodes.
You are given two admissible heuristics h1 and h2 and someone hands you h = h1 + h2, which overestimates on some states. Repair it in three different ways so that the result is admissible again, and rank the three by how many nodes A* will expand.
Three repairs: (1) max(h1, h2); (2) (h1 + h2)/2, the average; (3) min(h1, h2). All three are admissible by the table above.
Ranking by nodes expanded, fewest first: max, then average, then min, because max ≥ average ≥ min pointwise, and a larger admissible heuristic dominates and therefore expands no more nodes. So the repair that costs you the least search is the max, which is the rule printed on p.44.
Everything so far assumed tree search. Real state spaces are graphs: the same state is reached by several paths. Part 4 handled that with a simple test, refuse any path whose last state has been seen before. That test is no longer safe here, and this is the highest-value single fact in the Part.
we now have a new version of the loop breaking test, our formerly simple check that we used until now does not hold anymore when we are dealing with heuristics and a search graph instead of a search tree, a more advanced check that allows a new c if it is cheaper.(Lecturer, T4), on deck p.46. "a new c" is the node C in the slide's example.
The graph: S→A costs 1, S→B costs 1, A→C costs 1, B→C costs 2, C→G costs 3. Heuristics: h(S)=2, h(A)=4, h(B)=1, h(C)=1, h(G)=0. The optimal solution is S A C G at cost 5; the alternative S B C G costs 6.
Checked against the true costs, this heuristic is admissible at every node (h*(S)=5, h*(A)=4, h*(B)=5, h*(C)=3). So the tree-search theorem of section 8 applies and A* tree search would find the cost-5 path. Nevertheless the graph-search run on the slide returns the cost-6 path. Here is the frontier trace, reproduced by execution:
| Step | Frontier (path : f) | What happens |
|---|---|---|
| 0 | S : 2 | expand S |
| 1 | SB : 2 | SA : 5 | SB is cheaper by f, expand it, mark B closed |
| 2 | SBC : 4 | SA : 5 | expand SBC, mark C closed with g = 3 |
| 3 | SA : 5 | SBCG : 6 | expand SA, mark A closed |
| 4 | SAC : 3 | SBCG : 6 | SAC has the best f in the whole frontier, but C is already closed, so the simple check discards it |
| 5 | SBCG : 6 | returned. Cost 6. The cost-5 path was thrown away at step 4. |
The reason is visible at step 4: A* reached C the expensive way first (g = 3 via B) and the cheap way second (g = 2 via A), because the inflated h(A) = 4 made the A branch look bad. A closed set assumes the first arrival at a state is the best arrival. With an admissible-but-inconsistent heuristic, that assumption is false.
Fill this 2 × 2 table before revealing. Rows: which redundant-path rule you use. Columns: which property the heuristic has. Entries: the path returned and its cost.
| h admissible only (h(A) = 4) | h consistent (h(A) = 2) | |
|---|---|---|
| closed set: block any state already expanded | S B C G, cost 6, suboptimal | S A C G, cost 5, optimal |
| path deletion: keep only the cheaper path to a state, allow re-expansion | S A C G, cost 5, optimal | S A C G, cost 5, optimal |
Only one cell fails, and it is the cell the exam asks about. Note also the cost of the fix in the bottom-left cell: re-expanding C means its descendants have to be recomputed, which is exactly the caveat printed on p.46 ("requires recalculating C's descendants").
Deck p.47 gives the two conditions side by side under the heading "estimated heuristic costs ≤ actual costs":
The exercise sheet writes the same condition as h(x) ≤ h(x′) + c(x, x′) together with h(G) = 0. Both forms are the triangle inequality: going from A to the goal cannot be cheaper by way of a detour estimate through C than the direct estimate suggests.
The slide then lists the consequences, and the derivation is printed in the boxed panel:
f(S...A) = g(S...A) + h(A)
f(S...AC) = g(S...A) + cost(A to C) + h(C)
so f(S...A) ≤ f(S...AC) holds if and only if h(A) ≤ cost(A to C) + h(C)
which is consistency, rearranged. Hence:
this consistent horistic ensures that along a path uh the f value never decreases and this is what one refers to as monotonicity.(Lecturer, T4). Also printed on Part 5 p.47, so treat this as emphasis on slide content rather than an extra.
And consistency implies admissibility.(Lecturer, T4). A one-way implication, and deck p.50 prints it too. Consistency is the stronger property: every consistent heuristic is admissible, but the p.46 heuristic shows an admissible one that is not consistent.
(a) On p.46, h(A) = 4 and h(C) = 1 with cost(A, C) = 1. The slide crosses out 4 and writes 2. What is the largest value h(A) could take and still be consistent, and why does the slide pick exactly that value?
(b) Take the p.22 graph and the solution path S D E F G. Write the f value at each prefix and confirm it never decreases.
(a) Consistency constrains h(A) from both sides, and missing the lower bound is the standard error here.
The consistent window is therefore 1 ≤ h(A) ≤ 2. Note what this rules out: h(A) = 0 is perfectly admissible, since h*(A) = 4, yet it is not consistent, because it breaks the S→A arc. Lowering a heuristic is not a safe repair.
Within the window the slide takes the largest value, 2, because among admissible heuristics a larger one dominates and therefore expands no more nodes. Checking every arc with h(A) = 2: S→A needs 2 − 2 = 0 ≤ 1 ✓, S→B needs 2 − 1 = 1 ≤ 1 ✓, A→C needs 2 − 1 = 1 ≤ 1 ✓, B→C needs 1 − 1 = 0 ≤ 2 ✓, C→G needs 1 − 0 = 1 ≤ 3 ✓. The whole heuristic is now consistent. (Checked by re-running closed-set A* on this graph at h(A) = 1, 1.5 and 2: all three return S A C G at cost 5, while h(A) = 0 and h(A) = 4 both violate an arc.)
This is exactly the shape of exercise session 3 §1.5, which asks you to say how you would modify a heuristic to make it consistent. The answer that earns the mark names the violated arc, derives the two-sided window from the arcs touching that node, and then picks the largest value in it.
(b) f(S) = 0 + 11 = 11.0, f(SD) = 4 + 8.9 = 12.9, f(SDE) = 6 + 6.9 = 12.9, f(SDEF) = 10 + 3 = 13.0, f(SDEFG) = 13 + 0 = 13.0. The sequence 11.0, 12.9, 12.9, 13.0, 13.0 is non-decreasing, as monotonicity requires. The two flat steps are the arcs where consistency holds with equality: D-E has cost 2 and h drops by exactly 2.0, F-G has cost 3 and h drops by exactly 3.
That is a useful diagnostic in the exam: a strictly decreasing f anywhere along a path is instant proof that the heuristic is not consistent, and you do not need to compute h* to say so.
The sketch has two facts. Fact 1: A* expands nodes in increasing total f value (f-contours). Fact 2: for every state s, nodes that reach s optimally are expanded before nodes that reach s suboptimally. Which of the two is the one that fails in the p.46 example, and what does the other one buy you?
Fact 2 is the one that fails on p.46: the suboptimal arrival at C (g = 3 via B) is expanded before the optimal arrival (g = 2 via A). That is exactly why the closed set then blocks the good path. Consistency is what restores Fact 2, because monotonic f means a cheaper route to a state cannot be sitting further back in the queue.
Fact 1 is what makes the closed set safe once Fact 2 holds: since f never decreases along a path and A* pops in increasing f, the first time a state is expanded you are already holding its cheapest path, so discarding later arrivals loses nothing.
Deck p.50 collects the whole result, and p.51 repeats it as the A* summary:
| Setting | Requirement on h for optimality |
|---|---|
| Tree search | Admissible |
| Graph search | Consistent |
| "Consistency implies admissibility." And: "Most natural admissible heuristics tend to be consistent, especially if from relaxed problems." (p.50) | |
2023 sample theory exam, fill-in 2.1 (1 point), verbatim, two answer boxes
"Given an A* implementation with redundant path elimination with closed sets, what is a required property of a heuristic for this algorithm to be optimal?"
"Given an A* implementation with redundant path elimination with path deletion, what is a required property of a heuristic for this algorithm to be optimal?"
Box 1: consistency (equivalently, monotonicity). Box 2: admissibility.
Why the asymmetry: a closed set commits irreversibly the first time a state is expanded, so it needs the guarantee that the first arrival is the cheapest, and only consistency provides that. Path deletion keeps whichever path to a state is cheaper and re-expands when a better one shows up, so it never destroys the optimal path and plain admissibility suffices. The 2 × 2 table above is the same fact with numbers attached: exactly one of the four cells returns a suboptimal path.
Classic mistakes: (i) writing "admissible" in both boxes, which throws away the point the question exists to test; (ii) writing "consistent" in both, which is not wrong in the sense of being insufficient but does not answer what is required; (iii) answering with an algorithm ("use path deletion") when the question asks for a property of the heuristic. The lecturer said fill-in answers "can also be short answers", and the box size signals the expected length, so a one-word answer plus one clause of justification fits.
Exercise session 3, question 1.5 (A* algorithm), archetype A4, verbatim
"Perform the A* graph search algorithm on the following figure. Explicitly write down the frontier at each iteration of the algorithm." and, under the figure: "Is this a consistent heuristic? If not, specify how you could modify the heuristic to ensure consistency."
The figure, read off the sheet. Heuristics: S 17, A 10, B 13, C 4, D 2, E 4, F 1, G 0. Edges: S-A 6, S-B 5, S-C 10, A-E 6, B-E 6, B-D 7, C-D 6, D-F 6, E-F 4, F-G 3.
No, it is not consistent. The session's own counterexample is the arc S to C: h(S) − h(C) = 17 − 4 = 13, which is more than cost(S, C) = 10. Testing all ten arcs by machine finds four violations, not one: S-A (17 − 10 = 7 > 6), S-C (13 > 10), B-E (13 − 4 = 9 > 6) and B-D (13 − 2 = 11 > 7).
And yet it is admissible everywhere. True costs to G, computed: S 18, A 13, B 13, C 15, D 9, E 7, F 3, G 0, and every printed h sits at or below its own entry (B sits exactly on 13). That is the whole point of the question, and the same point as fill-in 2.1 above: admissible does not buy you consistency, and it is consistency the closed set needs.
It bites on this very graph. Executed: A* with a closed set returns S A E F G at cost 19, while A* with path deletion returns S B E F G at cost 18, which is the optimum. With the repaired heuristic below, the closed set returns 18 as well. So before you trace, write down which redundant-path rule you are using; on this graph it decides the answer.
The repair, by the session's method: enforce h(N) ≤ c(N, P) + h(P) node by node and fix a violation by raising the neighbour's value, then sweep again until a pass changes nothing. Raising h(E) to 7 and h(D) to 6 fixes B; checking S then forces h(A) to 11 and h(C) to 7; and h(E) = 7 in turn forces h(F) to 3. Final heuristic: S 17, A 11, B 13, C 7, D 6, E 7, F 3, G 0. Verified by re-running both tests: no arc violates consistency, and every value is still at or below the true costs listed above, so it is still admissible.
The choice the solution flags: you could instead lower h(B) from 13 and edit fewer numbers, but a smaller admissible heuristic is a worse one (dominance, p.44), so the repair that keeps the heuristic informative raises the neighbours. Say which direction you moved the values, and why.
What earns the marks: name the violated arc with its arithmetic rather than asserting "not consistent", state the rule you are enforcing, remember that h(G) = 0 is part of the definition, and for the trace write the frontier as paths with g, h and f.
A*'s weakness is memory: the frontier holds every path it has generated. Deck p.53 states the fix: "get DFS's space advantage with A* time / shallow-solution advantages". Run a depth-first search bounded by an f-limit (a contour). If no solution, raise the limit and run again.
The bookkeeping rule, from the same slide, is the whole exam question: "while expanding nodes, keep track of the smallest increase in f value; use the smallest f value as the next contour." In other words the new bound is the minimum f among the paths that were rejected for exceeding the old bound. Not old bound + 1, not the average, not the maximum.
Bound = 100. Only S has f = 100. Its three children have f = 120 (A), 130 (B), 120 (C). Which nodes are expanded in this iteration, which are rejected, and what is f-new?
Expanded (within the bound): S only. Rejected for exceeding the bound: A (120), B (130), C (120). f-new = min(120, 130, 120) = 120, which is the value printed on the slide.
Trap: f-new is the minimum over the rejected paths, not over all paths seen. S's own f of 100 does not enter the minimum, otherwise the bound would never rise.
Bound = 120, depth-first, children taken left to right. List the nodes expanded, the nodes rejected with their f values, and f-new.
Expanded: S (100), A (120), C (120).
Rejected: D (140), G (125) under A; B (130); E (140), F (125) under C.
f-new = min(140, 125, 130, 140, 125) = 125, as printed.
Two details that cost marks: (i) A has f exactly 120, equal to the bound, so it is within the bound and gets expanded; the test is f > bound for rejection. (ii) G is generated in this iteration and rejected even though it is the goal, because its f of 125 exceeds the bound. Being a goal does not exempt a node from the bound.
(a) Bound = 125. Which nodes does the depth-first pass touch before it succeeds, and why is the returned solution guaranteed optimal? (b) How many times in total has S been expanded across the three iterations?
(a) Left to right: S (100, within bound), A (120, within bound), D (140, rejected), G (125, within bound and a goal) → SUCCESS, returning S A G with f = 125. C, E and F are never reached in this iteration because the search stops on success.
Optimality: every path with f < 125 was already exhausted in the earlier iterations and none contained a goal, and the bound rose by the smallest possible amount each time, so no f value was ever skipped over. Nothing cheaper than 125 exists. That is precisely why the minimal-increase rule is the one that buys optimality, and why the fixed-step δ variant on p.58 gives it up.
(b) S is expanded once per iteration, so three times. That is the redundancy the slide flags with "Isn't that wastefully redundant?" (p.53).
Deck p.58 gives the properties:
Exercise session 3, question 1.6 (IDA*), archetype A6, verbatim, both parts
"Perform IDA* on the following figure." Heuristics: S 0, A 0, B 4, C 3, D 0, G 0. Edges: S-A 10, S-B 8, S-C 9, A-D 1, B-D 4, B-G 5, C-G 5. Start S, goal G.
"What changes when you apply IDA* to a problem where the costs between nodes are all completely different, real-valued costs (e.g. Euclidean distances between exact points on a map)? Can you come up with a way to make the algorithm more efficient in this scenario? What effect does this have on its optimality?"
The trace. The bound starts at f(S) = 0 and jumps each time to the smallest f among the rejected paths, giving 0, 10, 11, 12, 13: five iterations, and the fifth succeeds with S B G at cost 13.
Two things to notice. The goal is generated one iteration before it is accepted: SBG appears at bound 12 with f = 13 and is rejected for exceeding the bound, exactly as G is on deck p.56. And the same state carries two different f values in one iteration: B reached straight from S has g = 8 and f = 12, while B reached through A and D has g = 15 and f = 19. IDA* is depth-first over paths, so both exist at once.
The real-valued part. With real-valued costs almost every path has a distinct f, so each new bound admits roughly one extra path and the number of iterations explodes. The fix is to raise the bound by at least a fixed δ: the session's solution writes the new rule as f-new ← maximum(fbound + δ, minimum({f-new} ∪ {f(P) | P is a rejected path})). Consequence: the path found is no longer necessarily optimal, but it is at most δ away from optimal. That matches deck p.58's "Delta-optimal".
Classic mistakes: setting the new bound to old bound + 1 (only correct by accident when all costs are 1); taking the minimum over all f values rather than over the rejected ones; forgetting that a node whose f exactly equals the bound is inside the bound; claiming the δ version is still optimal.
Drill the bound sequence in viz-informed.html, which replays IDA* one f-limited pass at a time.
Deck p.59 frames the entire block of Parts 4 and 5 as a set of independent choices, and says "Different choices leads to different algorithms":
and then: "Four properties of interest: Complete, optimal, time and memory-complexity." The table below assembles the Part 5 algorithms along exactly those axes, using only the properties this deck states.
| Algorithm | Frontier ordered by | Complete? | Optimal? | Memory |
|---|---|---|---|---|
| Greedy | h(n) | Worst case is "like a badly-guided DFS" (p.12), so it can dive down a wrong branch for a long time; with loop detection on a finite graph it still terminates [derived] | No (p.11) | Full frontier of paths |
| Beam (width k) | h(n) | No (p.18) | No (p.18) | Queue always of size k, expansion needs O(k·b) (p.18) |
| Hill-climbing | h(n) | No [derived: it is beam with k = 1, p.18] | No [derived, same reason] | One path |
| A* | f = g + h | Complete under the conditions carried over from UCS in Part 4, namely a finite optimal solution cost and a minimum action cost above zero [derived from p.58's "under the same conditions as UCS + Greedy/A*"] | Yes if h is admissible for tree search, consistent for graph search (pp.50, 51) | Full frontier of paths: the weak point that motivates IDA* (p.53) |
| IDA* | f-bounded DFS | "Under the same conditions as UCS + Greedy/A*" (p.58) | Same (p.58); only δ-optimal if the bound is raised by a fixed δ instead of the minimum (p.58) | O(b · C*/ε) (p.58) |
The three bullets are: reason about combinations of components and deduce their properties; execute and simulate algorithms; model search problems and define heuristics. For each, name one concrete question from the sample exam or the exercise sessions that tests it.
it's important that you can put together these algorithms and that you can reason about them. For example, if you are given a number of ingredients that you can say something about the properties along these four uh dimensions or for example give a counterargument if something is not optimal... It's also important that you can execute and simulate these algorithms in a pen and paper uh version on a small scale.(Lecturer, T4), spoken over the summary slides pp.59-60. "Give a counterargument if something is not optimal" is a literal instruction: when a question says an algorithm is not optimal, the expected answer is a concrete instance with numbers, like the 450 versus 418 of section 3 or the cost-5 versus cost-6 of section 12.
Time budget: about nine minutes per point in both halves of the paper. A four-algorithm trace question worth 2 points is roughly 4.5 minutes per algorithm, so the trace has to be mechanical before you walk in.
the slides and the material for the exercise sessions uh are the main source of reference. So that's the basis of what you need to know uh for the evaluation.(Lecturer, T1). Also stated on the Part 1 slides. For this Part that means the 61 deck pages and exercise session 3, and nothing beyond them is required.
| Term | Precise definition | Plain paraphrase | Exam phrasing |
|---|---|---|---|
| Heuristic h(n) | A function estimating how close a state is to a goal, designed for a particular search problem (p.6). | A guess about how much journey is left. | "find a suitable heuristic for this problem" (exercise session 3 §1.4) |
| g, h, f, h* | g(n) = cost from root to n; h(n) = estimated cost from n to nearest goal; f(n) = g(n) + h(n); h*(n) = true optimal cost from n to nearest goal (pp.21, 24). | Paid so far, guessed still to pay, total guess, and the truth you do not know. | "f = accumulated path cost + heuristic" (exercise session 3 solutions) |
| Greedy search | Best-first search with the frontier ordered by h(n) alone (p.12). | Always walk toward whatever looks nearest. | "3. Greedy-search:" as one of four traces (sample exercise exam Q1) |
| Beam search | Breadth-first by level, keeping only the k best paths by h after each level is fully built; not complete, not optimal (pp.17-18). | Greedy with a hard memory cap; extra options are thrown away for good. | "Is it complete? NO / Is it optimal? NO" (p.18) |
| Hill-climbing | Beam search with k = 1 (p.18); operationally, depth-first with loop detection where successors are pushed after sorting them by increasing h. | Keep one path, always step to the best-looking child. | "Explain how the behaviour of this algorithm is distinct from that of greedy search" (exercise session 3 §1.2) |
| A* | Search with the frontier as a priority queue ordered by f(n) = g(n) + h(n) (pp.21, 24). | UCS and greedy added together. | "4. A*:" as one of four traces (sample exercise exam Q1) |
| Admissible | 0 ≤ h(n) ≤ h*(n) for every n: the heuristic never overestimates the true remaining cost (p.28). | Optimistic; never says the rest is worse than it is. | "are the following heuristics guaranteed to be optimistic? Why?" (exercise session 3 §1.3) |
| Consistent | h(x) − h(x′) ≤ cost(x, x′) for every arc, with h(G) = 0 (p.47 and exercise sheet). Equivalently h(x) ≤ cost(x, x′) + h(x′). | The estimate may not drop faster than you actually travel. | "Is this a consistent heuristic? If not, specify how you could modify the heuristic to ensure consistency" (exercise session 3 §1.5) |
| Monotonicity | The consequence of consistency: f never decreases along a path (p.47). | f only goes up as a path gets longer. | "The f value along a path never decreases (sometimes called monotonicity)" (p.47) |
| Dominance | h1 ≥ h2 if h1(n) ≥ h2(n) for all n. Among admissible heuristics, larger is better (p.44). | A bigger honest estimate prunes more. | "equally good or better than h1 as well as h2" (sample theory MC 1.3) |
| Max rule | h = max(h1, h2) is admissible whenever h1 and h2 are, and dominates both (p.44). | Take the more informative of two honest guesses. | "If h1 and h2 are both admissible heuristics, then max(h1, h2) is also admissible and..." (sample theory MC 1.3, True) |
| Relaxed problem | P2 relaxes P1 if A2(s) ⊇ A1(s) for every s. Then h2*(s) ≤ h1*(s), so h2* is admissible for P1 (p.40). | Solve an easier version exactly and use its cost as the guess. | "What if we had an easier 8-puzzle where any tile could slide any direction at any time...? Why is it admissible?" (p.43) |
| f-contour | The band of paths whose f value lies within a given limit; A* expands contours in increasing f order (pp.35, 49). | Rings of equal total estimate, stretched toward the goal. | "Fact 1: In tree search, A* expands nodes in increasing total f value (f-contours)" (p.49) |
| Closed set / path deletion | Two ways to eliminate redundant paths. A closed (reached) set blocks any path whose final state was already expanded; path deletion keeps only the cheaper of two paths to the same state and allows re-expansion (p.46). | Either "never revisit a state" or "revisit only if this route is cheaper". | "redundant path elimination with closed sets" vs "with path deletion" (sample theory fill-in 2.1) |
| IDA*, f-bound | Iterated f-limited depth-first search; the next bound is the minimum f among paths rejected for exceeding the current bound (pp.53-58). | Depth-first inside a cost ceiling, raised by the smallest possible step. | "use the smallest f value as the next contour" (p.53); "Only Delta-optimal" (p.58) |
Constructed, in the sample paper's format (fill-in, blanks as on the 2023 paper)
A heuristic h is called .................... when 0 ≤ h(x) ≤ c(x). It is called .................... when h(x) ≤ h(x′) + c(x, x′) and h(G) = 0. The consequence of the second property is that the f value along a path never ...................., a property known as .................... .
admissible (the deck also says optimistic) | consistent | decreases | monotonicity.
All four words are printed in this Part: admissible on p.28, consistent and monotonicity on p.47, and the first two also in the exercise session summary in exactly the notation used above. The real fill-in on the 2023 paper (2.1, in section 12) wants the first two of these words, one per box, so learn them as words and not as paraphrases: "never overestimates" is the definition, not the term.
The size of the printed box tells you the expected length. For a one-word slot write the word; where the paper leaves a two-line box, add the clause that justifies it.
Chapter index: index.html · Previous: Part 4, Uninformed Search · Next: Part 6, Constraint Satisfaction Problems · Search by question: question-index.html