Search algorithms · Part 2

Welcome to informed search. In Part 1 we built a complete toolkit of uninformed strategies — breadth-first, depth-first, iterative deepening and lowest-cost-first. Those methods are systematic but blind: they explore according to mechanical rules (oldest, newest, shallowest, cheapest-so-far) with no sense of where the goal actually is.

This part adds a crucial new ingredient: an estimate of how far each state still is from the goal. With that extra signal, search can stop wandering blindly and instead steer toward promising regions — often finding solutions much faster. The overall aim of this lecture:

• Use these estimates (called heuristics) to guide exploration;
• Then carefully examine when the resulting guided searches are complete or guaranteed to find a cheapest route.

Before you begin, make sure you can still answer three recap questions from Part 1:

• Represent a task using states, actions, a goal and costs. A state holds everything needed to decide the next move; legal transitions are edges (possibly with costs); a solution path ends at a goal; many strategies return on selection, while branch-and-bound saves the solution and continues; and cumulative cost measures path quality.
• Explain the difference between queue and stack exploration. A queue (first-in-first-out) selects the oldest waiting path, giving breadth-first behavior; a stack (last-in-first-out) selects the newest, diving deep — and this choice of data structure determines both exploration order and memory use.
• Choose an uninformed method using the costs and memory available. Fewest steps cheaply in memory → iterative deepening; minimum weighted cost → lowest-cost-first with nonnegative edges, sound duplicate handling and termination conditions; any solution with a small frontier → depth-first, while accounting for cycles, infinite branches and ordering.

With those foundations fresh, you are ready to see how a simple estimate transforms search from blind to guided.

The sequence is: build a useful estimate, compare global and local selection rules, combine past and future cost in A*, check the guarantee assumptions, then use lower bounds to prune depth-first search. The Part 2 labs use the supplied edge weights for returned solution costs. Their course-tree goal is S; the Part 1 BFS/DFS exercises are explicitly linked from the practice section.

The single new idea that turns uninformed search into informed search is a quantity called a heuristic, conventionally written h(n). Here n stands for any state, and h(n) is defined as:

Think of it as a rough guess, attached to every state you encounter, answering: “about how much more effort will it take to finish from here?” For example:

• In route-finding on a map, h could be the straight-line distance from this city to the destination — a reasonable guess that never overestimates the real road distance.
• In a sliding-tile puzzle, h might count how many tiles are out of place, or sum each tile’s movement needed to reach home — both cheap estimates of remaining difficulty.

It is essential to understand what a heuristic does and does not do:

• It does not replace the frontier or the successor function. We still keep our collection of candidate paths, and we still generate successors exactly as before. The graph machinery from Part 1 remains fully intact.
• It supplies an additional signal: one more number per state that helps us choose which unfinished route to investigate next — a guide for the frontier’s selection step.

Why is this worth doing? Because a good heuristic acts like a compass needle pointing toward relevant regions of the search space. Instead of expanding candidates purely by age or depth, we can prefer paths that seem close to finishing — reaching the goal with far less exploration.

The key practical constraint on any useful heuristic: it must be cheap to compute. If computing h(n) were as expensive as solving the whole problem from n onward, that computation could erase the search-time benefit. The value of a heuristic is precisely that it gives you a good directional signal for much less effort than actually solving the task — which is what makes “guided” search both faster and still affordable.

Name the quantities

G is the graph; V its state set; E its legal directed edges; v_G the fixed goal vertex; ℝ the real numbers. h_vG is the heuristic for that goal, usually abbreviated h. ω_V (omega V) assigns heuristic values to states, and ω_E (omega E) assigns actual edge costs. The letters u, v and n denote states. In the distance formula, (x, y) are the current position’s coordinates and (x_G, y_G) the goal’s coordinates.

Units and a concrete relaxation

g is cost already paid and h estimates cost still ahead. If g is in minutes, distance in kilometres cannot be added directly. A valid maximum speed of 60 km/hour converts a straight-line distance of 12 km into a remaining-time lower bound h_time = 12 minutes (0.2 hours). This relies on the stated speed limit and compatible units.

For the unit-cost horizontal/vertical grid in the slides, Δx and Δy are horizontal and vertical displacement in grid squares; |…| takes an absolute value. Ignoring the blocked square gives Manhattan distance |Δx| + |Δy| = 2, while the real shortest route costs 4 moves. The relaxed value h = 2 is a lower bound on the true least remaining cost h* = 4, because constraints were removed while move costs were preserved. Diagonal moves or different movement prices require a different bound.

For the quality comparison, exactly two paths are waiting: a goal costing 7 and an unfinished path with g = 3 and true remaining cost 6. The latter can only finish at cost 9 or more. With h = 2 its f is 5, so A* explores it before selecting the goal. With h = 5 its f is 8, so A* selects the goal costing 7 first and stops. Both estimates are safe at this state, and the example assumes admissible heuristics throughout. The tighter estimate avoids an unnecessary expansion in this snapshot. The true remaining cost is known to us for explanation, not supplied to A*. Search work, heuristic evaluation cost, ties and reopening affect runtime, so a tighter bound is not a blanket promise of a faster run.

From a vertex weight to a heuristic function

The goal is fixed when defining this function, so we usually shorten h_vG(v) to h(v). Vertex weights ω_V hold estimates; edge weights ω_E hold actual transition costs. When only vertex weights matter, the original writes G = (V, E, ω_V). A* uses both. With unweighted edges, take ω_E(u, v) = 1 for every (u, v) ∈ E, so accumulated cost counts transitions.

For a destination at coordinates (x_G, y_G) and a vertex at (x, y), Euclidean distance is h(v) = √((x − x_G)² + (y − y_G)²). This is straight-line distance, not the actual road distance; the lower-bound interpretation requires distance costs in compatible units. With multiple valid destinations, use the distance to the nearest one.

Not every guess makes a good heuristic — there are two important properties that separate useful estimates from misleading ones. The first is about units and meaning: a heuristic must refer to the same objective and use the same units as the cost it is estimating.

Consider route-finding. Straight-line (“as-the-crow-flies”) distance is a fine lower bound on road distance — roads can never be shorter than the direct line between two points. But that same number would not automatically lower-bound travel time: you might drive 10 km in minutes or hours depending on traffic, so straight-line kilometres say nothing safe about minutes without extra assumptions (e.g., a known speed). A heuristic is only trustworthy when its units and objective match what it claims to bound.

The second idea gives us a systematic way to build useful heuristics: relaxing constraints. If you take your hard problem and remove some of its restrictions, you get an easier problem that can be solved cheaply. Its solution value is then very often a valid bound on the original harder problem.

• The classic example is a puzzle like the sliding-tiles: to estimate remaining moves in the real (constrained) game, solve the relaxed version where tiles may pass through each other — that easier computation gives a lower bound on the true number of moves needed. In route-finding, ignoring obstacles yields straight-line distance as the relaxed problem’s solution.
• The principle is general: an optimum of a relaxation bounds the original below because removing restrictions can only make things cheaper or equal, never more expensive.

Finally, why does all this effort to build good, safe estimates pay off? Because of a direct relationship between heuristic quality and search efficiency: the more informative a safe (admissible) estimate becomes — that is, the closer it gets to the true remaining cost without ever overestimating — the more irrelevant exploration it can prevent.

• A crude bound like “0” tells us nothing and helps not at all; a tighter safe bound can make fewer paths competitive, although ties, evaluation cost and graph-state reopening still matter. The whole art of informed search lies in crafting estimates that are safe yet tight enough to prune away dead ends early.

The mathematical selection rule

F is the entire frontier, q ranges over its candidate paths, and end(q) is the candidate’s last vertex. arg min chooses a path whose endpoint estimate is smallest; it does not return the score itself. Ties need a fixed rule. In the course tree, A is followed by B and E; after E is expanded, F has the lowest available estimate, h(F) = 2. Greedy can therefore switch branches without finishing E’s descendants. Its priority ignores the cost already spent.

The first informed strategy is delightfully simple — so simple it earns the name greedy best-first search. Its rule:

• “Greedy” means it makes the most attractive choice according to h at the current step: whichever candidate looks closest to a goal right now.
• It compares every state sitting on the frontier and picks the one with the lowest remaining-distance estimate — regardless of how old it is or what depth it lies at.

The critical detail, which you must notice: greedy best-first ignores entirely the cost already spent to reach that endpoint. It judges a candidate solely on its future promise (h), not on its past expense. Compare this with lowest-cost-first from Part 1, which used only the past (g) and ignored the future; greedy uses only the future and ignores the past.

What does this buy us? Speed of discovery. Because greedy lunges toward whatever seems nearest to a goal, it often finds a solution very quickly — racing down promising corridors without wasting time on unpromising ones.

But there is no free lunch: greedy best-first provides no general minimum-cost guarantee. It can deliver you an expensive route while a cheaper one existed. The failure mode is easy to picture:

• A state might look excellent in terms of remaining distance (small h) only after you have already made a very costly detour (large g). Greedy never notices the accumulated bill, so it happily finishes down that expensive path.

So treat greedy best-first as a fast heuristic-driven explorer: potentially useful for finding a solution quickly, but without a general speed or minimum-cost guarantee. That goal requires balancing both past and future — which is exactly what A*, later in this lecture, will do.

In the selection rule, F is the frontier, q a waiting path, end(q) its endpoint, and p the selected path. h(end(q)) estimates remaining cost; arg min returns a minimizing path and ← assigns it. Greedy ignores g, the path cost already paid.

The counterexample has A → B → G costing 1 + 9 = 10, and A → C → G costing 4 + 1 = 5. With h(B) = 0, h(C) = 1 and h(G) = 0, greedy selects B and then G. Both estimates are admissible, yet greedy returns the more expensive solution: admissibility alone does not make its h-only selection optimal. Like DFS, greedy can also fail to reach a goal on an infinite space; it does not guarantee a fast answer.

The interactive example for greedy best-first search rewards careful prediction, and it contains a behavior that often surprises students at first. Here is how to study it:

1. Before advancing each step, scan all the h values currently displayed on the frontier.
2. Predict which endpoint has the smallest h — that is the next path greedy will select.
3. Advance and check whether you were right.

In this course tree, after A → B → E the new children have h(K) = 8 and h(L) = 7, while the older path to F has h(F) = 2. Greedy selects F next. The other waiting endpoints G, C and D have estimates 9, 4 and 3; none beats F.

Why is this allowed? Because greedy best-first makes its priority comparison globally across the entire frontier, not locally within one branch. Every waiting path competes on equal terms, judged purely by h. There is no obligation to finish exploring E’s descendants just because we started them; if some other state anywhere looks closer to a goal, greedy jumps to it.

• This global-jumping behavior is what distinguishes greedy best-first from a depth-first method that merely sorts its newly generated siblings. Depth-first commits to the branch it chose and follows it down; it never re-competes against distant states. Greedy, by contrast, keeps reconsidering everything at every step.

Explain the actual jump using the displayed values: “F has h = 2, less than K’s 8 and L’s 7, so greedy selects the older route to F.” With default goal S, this weighted lab returns A → B → F → P → S at cost 12.

p₁, …, pₘ are the m new path extensions of the selected route; i indexes those paths, and end(pᵢ) is path i’s last state. This m counts new children, rather than maximum search depth. The function h estimates remaining cost at each endpoint. The LIFO stack retains older alternatives underneath the newly pushed children.

The ordering rule and the stack

These are only the new extensions of the selected path. Push the largest estimate first and the smallest last so the best-looking new child sits on top of the LIFO stack. Equivalently, sort by ascending −h. At A, the estimates are h(C) = 4, h(D) = 3 and h(B) = 2: push ⟨A, C⟩, ⟨A, D⟩, ⟨A, B⟩, then pop the route to B. Older alternatives remain underneath. This is local ordering, unlike greedy’s comparison over the full frontier.

Heuristic depth-first search takes a gentler approach than greedy best-first: it uses the heuristic locally, to decide which newly generated children to try first, but otherwise keeps ordinary depth-first behavior. This hybrid is worth understanding carefully because it behaves very differently from global-greedy.

• When we expand a state and generate its successors, we push children with larger heuristic values first and the most promising child (smallest h) last, so it ends up on top of the stack.
• Then we continue exactly as plain DFS: always dive into the newest candidate and follow that branch down.

The key contrast with greedy best-first is where the heuristic applies:

• Greedy best-first makes every selection a global competition among all frontier endpoints, re-ranking everything at each step.
• Heuristic DFS uses h only to pick which child of the current node looks best; afterwards it commits deeply, exactly like depth-first. It can choose a promising sibling first without turning every later choice into another global contest.

What are the consequences? Because heuristic DFS keeps the stack-based structure:

• It retains memory advantages of DFS: only one deep branch plus a few waiting alternatives, not an entire frontier layer — far cheaper than greedy’s global bookkeeping or BFS.
• And it inherits depth-first limitations too: no optimality guarantee, and sensitivity to ordering. The heuristic helps pick good branches first but cannot protect against every bad case.

In the running tree, E generates K (h = 8) and L (h = 7). Push K first and L last, so L is on top. Heuristic DFS then selects L and K before returning to the older F (h = 2), even though F has the smallest estimate among those three paths. That is local ordering followed by depth-first commitment.

So heuristic DFS offers a useful middle ground: the direction of depth-first (lean memory, fast commitment) plus local guidance to try promising children first — while accepting that once committed, it stays put.

The small-frontier comparison assumes compact parent-linked records and bounded branching; storage still grows with explored depth. A global visited set or the widget’s stored rewind frames adds memory. Heuristic DFS inherits the possibility of being delayed forever by an infinite branch, as well as DFS’s lack of a general optimum guarantee.

This interactive example directly contrasts heuristic DFS with greedy best-first, and it drives home one of the most important conceptual lessons in this entire lecture — so study the sequence carefully.

• Watch what happens after we enter state E. In the greedy example from a moment ago, F’s small heuristic could pull greedy away to explore F even while E still had unexpanded children.
• In this heuristic DFS example, something different happens: even if F has a better estimate than some of E’s descendants, heuristic DFS will keep pushing through those descendants. Why? Because once we expanded E and pushed its children onto the stack, they occupy the top. Depth-first discipline says “take from the top” — so down we go into them, regardless of whether F elsewhere looks more promising.

The general lesson hiding here is profound and easy to miss:

Both greedy best-first and heuristic DFS “use h.” Yet they behave completely differently — one re-ranks everything globally, the other orders only local children then commits deep. The estimate is not the whole story:

• Where the estimate enters the selection process matters as much as (sometimes more than) the estimate itself.
• The same numbers can produce radically different exploration depending on whether h drives global re-ranking, local sibling ordering, or some other insertion into the loop.

This is why you should describe a search strategy by both what signal it uses and how that signal controls selection. Two algorithms can share an identical heuristic yet be entirely different methods. When you study A* next, notice again exactly where g and h enter the priority — because getting that placement right is precisely what gives A* its powerful guarantees.

With default goal S, heuristic DFS selects A, B, E, L, K, F, O, P, S and returns the weighted route A → B → F → P → S at cost 12. Greedy skips L and K at that point, but returns the same route on this one-goal tree. Equal returned paths do not imply equal search effort.

p is a path, q a waiting candidate, F the frontier and end(p) its last state. g(p) is actual cost from the start; h(end(p)) estimates what remains; f(p) is their sum. State labels such as F in A → B → F refer to a graph vertex; the frontier F is a separate mathematical variable.

The score and selection formula

F is the frontier. For each waiting route q, add its actual accumulated cost g(q) to the estimated cost still ahead h(end(q)); select a path with the smallest resulting f(q).

The start path has g(⟨A⟩) = 0 and f(⟨A⟩) = 0 + 5 = 5. Its extensions score 1 + 2 = 3 via B, 2 + 4 = 6 via C and 4 + 3 = 7 via D. After selecting B, the new routes score 3 + 1 = 4 via E, 7 + 2 = 9 via F and 4 + 9 = 13 via G. The routes to C and D still compete, so E is selected next.

A* (pronounced “A star”) is the most famous informed-search algorithm — and for good reason: it carefully balances the two pieces of information we have been keeping apart, past cost and future estimate.

• g(p): the known, exact cost already paid along this path p from start to its endpoint. This is certain fact, not a guess.
• h(n): the heuristic estimating how much more it will take from that endpoint to reach a goal — our best (imperfect) forecast of what remains.

A* combines them by simple addition into a single score f(p):

What does f represent? It is an estimate of the total cost to complete this route all the way from start to goal through this particular path: everything already spent (g) plus a forecast of what remains (h). By choosing the smallest f, A* simultaneously rewards paths that have made good progress cheaply and avoids abandoning ones that still look close — it weighs progress already made against the remaining task.

• Notice how this places A* between our earlier methods: lowest-cost-first used only g (past), greedy best-first used only h (future); A* uses both. That balanced perspective is what makes it so effective.

A useful sanity check to confirm you understand the formula: if we set h identically zero, then f = g + 0 = g, and A* reduces exactly to uniform-cost (lowest-cost-first) search. In other words, lowest-cost-first is just A* with a completely uninformative heuristic — which tells you that A*’s extra power comes precisely from the guidance of h.

With an admissible heuristic, nonnegative costs, goal testing on selection and a search policy that preserves cheaper routes, A* returns a minimum-cost solution when it selects a goal. The finite-branching and fixed positive minimum-edge-cost conditions later in the lecture provide a sufficient termination setting for a finite-cost reachable goal. In graph search, admissibility alone does not justify discarding improved routes to expanded states. Heuristic guidance can reduce exploration; runtime also depends on evaluating h, ties and reopening.

The first comparison in the course tree makes the arithmetic explicit. A–B has g=1 and h=2, hence f=3; A–C has f=6; and A–D has f=7. A* therefore selects B. After B is expanded, the new candidates must compete with older frontier entries rather than being chosen automatically. This global comparison explains why the algorithm can move between subtrees as their estimated total costs change.

After A, B and E have been expanded, the whole frontier has these total scores: C = 6, D = 7, F = 9, K = 12, L = 12 and G = 13. A* selects C, leaving E’s new children waiting. K and L tie; insertion order puts K first when that tie is eventually reached. These endpoint labels abbreviate complete paths, whose g costs are different.

The interactive example for A* rewards disciplined attention — the single most important habit here is: track all three values g, h and f together; don’t just read the heuristic alone. Since A* decides by f = g + h, looking only at h (or only at g) will leave you puzzled about why certain choices happen.

• g tells you what has already been spent on each path;
• h forecasts what remains;
• f is their sum — the actual number that ranks candidates for selection.

A particular decision worth watching closely: the algorithm may return to expand C before trying F, even though F might look closer by some criterion. The reason, if you inspect f values, is simply that C’s estimated total route cost (g + h) is lower than F’s — so A* rightly prefers finishing the cheaper-looking overall path first. Without tracking g alongside h this would seem arbitrary; with both in view it becomes obvious.

Now try the experiment that makes A*’s relationship to uniform-cost search concrete: use the toggle to set h = 0. This removes all heuristic guidance. Watch what happens — with f now equal to g alone, the exploration order changes into exactly uniform-cost (lowest-cost-first) behavior. You are watching one algorithm transform into its uninformed cousin before your eyes.

Because the graph and goal stay completely unchanged between toggles, any difference in exploration can be attributed directly to the priority calculation — nothing else moved. That clean comparison is precisely why this example teaches so well: it isolates the effect of adding heuristic guidance on top of otherwise identical machinery.

• Takeaway: whenever you inspect an A* trace, read f as “the total estimated cost if I commit to finishing through here,” and explain every selection by comparing these totals — never by h alone.

This lab keeps the supplied unequal edge weights in both settings. With h = 0, A* reduces to UCS using the same insertion-order tie rule. The default S-goal solution is A → B → F → P → S at weighted cost 12; toggling the heuristic changes exploration order, not the definition of edge cost.

Two properties of the heuristic

The heuristic h estimates the cheapest remaining cost, using zero at a goal. Admissibility asks whether that estimate ever exceeds the true cheapest cost still needed. An underestimate is allowed: if 6 remains, h = 4 is safe but h = 8 is too high. This supports A*’s optimality when better routes remain available and goals are tested on minimum-score selection.

Consistency asks whether estimates agree across each move: the decrease in h must be no greater than the move cost. For a move costing 1, a change from 3 to 2 passes, while a change from 5 to 2 fails. This is a stronger property. With zero estimates at goals, a consistent heuristic is also admissible; an admissible heuristic can still be inconsistent. With correct cost updates, consistency lets graph A* avoid reopening expanded states. With an admissible but inconsistent heuristic, graph A* may need to reopen a state when a cheaper route is found. These heuristic properties are distinct from the algorithm’s rules for selecting paths, testing goals and preserving cheaper routes.

We said A* guarantees an optimal solution “under suitable assumptions.” The most important of those assumptions is that the heuristic be admissible. This is a precise mathematical condition, and understanding it fully tells you exactly why A* can trust its own choices.

• “Never overestimate”: an admissible heuristic’s value is always less than or equal to the real minimum cost still needed. It may guess too low, but it never guesses too high.
• Zero at a goal: when you are already at a goal, no more work remains, so h must be 0 there (the nonnegative estimate cannot exceed the zero remaining cost).

The straight-line-distance example fits perfectly: real roads can never be shorter than the direct line between two points, so straight-line distance is an admissible lower bound on road travel. A heuristic that could overestimate — say, guessing 10 when the true remaining cost is only 4 — would break A*’s reasoning by making a good path look artificially expensive.

A numerical example: suppose the true cheapest remaining cost from a state is 6. An estimate of 4 is a safe underestimate; 6 is exact and also safe; 8 overestimates and is not admissible at this state. The condition must hold at every state, so one successful example cannot establish admissibility of the whole heuristic. If a path has already paid g = 3 and uses h = 4, its total estimate is f = 3 + 4 = 7. The cheapest completion through that path costs 3 + 6 = 9. Thus f is a lower bound: it cannot exceed the cost of any completed solution extending this path.

Why does admissibility matter so much? Because of this chain of reasoning:

• Let C be the cost of the selected goal. At a goal, h = 0, so f = g = C. If a cheaper solution of cost C* still existed, a waiting prefix of that solution would have f ≤ C* < C and would have been selected first. This requires that the search has not incorrectly discarded that cheaper prefix. Tree search preserves it; graph search must preserve improved routes and reopen expanded states when needed.

That argument — f is a safe underestimate, so expanding in order of smallest f can never skip an optimal answer — is the heart of A*’s standard tree-search optimality guarantee. It requires some supporting conditions we should state honestly:

• finite branching factor;
• edge costs that are positive and bounded below (so cheap detours cannot hide a better route indefinitely);
• and goal testing performed at selection, not generation (the same subtlety we met with uniform-cost search).

A final, important mindset point: admissibility is a mathematical property of the estimate — it is never established by “it worked on a few examples.” Just because A* found good answers in practice does not prove the heuristic was admissible. To claim optimality you must verify h really cannot overestimate for all states, through reasoning about the problem (e.g., the relaxation argument from earlier), not anecdote.

n denotes a state; h its estimate; h* (h star) the true remaining optimum; p a partial path; and f = g + h its completion lower bound. ε (epsilon) is one fixed positive lower bound on every edge cost, not a different shrinking minimum at each step. With finite branching and a finite-cost reachable goal, this bounds the depth of paths competitive with that solution. Optimality on selection and eventual selection are distinct claims.

The same argument with numbers

Suppose A* is about to select its first goal, costing 10. Its h is zero, so its f is 10. If a solution costing 8 existed, either the cheaper goal itself or a discovered but unfinished initial part of its route would still be waiting in the frontier. The initial part of a route is called a prefix. Because the heuristic never overestimates, that waiting path has f at most 8. A* always chooses the smallest f, so it must explore that path before selecting the goal costing 10. This contradicts the proposed first selection: no cheaper solution can exist when the first goal is selected. The argument requires that better routes remain available; it does not justify stopping when a goal is merely discovered.

Read the updated illustrations

The true remaining cost is 6. Estimates of 4 and 6 are admissible because they do not exceed 6; 8 is too high.
Why it matters: admissibility keeps estimates optimistic, so A* does not overlook a cheaper solution.

A goal costing 10 has been found, but a waiting path could lead to a solution costing 8.
Its estimated total is at most 8, so A* explores it before selecting the more expensive goal.

The route diagram now labels h beneath every node. At the start, h ≤ 8 because we assume a solution costing 8 exists. At the waiting endpoint, h ≤ 5 because 5 remains on that route. Both goals have h = 0. The inequalities show safe upper limits, not exact chosen values of the heuristic. Admissibility keeps the estimates optimistic: it prevents a potentially cheaper route from appearing more expensive than its real completion cost, which is why minimum-f selection can protect optimality.

Admissibility is the property you need for A*’s optimality, but there is a second, stronger condition called consistency (also known as monotonicity) that makes many guarantees cleaner and simpler. Let us see what it demands.

• Read in words: the estimate at u must be no larger than “pay for this one move, then finish from v.” In other words, the heuristic should not estimate a greater remaining cost here than the cost of one move plus the estimate at its successor — a condition that looks just like the triangle inequality you may know from geometry.
• Intuitively: my guess of remaining distance from u should not exceed (the cost to get to v) plus (my guess from v). If it did, h would be “optimistic in a way that contradicts its own neighboring estimates.”

The practical payoff of consistency is beautifully simple:

• As A* extends a path, its f value never drops. That monotonicity means the first time a state is selected/expanded it already has its final best cost — no later surprises force revisiting.
• It also implies admissibility: with h(goal)=0, consistency guarantees h never overestimates anywhere (you can chain the inequality down to a goal). So consistent ⇒ admissible; but the reverse does not hold.

The lecture’s running tree gives you a crisp example of the gap between them: an admissible yet inconsistent heuristic. Suppose h(A)=5, while the edge cost from A to B is c(A,B) and h(B) makes c(A,B)+h(B)=3. Then:

• It is still admissible (it never overestimates the true cost to a goal), yet inconsistent — it fails the per-edge triangle inequality. Such heuristics are possible and perfectly safe for optimality in tree search.

Why does this distinction matter so much? Because of graph search that closes states. When an algorithm records “state X is fully expanded, discard it,” a consistent heuristic lets us safely never revisit X (since its selected path already had the best possible g). An inconsistent-but-admissible heuristic may require the ability to reopen closed states when an improved route arrives with lower cost — more bookkeeping and potentially more work. So knowing which property your heuristic has tells you exactly how much care graph search must take.

u and v are neighboring states; c(u,v), also written cost(u,v) or ω_E(u,v), is the directed edge cost. For a path p ending at u, p ⊕ v is its one-edge extension. The slide’s derivation compares these two paths:

On the course edge A → B, g increases from 0 to 1, but h changes from 5 to 2: f falls from 5 to 3, exposing inconsistency. Setting h(A) = 3 makes f = 3 at both endpoints on this edge; it does not certify all other edges. Check the condition everywhere. With sound graph bookkeeping and a consistent heuristic, the first selected route to a state has its best g; closing a state on mere first discovery is still unsafe.

Read the one-move check as a limit on the drop in h

A move costing 1 may reduce the remaining estimate by at most 1. A change from h = 3 to h = 2 passes this edge; a change from h = 5 to h = 2 fails it. If the accumulated path cost before the move is g = 4, it becomes 5 afterwards. In the passing case, f changes from 4 + 3 = 7 to 5 + 2 = 7: the increase in g balances the decrease in h. In the failing case, f changes from 4 + 5 = 9 to 5 + 2 = 7: the decrease in h is too large. In general, consistency limits the drop in h to the move cost, while g increases by exactly that cost, so f cannot decrease. These numbers illustrate one edge only; consistency must hold on every directed edge.

When searching a graph (as opposed to a tree), two paths that end at the same state are not necessarily equivalent — and this section explains why careful bookkeeping matters. The key observation is simple:

• Imagine arriving at city X once having spent 10, and again having spent only 4. The second route is strictly better — it reaches the same situation cheaper.
• A good graph search therefore should retain the best known cost for each state. When a newly discovered route reaches an already-seen state at lower g, we update that record (or “reopen” the state if it was closed) so the improved path is not lost.

The precise bookkeeping depends on the algorithm and its assumptions:

• With a consistent heuristic, f never decreases along paths, so the first time we expand a state its g is already final — closing it permanently is safe (this is why consistency simplifies graph search).
• With an inconsistent but admissible heuristic, f can dip later. If you close a state too early and refuse ever to revisit it, you may throw away the record of a genuinely cheaper route discovered afterwards — losing the optimal solution entirely.

This is precisely why we spent time distinguishing consistency from admissibility: it directly determines whether a graph search must support reopening closed states or can safely discard them forever.

A separate warning about negative edge costs, because they break the whole framework we have built:

• All of our reasoning assumed costs are nonnegative. A negative edge can make an expensive partial path become cheaper later. Endless decrease requires a reachable negative cycle that can still lead to a goal.
• The classic pathological case: if there is a reachable cycle with total negative cost somewhere on the way to the goal, then you can loop around it repeatedly and reduce your total without bound. In that situation the “optimum” is not just hard to find — it does not exist as a finite number; the best value is unbounded (−∞).

The lesson: negative edges require entirely different algorithms and reasoning (this is beyond our scope, but good to recognize why we assume nonnegativity everywhere here). For all of A*’s guarantees, hold onto that assumption — it is load-bearing.

The concrete reopening example

The toy graph has A → X costing 3, A → B costing 1, B → X costing 1, and X → G costing 3. The estimates h(A) = 0, h(B) = 4, h(X) = 0 and h(G) = 0 are admissible, but B → X violates consistency: 4 > 1 + 0. A* first expands X at g = 3 and discovers G at cost 6. It then expands B (g = 1, f = 5), finds X at g = 2, reopens X and improves G to cost 5. Permanently suppressing X would leave the cost-6 solution. Preserve best costs and parent links, and propagate improvements through reopened states.

One negative edge is already enough to break the usual stopping rule

A → G costs 2, A → B costs 5, and B → G costs −10. UCS selects G at cost 2, although the route via B costs −5. This graph has no negative cycle; the single negative edge invalidates ordinary UCS reasoning. A negative cycle makes the optimum unbounded only when it is reachable and can lead to a goal.

Same state, cheaper route: update the record

Reaching X before does not make every new arrival useless. Keep the cheaper route, so its lower cost can improve the solution.

Further explanation: The arcs abbreviate whole routes, not single edges. S is the start; X is the same state reached by both routes. The generic best-cost record improves from 10 to 4. Store the improved parent link as well as cost. If X waits in the frontier, update or insert the improved priority entry and ignore stale entries. If X has been expanded under an admissible but inconsistent heuristic, reopen and propagate the improvement. Under a consistent heuristic and correct minimum-f selection, an expanded state already has its best g and does not require reopening. Closing on first discovery is unsafe. Negative edges are handled separately on the later slide.

Reopen a state when a cheaper route arrives

Refusing to expand X again leaves the cost-6 solution. Reopening lets the cheaper route reach the goal, giving cost 5.

Further explanation: Start A has g=0. After expanding A, X has g=3,h=0,f=3 and B has g=1,h=4,f=5. Expanding X discovers G at g=f=6. B is then selected at f=5 and reaches X at g=2, f=2. X was closed (already expanded), so reopen it. Its next expansion improves G to g=f=5, and G is then selected as the optimal solution. Actual least remaining costs are A=5, B=4 and X=3, so all displayed h values are admissible. B→X has cost 1 and h(B)=4>1+0, so the heuristic is inconsistent. The graph is independent of the course lab.

Negative costs can change which route is cheapest

UCS selects the direct goal at 2 before B at 5, but the route via B costs −5. A repeatable negative loop on the way to a goal lowers cost forever: no cheapest solution exists.

Further explanation: Left graph: A→G costs 2, A→B costs 5, B→G costs −10. UCS selects G at g=2 before B at g=5, but A→B→G costs −5. There is no cycle, so the negative edge alone defeats the ordinary first-goal stopping argument. Right graph: A→X costs 0, a repeatable loop at X costs −1, and X→G costs 2. Goal costs are 2−k after k loops. The loop must be reachable from the start and able to reach a goal for it to make the optimum unbounded. Both are directed graphs. The standard nonnegative-cost reasoning does not apply; preventing loops alone does not fix the left example.

The bound test as a mathematical algorithm

h*(v) is the actual least cost from v to a goal. Nonnegativity and admissibility imply h(goal) = 0. With nonnegative edge costs, f(p) = g(p) + h(end(p)) is a lower bound on any solution extending p. B is an upper bound supplied by the best complete solution already found; initially use B = ∞ with no saved solution.

F ← stack(⟨vₛ⟩); B ← ∞; best ← none
while F ≠ ∅:
    p ← pop(F)
    if g(p) + h(end(p)) ≥ B: continue
    if end(p) = vG:
        best ← p; B ← g(p)
    else:
        for v with (end(p), v) ∈ E:
            if v is not in p: push(F, p ⊕ v)
return best

How to read the code: pop selects the latest stack entry. If its lower bound is at least B, continue skips directly to the next loop iteration. Otherwise a goal updates both the saved route and B; a non-goal generates legal extensions p ⊕ v. Checking that v is not already in p prevents cycles on that route without a global visited set that might discard a cheaper alternative. With nonnegative costs, a cycle is not needed to obtain one optimum. Only an empty stack triggers the final return.

This version terminates on a finite graph because only finitely many simple paths exist. On infinite spaces, termination requires further conditions, discussed below. A finite initial B without a saved route is a strict cutoff: returning none means no route below B was found, not that no solution exists. See the later bound discussion for equality handling.

Read the algorithm in the slides →

Branch-and-bound is a powerful idea for finding provably optimal solutions when A*’s frontier would require too much memory. Safe pruning still requires a lower bound; with nonnegative costs, h = 0 is valid when no more informative heuristic is available. The name captures its two-part strategy: branch by exploring alternatives depth-first, and bound by pruning away anything that cannot beat the best solution found so far.

• The algorithm retains the incumbent, the best complete solution found so far, and uses its cost as the upper bound. Before any solution is found, the bound may be set to infinity.
• As search proceeds depth-first, whenever we reach a goal and finish a route, we compare its cost with the incumbent and update if better — so the incumbent improves over time.

The pruning step is what gives branch-and-bound its efficiency:

• For any partially explored path, we can compute a lower bound: the cost spent so far plus an underestimate of what remains. If even that best-case total is no better than (or equal to) our incumbent — if it cannot possibly improve on the solution already in hand — then there is no point continuing down this branch. We cut it off immediately and avoid generating its descendants.

Here is a key mental shift from plain search: finding one complete solution does not necessarily end branch-and-bound; instead, it tightens the search. A cheaper incumbent lowers B, so more partial paths meet f ≥ B and can be pruned. Only when every remaining possibility has been explored or pruned do we know our current incumbent is optimal.

Because a strong early incumbent lets us prune aggressively, good neighbor ordering matters enormously: if depth-first happens to find an excellent solution quickly (by trying promising branches first), the cost bound becomes low early and many later branches can be eliminated safely. Poor ordering finds only mediocre solutions late, pruning little.

A precise clarification separates two different claims that students often blur:

• Optimality on completion: if branch-and-bound terminates with an incumbent, is it guaranteed to be optimal? Yes — provided every pruned branch was really bounded below correctly (never overestimated), so nothing better was discarded.
• Termination itself: will the algorithm always finish and return that optimum? This is a separate question. With an initial infinite bound, plain depth-first could chase an infinite branch forever without ever finding any incumbent — never getting the chance to prune. To guarantee termination you need the search space actually explored to be finite (e.g., a finite graph with cycle pruning), or additional assumptions (bounded costs/depths) for infinite spaces.

So: optimality-on-completion and termination are independent guarantees, each requiring its own conditions — keep them separate when you reason about the algorithm.

In the code, F is the frontier stack, p the popped path, vₛ the start vertex, v_G the goal vertex, v a successor, and E the legal-edge set. g is actual path cost, h estimated remaining cost, f = g + h their lower bound, B the pruning threshold and best the saved route. ∞ means infinity (no finite bound), ∅ an empty collection, none no saved route, ← assignment, pop removes the latest path and push adds a path. Path-cycle checking does not merge all arrivals at the same state.

Read the bound trace and its stopping assumptions separately

The exit lab’s rightmost-first DFS saves G3 at cost 12, then explores C and D with lower bounds 6, then saves G2 at cost 6. The waiting path through B has g = 1 and h = 7, so f = 8 ≥ B = 6 and is pruned. That branch’s actual completion cost is 9; the lower bound is safe.

A saved route costing 6 justifies pruning equality when only one optimum is required. A threshold B = 6 without a saved route instead asks for cost strictly below 6; returning none does not return a cost-6 route or prove infeasibility. To enumerate all equally optimal solutions, equality handling must change.

A finite graph with path-cycle checks has finitely many simple paths and terminates. In an infinite space, finite branching, a finite bound and a fixed positive minimum edge cost ε limit surviving depth when h is nonnegative. Finding the first incumbent under B = ∞ is not guaranteed: unbounded DFS may never leave an infinite branch. A finite threshold can bound the search without providing a feasible solution, so preserve the cutoff-versus-incumbent distinction.

A cost limit is not a saved solution

Both prune f ≥ 6. If the search finishes without finding a cheaper route, the left returns its saved route; the right returns no route—even if a cost-6 solution exists.

Further explanation: The incumbent means the best complete solution already saved. Its cost is an upper bound with evidence. If it costs 6, pruning f≥6 is safe for finding one optimal solution because such branches cannot improve it. A finite threshold of 6 with no saved solution is merely a strict cutoff: cost-6 branches can be skipped and no route returned. Returning none does not prove infeasibility. The stored solution is optimal only after all better alternatives have been explored or safely pruned. To enumerate all equally optimal solutions, equality handling must change. Safe f=g+h uses actual paid cost g plus admissible remaining estimate h and nonnegative costs; all definitions and full code remain in the handout.

Safe pruning does not always make DFS finish

Without a finite bound, DFS can follow an endless branch while a goal waits. With finite branching and a fixed positive minimum step cost, a finite bound makes the remaining search finite.

Further explanation: Left: DFS explores the chain first, with cost 1 on each downward edge; a goal costing 2 waits on the other branch. With B=∞, f=g never reaches the bound and DFS may never return. No cycles are needed for this counterexample. Right: an actual cost-6 solution is saved, h=0, and each move costs 2; g grows 0,2,4,6 and the g=6 path is pruned. The example illustrates the general sufficient conditions: finite branching, a finite initial bound (or incumbent already obtained), nonnegative h, and one fixed positive minimum edge cost epsilon>0 give a finite surviving depth because depth times epsilon≤g≤f

The interactive demonstration in this section is designed to show you branch-and-bound’s defining behavior — the way a single discovery transforms how much work remains. Note first that it deliberately tries the rightmost branch first, so you can see the algorithm at its worst as well as its best.

• Watch what happens to the incumbent cost: in this example it improves from twelve down to six. That is not a trivial detail — each improvement tightens the pruning bound and directly changes which remaining paths are worth exploring.
• Before any solution existed, every branch seemed potentially valuable; after we hold a complete route costing 6, any partial path whose best-case completion cannot beat 6 becomes prune-worthy immediately. The search visibly shrinks as the incumbent improves — exactly why good early solutions help so much.

A crucial mindset point reinforced by this trace: the first solution found is only provisional. It may be cost 20, then we find 15, then 8 — each merely the best-so-far until proven otherwise. Do not confuse “first complete route” with “optimal.” Branch-and-bound keeps going precisely because a better incumbent might still exist in an unexplored region; it only stops when nothing unpruned remains.

• Experiment now with setting the initial strict bound. If you set an initial bound of 6 without a saved route (rather than infinity), you are effectively asking: “find a solution costing strictly less than 6.” That is a different question from “minimize.” In particular:
• A failure under that strict setting does not prove no solution of cost exactly 6 exists — it only shows none cheaper than 6 was found, because the bound excluded anything equal to or above 6. The initial strict bound is a filter you impose; changing it changes what counts as acceptable.

The takeaway: read branch-and-bound traces by tracking (1) the current incumbent at each moment and (2) how that number governs pruning — those two observations explain every decision in the animation.

Default bound ∞ produces improvements 12 → 6 and returns A → C → D → G2 at cost 6. Initial strict bound 12 still finds that route; strict bound 6 finds none below 6 and saves no route. The node named B and the cost bound B in the mathematical slides are different uses of the letter.

The comparison table in this section offers one of the most useful perspectives for understanding — and even reading — search algorithms: summarize each method by its frontier rule, i.e., “exactly how does it decide which candidate to take next?” Organizing them that way reveals a clean taxonomy:

• Queue methods (breadth-first) and stack methods (depth-first): selection depends purely on insertion order — oldest first, or newest first. No scalar score; just the data structure’s discipline.
• Scalar-priority methods: each candidate carries a number used to rank it against all others.
  • Uniform-cost: priority = g (cost spent so far).
  • Greedy best-first: priority = h (remaining estimate only).
  • A*: priority = f = g + h (both together).
• Branch-and-bound: combines depth-first traversal with an incumbent-based rejection test — it explores deep like DFS but refuses to continue any partial path whose lower bound cannot beat the best complete solution so far.

This framing is not just tidy — it is genuinely practical. When you encounter a new or unfamiliar search implementation, ask yourself four questions and the algorithm’s behavior will fall out:

1. What does it store? Paths in a queue/stack? Scored candidates in a priority structure?
2. How does it rank candidates? By age, depth, g, h, f, or some combination?
3. When does it check for the goal? On generation or on selection (as we saw matters so much for optimality)?
4. What information allows it to discard a route? Pruning by bound? Closing visited states? Cycle detection?

The answers to those four questions determine everything about the algorithm’s completeness, optimality and efficiency — far more than memorizing which name goes with which behavior. Once you can describe any search method in terms of its frontier rule and these four decisions, you truly understand it.

With the whole toolkit now on the table, how do you pick? The answer should always start from what your problem requires, not from what algorithm you happen to like. Work through requirements in this order:

1. Minimum number of steps (equal edge costs)?
   • If memory is plentiful → breadth-first search: fewest edges, simple.
   • If memory is tight → iterative deepening: same fewest-edge guarantee at stack-sized memory, with repeated work whose size depends on branching, depth and where the goal is found.
2. Minimum weighted cost (edges differ, all nonnegative)?
   • No useful heuristic available → uniform-cost search, the honest uninformed choice.
   • A suitable admissible estimate exists that could cut exploration dramatically → consider A*: it preserves optimality when its conditions and duplicate policy are sound; the benefit depends on heuristic quality, evaluation cost, ties and reopening.
3. Optimization needed but a large best-first frontier impractical? → branch-and-bound, which searches depth-first (tiny memory) and prunes using an incumbent, trading a smaller frontier for depth-first exploration; storage still depends on depth, and termination must be checked.

A few practical reminders that keep the choice honest:

• “Memory permits” and “tight” are real engineering judgments, not abstractions — a huge branching factor can make even one BFS layer infeasible.
• The guarantee you expect is only as good as its assumptions being met: A* optimality needs admissibility, nonnegative costs, goal testing on selection and sound duplicate handling, including reopening when needed. UCS also needs correct graph duplicates. Eventual completion has separate cost and branching assumptions. If an implementation skips those, the promised property silently vanishes.

In other words, algorithm selection is a matching problem — map your objective (steps vs. weighted cost vs. any solution) and your constraints (memory, availability of a heuristic, admissibility you can verify) onto the method whose guarantees fit. Implementation details still determine which guarantees actually apply, so always double-check that the code honors its assumptions.

The review questions in this section are best approached with a discipline that will make your answers genuinely correct rather than merely plausible: name the selection or pruning rule first, then predict the outcome. For example:

• Don’t say “A* goes to C next because C looks closer to the root.” That is explaining from the picture alone — and it is wrong reasoning. Instead commit: “C has the smallest f = g + h among all frontier endpoints, so A* selects it.”
• For a branch-and-bound question, state the rule explicitly: “this partial path’s lower bound (g plus underestimate of remaining) cannot beat incumbent 6, so we prune it.” Predictions made by invoking the actual mechanism are testable and self-correcting.

The reason this discipline matters is that visual intuition — “that node seems near,” “this route looks short” — can easily fool you, especially when edge costs differ or a heuristic is involved. Only appealing to the concrete selection/pruning rule grounds your reasoning in what the algorithm really does.

Then use the interactive examples as an experiment: make your prediction from the rule, run it, and see whether the actual frontier behavior matches:

• If it matched — good, you reasoned correctly.
• If not — do not just shrug; revise your explanation until it accounts for what actually happened. That revision is where genuine learning occurs.

The strict-bound question asks for a route costing less than 6 when no incumbent is saved. If the search completes with sound pruning and finds none, it establishes that no cheaper route exists under those rules. It does not establish that no feasible route exists: the cost-6 solution was excluded by design. A bound value is not itself a saved route, and an unfinished search cannot establish the completed-search conclusion.

1. The search explored fully and found no route cheaper than the bound — genuine failure to improve it.
2. Or the initial settings prevented even finding an existing feasible route (for instance, because pruning excluded everything at or above the bound).

For practice questions 1–2, use the Part 1 BFS, DFS and weighted exit-comparison labs. The Part 2 heuristic labs keep S as their course-tree goal. Questions 3–4 use this part’s A* and branch-and-bound labs.

The worked answers in this section illustrate beautifully how every search outcome is forced by the algorithm’s frontier rule, not by any magic attached to a method’s name. Walk through each one with that lens:

• DFS reaches B late. In the stated insertion order, other paths were pushed onto the stack after B and so sit above it. Since DFS always takes from the top (most recent), those newer candidates are explored first; B waits below until they are exhausted or a dead end forces backtracking. It is purely stack discipline — nothing about B being “far” made it late.
• BFS selects B directly after A. With a queue, B was discovered right at the start (as A’s child) and so sits near the front; FIFO order brings it out almost immediately. Same goal, opposite timing — because the data structure differs.

The weighted example then delivers the cost lesson:

• A route with more transitions can still be cheaper in real cost if its edges are inexpensive; a shortest-in-steps path may traverse one very costly link. Which “best” you get depends on the algorithm’s objective (steps vs. weighted cost).

For A*, the decision is again arithmetic:

• Not because E “looks closer” or has a better name — but because, summing what is already spent (g) with the remaining guess (h), E’s overall estimated completion cost is lower. The number decides.

And for branch-and-bound: a strict initial bound of six excludes any solution whose cost equals six, not merely those above it — because “improve strictly below 6” rejects equal-to-6 answers by definition.

• Each of these results follows directly and mechanically from the algorithm’s rule. That is the deep takeaway: if you know a method’s frontier/selection/pruning logic, every behavior — even surprising ones — can be predicted and explained without appealing to intuition or luck.

The deepest way to understand everything in this lecture — both parts of it — is a single phrase: search is controlled exploration. Left alone, your problem is an enormous (often astronomically large) collection of possibilities. Search transforms that chaos into an orderly, methodical investigation by imposing structure at every level:

• A sound representation defines legal states and actions. We decide what counts as a situation worth tracking and which moves are permitted — this is the map on which all exploration happens. Get it wrong and everything downstream inherits the error.
• The frontier records unfinished paths. Rather than juggling every possibility at once, we keep only those candidates not yet fully explored, organized so they can be selected sensibly.
• A selection rule decides where effort goes next. This single choice — oldest, newest, cheapest-so-far, best-estimated-completion — determines the algorithm’s entire personality and guarantees.

Two accelerators refine this control:

• Heuristics (informed methods) steer effort toward promising regions using cheap estimates of what remains;
• Pruning (as in branch-and-bound, or closing visited states) discards whole branches that cannot possibly matter.

Admissibility protects the completion lower bounds used by A* and branch-and-bound. Consistency lets graph A* close a state after its best path is selected, with sound duplicate handling. Greedy and heuristic DFS can use the same admissible estimate yet still lack a minimum-cost guarantee. Always distinguish the estimate’s property from the selection rule and the implementation policy.

This leads to the central habit of the whole course on search — a reflex worth practicing constantly:

Every claimed property — speed, completeness, optimality, memory use — must be traceable back to the specific rule and assumptions that produce it.

• If someone says “this method is complete,” ask: under which conditions? (finite branching? bounded depth?)
• “Optimal”? Under what heuristic or cost assumptions?
• “Uses little memory”? Which data structure, and how are paths stored?

Anchor every property in its mechanism and you will never be fooled by a name — the single most transferable skill from this entire lecture.

This section is simply your guide to going deeper if you want more detail than this handout provides. Two resources complement what you have read:

• The original course resource supplies the running search tree and its exact numerical costs and heuristic values used throughout the lecture — useful for redoing every example with precise numbers in hand.
• The linked textbook chapter develops the general framework, individual strategies (BFS, DFS, uniform-cost, greedy, A*, branch-and-bound) and pruning conditions in considerably greater depth than a single handout can manage.

When should you reach for these references?

1. Checking assumptions behind a guarantee: when you want to confirm exactly which conditions (admissibility, consistency, nonnegative costs, finite branching) a theorem requires — the textbook will state them rigorously.
2. Comparing tree search with graph search: the differences in bookkeeping and guarantees between these two settings deserve careful study, and the text explores that distinction thoroughly.

The slide details below retain all original links plus the precise comparison material used across the lecture — so they double as a reference deck for quick review. Keep them handy: search is one of those topics where re-reading worked examples with full numbers solidifies understanding faster than almost any other activity.

You have now completed the full arc of search — from blind exploration in Part 1 to guided, optimal and pruning-based strategies here. Check yourself against three core takeaways before moving on:

• Explain what a heuristic estimates. A heuristic h(n) is a cheap-to-compute guess at how much more cost remains to reach a goal from state n — in the same units as edge costs (e.g., straight-line distance estimating remaining road travel). It guides which frontier path to expand next but never replaces the frontier or successor function, and it must be safe (admissible: never overestimate) to support optimality.
• Compare greedy search with the cost-plus-estimate rule in A*. Greedy best-first ranks candidates by h alone — its future estimate only — ignoring how much has already been spent; this can find solutions quickly, but provides no general speed or minimum-cost guarantee. A* uses f = g + h, adding the exact past cost (g) to the future estimate (h); with admissibility, the stated cost conditions, goal tests on selection and sound handling of improved routes, it returns a cheapest selected goal. Its search savings depend on the heuristic and implementation.
• Use a valid bound to explain why a branch can be pruned. In branch-and-bound we maintain an incumbent — the best complete solution found so far. Any partial path whose lower bound (cost spent + underestimate of remaining) cannot beat that incumbent is provably unable to improve it, so pruning it discards nothing valuable and tightens future search.

Now choose one of these ideas and explain it in your own words with an example from this part — for instance, why greedy might return a costly detour route, or how lowering the incumbent cost lets branch-and-bound cut away branches. Teaching it back is the surest way to confirm you have truly mastered informed search.