Uninformed and Informed Search

3.1 Search Problem Formulation Recap

3.1.1 The Five Components of a Problem

The agents that do this are called problem-solving agents (PSA). A problem-solving agent does not act on the first thing it sees; it plans ahead. It simulates sequences of actions inside a model of the world, searches until it finds a sequence that reaches the goal, and then executes that sequence for real. The sequence it finds is called a solution. The four-phase process is: goal formulation (adopt the goal), problem formulation (describe the states and actions needed to reach it), search (simulate action sequences in the model), and execution (carry the found solution out).

To model a problem this way, we must be able to produce five things for any question we are given:

1. Initial state — where the agent starts, written $s_0$. For the road trip: Arad.
2. Goal state (or goal test) — what "done" looks like. Sometimes a single state (Bucharest); sometimes a small set; sometimes a property, as in a vacuum-cleaner world where the goal is "no dirt anywhere". A goal test answers the yes/no question "is this state a goal?" for any state.
3. Possible actions — what the agent may do in each state. Written $\text{ACTIONS}(s)$, it returns the finite set of actions applicable in state $s$. Example: $\text{ACTIONS}(\text{Arad})=\{\text{ToSibiu},\text{ToTimisoara},\text{ToZerind}\}$.
4. Transition model — where each action leads. Written $\text{RESULT}(s,a)$, it returns the state that results from doing action $a$ in state $s$. Example: $\text{RESULT}(\text{Arad},\text{ToZerind})=\text{Zerind}$.
5. Path cost — what each move costs. Written $c(s,a,s^{\prime })$, it gives the numeric cost of applying action $a$ in state $s$ to reach state $s^{\prime }$. For route finding, the cost of an action might be the road length in miles or the time it takes. Path costs are assumed additive: the total cost of a path is the sum of the individual action costs. An optimal solution is the solution with the lowest path cost among all solutions.

The professor's way of checking this: whatever question is given, you should be able to come up with these five components. Writing these five things down is what formulating a problem means.

This sits on top of what was covered before: the PEAS specification (performance measure, environment, actuators, sensors), the different natures of the environment (is it partially observable? static or dynamic?), and the different types of agents (simple reflex, model-based, goal-based, utility-based, learning). A useful link back to the previous lecture: the five-component formulation only makes sense for the environments the search chapter assumes — episodic, single-agent, fully observable, deterministic, static, discrete, and known. If the world is dynamic or partially observable, the same five components still exist, but the search must be re-run or made contingent on what the agent observes.

3.1.2 Worked Examples of Formulation

One subtle point about formulating problems: abstraction. The five components are a model, not the real thing. "Arad" in the model leaves out the radio program, the scenery, the weather, and the traffic — all irrelevant to finding a route. A good problem formulation removes as much detail as possible while keeping a solution easy to carry out: the action "drive from Arad to Sibiu" is useful; "move the right foot forward one centimeter" is not. Formulating a problem is an act of judgment, not just transcription.

3.1.3 Learning Outcomes and Probable Questions

The professor listed the skills this material is expected to produce, which are also the probable question types so far:

• Given a situation (for example, "you are playing chess"), explain the environment: all the aspects from the environment taxonomy.
• Given a situation, argue which agent architecture is best suited — is a reflex agent enough, or do you need a goal-based, utility-based, or more capable design?
• Given a problem, formulate it using the five definitions: initial state, actions, transition, goal, and path cost.

Real-world connection: this formulation style is not classroom decoration. Route-finding web sites and in-car navigation systems are direct extensions of the Romania example — states are locations, actions are roads, costs are travel time. The same five components drive airline travel-planning systems (states there include airport and time, and the action cost mixes money, waiting time, and flight time), robot navigation (states are positions and joint angles), and touring problems such as the traveling salesperson problem, where the goal is to visit every city. Whatever the domain, the agent first needs a well-formed problem — the five components — before any of the search techniques in this lecture can start.

3.2 Uninformed versus Informed Search

3.2.1 Two Categories of Search

Broadly there are two categories: uninformed and informed search. Uninformed algorithms have no information apart from the given problem — the initial state, the goal state, the transitions, and the path costs of the graph they are handed. That is all they may use. They cannot look at a state and guess how close it is to the goal. Informed algorithms get extra information — an estimate that comes from outside the problem — and this extra information is called a heuristic. The name says it: an informed search is being informed, it has something beyond the raw problem statement.

A good way to feel the difference: the uninformed agent in Arad has no clue whether Zerind or Sibiu is the better first step, because it has no knowledge of Romanian geography. An informed agent who knows where each city lies knows Sibiu is far closer to Bucharest and is more likely to be on a shortest path. Same problem, same graph — the only difference is that extra hint.

3.2.2 The Comparison Table

The professor presented a comparison table between the two families (values transcribed as stated; the completeness row was delivered unclearly, so the standard treatment from the reference is given and marked):

Completeness means: are you able to find the goal state or not? The standard treatment: completeness is a property of the specific algorithm, not the family. Among uninformed algorithms, breadth-first search, uniform-cost search, and iterative deepening are complete (BFS and UCS whenever a solution exists, on finite state spaces; UCS with positive step costs); depth-first search is not complete in general. Among informed algorithms, greedy best-first graph search is complete on finite state spaces but not on infinite ones, while A* is complete when its heuristic conditions hold. So "can be complete and incomplete" is true for both families — the row depends on which member of the family you pick and what the state space looks like.

Efficiency is where the families truly differ in spirit. Uninformed search costs more and generates slower results because it explores in the dark; informed search spends less and reaches answers quicker because the heuristic prunes away unpromising paths. The professor's framing: uninformed methods are often called blind searches — you are given just the problem and you grind through it.

3.2.3 Student Questions

3.2.4 Why Move to Informed Search

All the uninformed methods — BFS, DFS, UCS, iterative deepening, iterative lengthening — are slow, and are often called blind searches. You are given just the problem, and you grind through it. The professor's framing: in life, when you are in a difficult situation you do not try to solve it alone; you go to a therapist, a mentor, someone experienced who can guide you. That guidance can help you do better — or it may lead you into a worse situation — but at least you have extra information to navigate by. The same thing holds in the AI world: this extra information or intuition is called a heuristic, it comes from domain experts, and the class of algorithms that use it is called informed search. Informed search, the name itself says it: I am being informed, I have extra information apart from the given problem.

A bridge to the next topics: the rest of the uninformed family — BFS, DFS, UCS, and iterative deepening — are each a specific rule for which node to expand next. Once we meet informed search, each of those rules gains a cousin that uses the heuristic: greedy best-first search expands the node with the smallest heuristic value, and A* expands the node with the smallest value of cost so far plus heuristic. Knowing the uninformed rules first makes the informed cousins easy to understand.

3.3 Breadth-First Search (BFS)

3.3.1 What BFS Does

Breadth-first search (BFS) is the more cautious of the two classic techniques: it examines paths of length $i$ before it examines paths of length $i+1$. It visits a tree or graph level by level — it covers one full level, then the next, then the next. It uses a queue to do the visit, which is FIFO: first in, first out. The name says it: breadth first — cover all nodes at a given depth before proceeding to deeper nodes. All the algorithms discussed in the first part of this topic are uninformed: they only have the graph, possibly with path costs, and nothing else.

Because new nodes are always deeper than their parents, a FIFO queue gives exactly the right order with no extra bookkeeping: old, shallow nodes sit at the front and are expanded first; new, deep nodes join the back. The search also keeps track of reached states so that a state reached once is never reached again — without that check, a cycle like Arad → Sibiu → Arad would let the search loop forever.

3.3.2 Worked Example — Queue Trace

A second, textbook-style view uses colors: the orange nodes have been covered (explored); the gray nodes have been generated but not yet explored — we have not gone there yet. You generate all nodes at a given depth before moving deeper. If the node we are currently at is the goal, we stop there and do not go further; exploring the goal further is unnecessary. The goal can be any node — anything can be a final goal, that is decided in your problem formulation (initial goal, final goal).

3.3.3 The Branching-Factor Problem

BFS has a real weakness. A branch factor is how many children a node has — in this example $A$ has two children. Suppose $A$ has 2000 children, and the goal is somewhere deep on the other side. BFS will first have to go through all 2000 children before it can even come to the next level. If the goal is somewhere beyond them, we waste a lot of time and memory in the full exploration of all the siblings of those nodes. That is one problem with BFS — a branch problem: high branch factor means slow progress toward depth.

The cost of that caution is easy to see on a uniform tree where every node has $b$ children. The root generates $b$ nodes, each of those generates $b$ more, giving $b^2$ nodes at level 2, $b^3$ at level 3, and so on. If the solution sits at depth $d$, the total number of nodes generated is

$$1+b+b^2+b^3+\cdots +b^d=O(b^d),$$

so both time and space complexity are $O(b^d)$. Those exponential bounds are the practical killer: with branch factor $b=10$, a million nodes processed per second, and 1 KB of memory per node, a search to depth 10 takes less than 3 hours but needs about 10 terabytes of memory. BFS's memory demand is usually the bigger problem — it keeps every generated node until the search ends. This is the sense in which BFS "wastes space and time" when the goal is shallow but the branch factor is large.

3.3.4 Applications

Real-world: BFS is used for finding a path in a graph and for finding many solutions of a problem. There is a concept in graph theory called bipartition — a graph whose nodes split into two groups such that every edge runs between the groups — and BFS suits those problems too: color the start node red, its neighbors blue, their neighbors red, and a graph is bipartite exactly when this alternation never creates a conflict. The professor notes these two classic searches are fundamental; both are perfectly useful for particular applications and neither is "better" — they are suitable for different problems, which is more of a data-structures viewpoint.

3.4 Depth-First Search (DFS)

3.4.1 What DFS Does

Depth-first search (DFS) catches hold of one path and goes as deep as possible. When it realizes it cannot go any further, it comes back — backtracks — and tries another path. It maintains a stack (LIFO: last in, first out) to do this, instead of a queue. BFS was cautious: complete one level, then go to its children. DFS is the opposite: from a node, plunge immediately into the first child, then that child's first child, and so on until you hit a dead end.

The stack is what makes DFS what it is. The node added most recently sits on top, so the next expansion always dives into the newest frontier node — the deepest one — instead of the oldest, as a queue would. Since new children are pushed after their parent is expanded, the search immediately descends toward the leaves.

3.4.2 Worked Example — Deep Dive and Backtrack

The professor's second look at the same tree shows the aggressiveness even better: from $B$ we jump straight to $D$, and from $D$ we jump to $H$; when we cannot go further from $H$, we explore $I$; $I$ has no children — it is a leaf node — so we jump back to $E$, and from $E$ we go to $J$, then $K$, and so on. We catch hold of something very deep and, as long as there is a path, we go there aggressively; when we can go no further, we stop and backtrack.

3.4.3 The Depth Problem

Suppose $C$ is the goal. When will DFS actually reach $C$? It will, eventually — but only after the deep dive. If $D$ also has a child $H$, and $H$ has children, and so on — a structure called a skewed tree, with many children in one direction — DFS gets into a loop of going deeper and deeper, and the goal, which is off to the side, is missed for a long time. This is the opposite of BFS's problem: in BFS we explored sibling branches and wasted time; here it is not a branch problem, it is a depth problem. We keep going deep in one direction and only when we reach the leaf do we come back and eventually reach $C$.

The memory benefit of DFS is real, though: a tree-like DFS without a reached table keeps only the current path, so space is $O(bm)$, where $b$ is the branching factor and $m$ is the maximum depth of the tree. Problems that would need exabytes of memory under BFS can be handled with kilobytes under DFS. But the price is that DFS is not complete in general — in a cyclic state space it can loop forever (unless cycles are checked), and in an infinite state space it can wander down an infinite path. It is also not cost-optimal: it returns the first solution it finds, even if another path is far cheaper.

Neither algorithm is discarded: both have benefits. If the graph is small, nothing of this really matters — they are all the same on small inputs. And each has particular applications where it shines.

3.4.4 Applications

Real-world: DFS is intuitively better for connectedness questions. Suppose we want to know whether two people, call them X and Y, are friends in a social network graph. Catch hold of one of them and do DFS: go as deep as possible along one path — X → friend A (a dead end) — then backtrack and take another: X → friend B → friend C → Y. If we meet the other person's name anywhere along a path, they are connected; otherwise they are not. DFS answers this more simply than BFS. Similarly, topological sort in sorting techniques can be done with just DFS, and it will always give you the topological ordering — list tasks so that every task appears after all of its prerequisites. These are just two examples; a lot of things can be done with these two searches.

3.5 Uniform Cost Search (UCS)

3.5.1 Definition and Rules

Uniform cost search (UCS) is also called cheapest first. It is essentially BFS, but with costs. Instead of expanding the shallowest node, UCS expands the node $n$ with the lowest path cost $g(n)$ — the sum of edge costs from the start node to $n$. Two rules matter:

• Sort the frontier. Whenever we put something into the queue, we should immediately sort the queue. Otherwise we get misled: the node at the front of the queue might have a higher cost than something behind it. So we sort again and again, then pick the first element. The frontier is whatever is in the queue right now. We are not forced to use a priority queue — a normal queue that we sort works; a priority queue implemented with a min-heap would also always give you the minimum at the start, but any data structure is fine as long as the order is sorted.
• Test the goal during expansion, not during generation. When we generate a new node (discover that it exists as a successor), we do not stop, even if it is the goal state. We only claim the goal when that node is expanded — pulled off the queue for exploration.

The weights are actual, measured quantities: kilometers, miles, or fare — they come from real empirical data of the problem at hand, not from any estimate.

3.5.2 Worked Example — Romania

3.5.3 Student Questions

3.5.4 Where UCS Stands

At the end of the day UCS is nothing but BFS plus costing — the sorting on top. The known costs: memory usage is more, complexity is more, and so on. The worst-case time and space complexity is $O(b^{1+\lfloor C^{\ast }/ϵ\rfloor })$, where $C^{\ast }$ is the cost of the optimal solution and $ϵ$ is the smallest step cost. When all step costs are equal, $b^{1+\lfloor C^{\ast }/ϵ\rfloor }$ reduces to $b^{d+1}$ and UCS behaves like BFS. The exponent shows why UCS can be expensive: it will happily explore large trees of cheap actions before touching a single expensive-but-useful edge.

Real-world connection: UCS is exactly what a "cheapest-first" planner needs when costs are real measured quantities — route planning by kilometers or miles, fare minimization, and any graph problem where the edges carry empirical prices rather than unit steps. Because it is Dijkstra's algorithm under an AI name, every industrial shortest-path problem (network routing, logistics, GPS precomputation) is a uniform-cost search in disguise.

3.6 Iterative Deepening Search

3.6.1 The Idea

BFS has the branch-factor problem: with many branches we explore everything at one level before the next, wasting space and time. DFS has the opposite problem: the goal may sit somewhere in the breadth, but because DFS is aggressive it catches one path and keeps going, wastes space and memory, and may reach the goal too late — or not be optimal. Iterative deepening search (IDS) fixes both by applying DFS, but iteratively, with a growing depth limit. We show the graph only partially: first only the node at limit 0; then the children at limit 1; then one more level at limit 2; and so on, until the goal is found. The professor's explanation: "I will show you the graph partially — I'll hide the graph for you. First I'll show you only limit 0, then the first level, then the second level of children. I'm applying DFS in an iterative fashion so I don't get into that worst case where I keep going in one direction and get lost." We are not deciding a limit ahead of time — we start at zero and increment until we find the goal.

3.6.2 Worked Example — Growing Limits

3.6.3 Iterative Lengthening Search

If we can do DFS iteratively for the depth problem, can we do the same for the branch problem? Yes — that is iterative lengthening search: instead of increasing the depth limit, we increase the cost limit and run BFS (or UCS) within it, showing the graph partially and expanding when no goal appears. It can be described as a modification of UCS or BFS that runs iteratively. In the same way, iterative lengthening is not as bad as regular BFS in the worst cases: with a 2000-child node, iterative lengthening shows only part of the structure at a time and expands when no goal is found, so it never sweeps all 2000 siblings before making progress.

3.6.4 Student Questions

3.6.5 Choosing a Search Algorithm

Recap + bridge. IDS = DFS with a leash: run depth-limited DFS at limit 0, 1, 2, ... until the goal appears, buying BFS-like completeness and DFS-like memory. This closes the uninformed family. From here the lecture changes direction: every uninformed algorithm is slow because it searches blind, and the fix is a heuristic — the topic of the next section.

3.7 Heuristic Functions and Informed Search

3.7.1 What a Heuristic Is

Informed search is more useful for large search spaces — a state space is the transition diagram we draw, and for something like chess it is far too big to draw at all; every move produces a different state. Informed search algorithms use the idea of heuristics, so the family is also called heuristic search. A heuristic function is a function used in informed search that finds the most promising path, cost, or solution. It takes the current state of the agent as its input and produces an estimation of how close the agent is to the goal:

$$h(n)=\text{estimated cost of the cheapest path from the state at node }n\text{ to a goal state.}$$

It does not promise the best solution — the heuristic method might not always give the best solution, but it is guaranteed to find a good solution in reasonable time. Two practical notes: the heuristic function is not probabilistic — it is a deterministic function; you put values in, you get an answer. And in many cases — including in exams — you will be given the heuristic function, or even the promising path directly; do not worry about how it is derived.

Where the estimate comes from matters less than what it does: a node is selected for expansion based on an evaluation function that estimates the cost to the goal. The heuristic is the ingredient that turns a blind algorithm into an informed one.

3.7.2 Good versus Bad Heuristics

There are two aspects of any heuristic: a good one and a bad one. There are proofs and standard ways to decide which is which — admissibility and consistency — which are covered in the next topic. The intuition: before applying a heuristic to a problem, evaluate it fairly. The professor's analogy: before a career switch you ask three people for advice; if one of them gives you useless advice, you immediately see it and discard that heuristic and go with another. So you evaluate heuristics, decide if they are good or bad, and then apply them to the problem.

3.7.3 Student Questions and Analogies

3.7.4 Where Heuristics Come From

For the whole of this session, every heuristic value is human-given: a domain expert supplies the estimate before the algorithm runs. The heuristic is not updated at runtime. But there is a whole class of learning heuristics techniques where the heuristic itself learns from patterns — that is part of this course's curriculum this semester, and a good amount of the next session is spent on how a heuristic can learn, how to create these functions, how to decide good versus bad, and specific use cases for heuristics (like databases and similar).

Real-world: Google Maps relies heavily on heuristics of exactly this kind, though the real system is far more advanced (see the informed-search sections). The frontier of practice is learning heuristics: instead of paying a domain expert for every new domain, algorithms learn the heuristic function from patterns in the data — which is where the course goes next.

3.8 Greedy Best-First Search (GBFS)

3.8.1 Definition

Greedy best-first search (GBFS) is an informed search technique that takes heuristics very seriously — it works only on the heuristics. Whatever heuristic value is given, that alone drives the search; the actual path costs are ignored completely. The evaluation function is simply the heuristic itself:

$$f(n)=h(n)$$

where $f(n)$ is the evaluation used to pick the next node, and $h(n)$ is the heuristic value — the estimated cost from node $n$ to the goal (not an actual measured value, just the estimate someone gave us). GBFS expands the node with the smallest $h(n)$.

Reading the heuristic table correctly matters: every value $h(n)$ means "from node $n$ to the goal". Bucharest has $h=0$ because it is the goal — if you are already in Bucharest, it takes 0 kilometers to reach Bucharest. Arad's 366 means "if you are in Arad, it will take about 366 kilometers (or whatever metric) to go to Bucharest." These numbers come from a domain expert — someone who knows the whole region and its intuitions and hands you this data.

3.8.2 Worked Example — Romania

3.8.3 Worked Example — Five-Node Graph

3.8.4 Why GBFS Is Not Optimal

GBFS is not optimal. Two reasons are worth separating. First, it is greedy: a greedy algorithm takes what is best at the current moment without regard to future consequences. Greedy never promised the best possible way — it optimizes only for the current situation. Second — and this is the professor's deeper point — GBFS did not fully use the knowledge it had: the actual path costs were sitting right there in the problem, and it ignored them. It is the person who just believes others' advice and does not introspect: "You already know what is best for you. You're also taking advice. Why are you just believing on others' advices? Look at your data also. Think about yourself also."

Note the careful phrasing: GBFS did not take the wrong path — it took you to the goal — but its path cost was not optimal. In the five-node example it reached node 5 with cost 225, while the graph offers routes the search never priced: 1 → 2 → 5 = $100+125=225$, 1 → 2 → 3 → 5 = $100+50+125=275$, 1 → 3 → 5 (the route taken), and the routes through node 4 (1 → 3 → 4 → 5 and 1 → 2 → 3 → 4 → 5), each with its own cost. The lecture's point stands whichever route you price: the greedy search picked its path from the heuristic alone, so optimality was never even on the table.

In worst cases GBFS graph search is complete only on finite state spaces (on infinite spaces it can chase an ever-decreasing heuristic forever), and its worst-case time and space are $O(|V|)$ — though with a good heuristic it typically explores far fewer nodes than that, in favorable cases dropping to $O(b^m)$.

3.8.5 Student Questions and Answers

The same reading rule answers the next pair of questions about where heuristics come from and what happens to the start node's own value.

Now the questions that circle the real weakness — optimality — and what GBFS never looks at.

Two questions connect GBFS to its cousins — Dijkstra's algorithm and the informed family.

And the vocabulary question that trips up many students — it matters for exam traces.

Recap + bridge. GBFS trusts the heuristic alone: $f(n)=h(n)$, expand the smallest. It reaches the goal fast, but ignores the actual costs it has, so the path can be expensive — the person who believes every piece of advice and never introspects. The fix is to use both inputs — and that is precisely what A* does next: $f(n)=g(n)+h(n)$.

3.9 A* Search

3.9.1 Definition and Evaluation Function

A* search is one of the best and most popular techniques in pathfinding and graph traversal; a lot of games and web-based maps use it to find the shortest path efficiently. It is essentially a best-first search algorithm, an informed search technique that works with heuristic values. A* maintains a tree of paths originating at the start node, extends those paths one edge at a time, and continues until its termination criteria are satisfied. The core idea: avoid expanding paths that are already expensive.

A* extends the path that minimizes the evaluation function

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

where:

• $g(n)$ is the cost so far to reach node $n$ from the start node — the actual cost incurred, summed along the edges. It is 0 for the start node, because we have not come from anywhere.
• $h(n)$ is the heuristic value — the estimated cost from $n$ to the goal. It is 0 for the goal node, because the estimated cost from the goal to the goal is 0.
• $f(n)$ is the estimated total cost of the path from the start to the goal passing through $n$ — the two quantities added.

Compare with GBFS, where $f(n)=h(n)$ directly: no path cost considered, whatever the intuition says, take that. A* says: add the heuristic to the actual cost incurred so far. If both together are already expensive, the path is misleading me — so do not take it. This is the more cautious, better informed algorithm.

3.9.2 Worked Example — Five-Node Graph

A common student slip — the professor flags it as "very, very important": do not carry the 140 forward to node 5. The 140 was the $f$-value of node 4. Once we expand node 4 and generate node 5, we compute $f(5)$ from scratch with its own $g$ and $h$: the cost incurred so far (100 + 50 = 150) plus the heuristic of node 5 (0). The re-explanation walkthrough: "What is the cost to come till here? That is 1 to 4 plus 4 to 5. 1 to 4 is this 100, and 4 to 5 is this 50. 100 plus 50. What is the heuristic value of 5? It is 0, because I am already in the goal. So 100 + 50 + 0 = 150. You are done."

3.9.3 Worked Example — Romania

3.9.4 Student Questions and Answers

Recap + bridge. A* balances both inputs: $f(n)=g(n)+h(n)$, expand the smallest, claim the goal only at expansion, and always compare every leaf in the queue. It found 418 in Romania where GBFS found 450. But "A* is optimal" has a condition attached — the heuristic must be admissible and consistent. That condition is the final topic: it decides when A*'s guarantee actually holds.

3.10 Admissibility and Consistency

3.10.1 Admissibility

A* is optimal when the heuristic satisfies two conditions: admissibility and consistency.

A heuristic is admissible if it never overestimates the actual cost to reach the goal:

$$h(n)\le h^{\ast }(n)$$

where $h(n)$ is the heuristic value you were given (as in all the problems so far), and $h^{\ast }(n)$ is the true cost from node $n$ to the goal — the real, actual cost found in the graph. Students sometimes want to put $g(n)$ here; that is wrong. $g(n)$ is the cost taken from the initial node to arrive at node $n$. $h^{\ast }(n)$ is from node $n$ to the goal — a different quantity entirely.

Real-world: straight-line distance is admissible for route planning, because the actual road cost between two places cannot be shorter than the straight-line distance between them. No road is a perfectly straight line — they all bend, so the true driving distance is at least the bird's-eye distance. That makes straight-line distance a natural admissible heuristic for maps.

3.10.2 Consistency

How close the heuristic is to the true value matters, and that is what the second condition, consistency (also called monotonicity), captures. A heuristic is consistent if, for every node $n$ and every successor $n^{\prime }$ of $n$:

$$h(n)\le c(n,n^{\prime })+h(n^{\prime })$$

where $c(n,n^{\prime })$ is the actual cost of the step from $n$ to $n^{\prime }$, and $h(n)$, $h(n^{\prime })$ are the heuristic values of the two nodes. The plain-language meaning: the estimated cost should not suddenly drop by more than the actual step cost. As we move towards the goal, the heuristic should reduce gradually — the estimate decreases along the path, but no faster than the real step cost justifies.

Example of the intuition: $h(\text{Pitesti})=100$ and $h^{\ast }(\text{Pitesti})=101$ — the estimate is close to the truth. A value of 10 would also satisfy admissibility (10 < 101, no overestimate), but 10 is not close to the actual 101 — a weak guide. Closeness is what distinguishes a good heuristic from a merely admissible one.

3.10.3 Why Consistency Matters

If a heuristic is consistent, $f$-values do not decrease along the path. This means: once A* expands a node, the best path to that node has already been formed — there is no danger that a later, cheaper route to the same node appears. If this property is not satisfied, "we will go for a toss": the search can re-find nodes more cheaply, and the optimality guarantee breaks down. Both conditions — admissibility and consistency — must hold for all nodes; then A* is optimal and you will definitely get the correct answer. Otherwise A* is not optimal.

The reasoning in one breath: moving from $n$ to $n^{\prime }$ changes $f$ from $g(n)+h(n)$ to $g(n)+c(n,n^{\prime })+h(n^{\prime })$. The $g(n)$ cancels, and the $f$-value is non-decreasing exactly when $h(n)\le c(n,n^{\prime })+h(n^{\prime })$ — which is precisely consistency. So with a consistent heuristic, A* expands nodes in order of non-decreasing $f$; the first time it pops a node, that node has already been reached by its cheapest possible path, and the first goal popped is the cheapest goal.

3.10.4 Student Questions

3.10.5 Exercises for the Next Class

Two exercises were set. First, planning and problem formulation — three problems, and for each you should formulate the five components (initial state, goal state, actions, transitions, path cost) and, as extra practice, do the PEAS and environment definition as well: planning a trip with a delivery drone; solving a maze; scheduling patient appointments in a clinic. Second, an A* trace: a graph is given with data — the start, the goal, actual costs, and heuristic values $h(s)$, $h(n)$, and so on — run A* on it and report the search. A third task will be done together next class: for each node of a given graph (with node 3 as the goal), check whether the given heuristic is admissible, and then check consistency — the class already agrees on the admissibility answers, and the consistency check via the formula $h(n)\le c(n,n^{\prime })+h(n^{\prime })$ will be worked through together.

Recap + bridge. Admissibility keeps the heuristic optimistic ($h(n)\le h^{\ast }(n)$); consistency keeps it from dropping too fast ($h(n)\le c(n,n^{\prime })+h(n^{\prime })$). Together they make $f$-values non-decreasing, so the first goal A* expands is the cheapest — that is when A* is optimal. This closes the lecture's arc: from the five-component formulation, through the uninformed family, to heuristics, GBFS, A*, and the conditions that make A* trustworthy. Next class turns to the heuristics themselves — how they are created, and how they can be learned.

Exam Guidance Summary

• Mid-semester exam talk: the professor will discuss the mid-sem exam in the 8th class and will upload a sample paper then; the same happens before the final exam. The ACI exam usually falls in the second week of the exam schedule, so there is preparation time after the discussion.
• Sample papers: the course has changed a lot — many topics were removed and new ones added — so some past papers may not be relevant. The advice is explicit: do not get bogged down by sample papers and exam preparation; there is no correlation between solving past papers and performing better, and it can do more harm than good. Attend all classes, explore the topics, and you will fare well; the quiz, the assignments, and the final exam are other avenues.
• Probable question types so far (learning outcomes):
• PEAS specification for a given situation; judging an environment (e.g., chess) across its different aspects.
• Choosing the best-suited agent architecture (reflex vs goal-based vs utility-based, etc.).
• Formulating a problem with the five definitions: initial state, actions, transition, goal, path cost.
• Tracing uninformed searches — BFS, DFS, UCS, iterative deepening — and knowing the intuition for when each fits (e.g., maze → DFS; unknown depth, large tree → iterative deepening). The animations are not exam questions, but they form the basis of the techniques.
• Tracing GBFS given a graph, heuristic values, start and goal: expanded nodes, generated nodes, queue behavior (max queue length), the path, and its actual cost.
• Tracing A* given the graph, $g$, $h$, source, and goal: produce the state-space trace, the path, and the cost. When multiple shortest paths tie, use lexicographical (alphabetical) ordering in exams.
• Admissibility and consistency of a heuristic, and what they guarantee about A* optimality: $h(n)\le h^{\ast }(n)$ for admissibility; $h(n)\le c(n,n^{\prime })+h(n^{\prime })$ for consistency, checked per node and per edge.
• Study resources: the uninformed-search animations (play with your own inputs); the data-structures material on the course page, only if you lack a CS background (queues, stacks); the lab activity where BFS and DFS are implemented — the recording and the Python program are available if you want to see the algorithms in code.

Key Industry Applications

• BFS: finding a path in a graph, finding many solutions, and graph-theory problems such as bipartition — checking whether a network can be split into two groups with no edges inside a group, useful in scheduling and matching problems.
• DFS: quickly checking connectedness in a graph — e.g., are two people connected in a social network (walk from one, go deep, backtrack until you either meet the other person or exhaust the paths) — and topological sort, which DFS always produces in the correct ordering, a staple of build systems and task scheduling (a task is listed only after its prerequisites).
• UCS: cheapest-first route planning with real measured costs — kilometers, miles, or fares from actual empirical data. Under its other name, Dijkstra's algorithm, it is the workhorse of network routing: computer networks, logistics, and shortest-path services all run uniform-cost ideas at scale.
• A*: pathfinding and graph traversal in a lot of games and web-based maps; it finds the shortest path efficiently by balancing cost so far with the heuristic. Video-game enemy AI, GPS navigation, and robotics motion planning are the classic A* consumers.
• Google Maps (with a warning): it does not use just A* — it is far more advanced because its environment is dynamic: accidents get reported, routes change, users report roadblocks, and those inputs act as heuristics that are updated live. It uses sophisticated machinery, but it all boils down to these fundamentals.
• Heuristics in practice: domain experts supply the estimates (like a city guide's travel-time estimate); heuristics must be evaluated (admissibility, consistency) before use; and the frontier of practice is learning heuristics — algorithms that learn their own heuristics from patterns, covered later in the course.