Heuristic Approaches: Guided Problem Solving, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 4.4 Free with a free account

Heuristic Approaches: Guided Problem Solving

Introduction to Artificial Intelligence · Chapter 4: Search, Heuristics, and Game StrategySection 4.4 · lesson 26 of 6913 min · free with a free account

← Blind and Competitive Search StrategiesNext lesson: Strategic Reasoning: Game Theory in Intelligent Systems →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

How heuristics guide greedy best-first search and A* toward goals.

  • Define a heuristic function and give examples for routes, puzzles, and grids
  • Trace greedy best-first search and A* and explain why they can return different routes
  • Test whether a heuristic is admissible and consistent
  • Design admissible heuristics by relaxing a problem and compare them by dominance

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,909 words). Read along, or search it.

Opening Question

Driving With a Straight-Line Hint

You're driving to a city you've never visited, with no map and no signs. You could try every road in turn: reliable, but slow. Now your phone tells you, at every junction, how far the destination is in a straight line. That hint doesn't name the road. But it lets you favor the junctions that look closer. So how should a search program use advice like that, without being fooled by it?

Definition

The Heuristic Function h(n)

That hint is a heuristic function, written h(n). It estimates the cost of the cheapest path from a state n to the nearest goal. It's a rule of thumb, quick to compute, because it's evaluated for many states. h is never negative, and h of the goal is zero. For a road route, use the straight-line distance. For a sliding-tile puzzle, count the misplaced tiles, or add up each tile's distance from its goal square. And for a robot on a grid, count the rows plus the columns to the target.

Best-First Search

Evaluation Functions for UCS, Greedy, and A-Star

Informed search uses such an estimate to decide what to explore next. Most informed methods are best-first. They keep a frontier: the states discovered, but not yet expanded. And they always expand the frontier state with the lowest value of an evaluation function, f of n. Uniform-cost search uses f equals g, the cost paid so far, with no sense of direction. Greedy best-first uses f equals h, the estimate alone. And A* adds them: f equals g plus h.

Comparison

Greedy Best-First Versus A-Star

Greedy best-first expands whatever looks closest to the goal. With a good hint, it's fast, and light on memory. But it ignores what the journey has already cost, so it can be lured onto a route that looks close, but is long. It doesn't guarantee the cheapest path, and without a check for repeated states, it can wander in circles. A* fixes this. g of n is the exact cost of the best path found so far, from the start to n. h of n estimates the rest. Their sum, f, estimates the whole trip.

Algorithm

A-Star Search Step by Step

Here's A* in plain words. Put the start state on the frontier. Then take off the state with the lowest f. If it's a goal, stop. Otherwise expand it. Each successor's g is the parent's g plus the step cost. If it's already waiting with a higher g, keep the cheaper path. Then repeat. One detail matters a great deal. The goal test happens when a state is removed, not when it's first generated. A goal can be found early, by an expensive route, while a cheaper route is still waiting.

Running Example

A One-Way Map With h Values

Here's a small map. Roads run one way, left to right, from the start, S, to the goal, G. From S, a road costs 3 to A, and 2 to B. From A, one road goes straight to G, and costs 9. From B, a road costs 2 to C, and from C, it's 3 more to G. Beside each state is its h value: 5 at S, 2 at A, 5 at B, 3 at C, and 0 at the goal.

Greedy Trace

Greedy Takes the Route Costing 12

Greedy first. From S, it sees A, with h 2, and B, with h 5. A looks closer, so greedy expands A. That puts the goal on the frontier, with h 0. It expands G, and stops: three steps, and the route S, A, G costs 3 plus 9, which is 12. A looked close, and greedy never noticed that the road from A to G costs 9.

A* Trace

A-Star Finds the Route Costing 7

Now A*, which ranks states by f equals g plus h. Start with S: g is 0, and h is 5, so f is 5. Expanding S gives A, with f equal to 3 plus 2, or 5, and B, with 2 plus 5, or 7. A has the lowest f, so A* expands it. That reaches G, with g equal to 12, so its f is 12. The goal is on the frontier now, but A* doesn't stop. B, at 7, is lower than 12. Expanding B reaches C, also at f 7. Expanding C reaches G again, with g equal to 4 plus 3, which is 7. That replaces the old entry at 12. Now G has the lowest f. It's removed, and A* stops. The route is S, B, C, G, costing 2 plus 2 plus 3: 7.

Interpretation

Weighing a Hint Against Cost Paid

A* found the cheaper route. G waited at 12, while B and C had lower f values. The g term exposed the trap: A looked close, but its route cost 12. So that's how to use a hint without being fooled: weigh it together with the cost already paid. The price is effort: A* took five steps, against greedy's three.

Common Mistake

An Overestimate Hides the Better Route

But what if an estimate is too high? Suppose h of B were 11, though B is really only 5 from the goal. Then f of B is 2 plus 11, which is 13. After A* expands A, the frontier holds G at 12, and B at 13. So G comes off first, and A* returns the route that costs 12. An overestimate hid the better route.

Quick Check

Order of A-Star Expansions on a New Map

Quick check, on a new map. From S, a road costs 2 to D, and 1 to E. From D to the goal costs 4, and from E, 7. The h values are 3 at S, 3 at D, 2 at E, and 0 at G. In what order does A* expand the states? Pause, and decide. S, then E, then D, then G. E goes first, because its f is 1 plus 2, which is 3. It reaches G at 8. But D is waiting at 2 plus 3, which is 5, below 8. So A* expands D, which reaches G at 6, and replaces the 8. Then G comes off at six. S, E, G is tempting, but it stops at the first goal generated. S, D, G skips E's lower f.

Key Properties

Admissible and Consistent Heuristics

Let h*(n) be the true cost of the cheapest path from n to a goal. Two properties say when a heuristic can be trusted. It's admissible if it never overestimates: h of n is between zero and h-star of n, for every state. It's optimistic. It's consistent, or monotone, if for every step from n to a successor n-prime, h of n is at most the step cost plus h of n-prime. That's a triangle rule. The estimate from n can never exceed taking one step, and then trusting the estimate from there. Consistency implies admissibility, but not the other way around.

Guarantees

When A-Star Stays Optimal

With an admissible heuristic, the first goal A* removes is on a cheapest path, if repeated states aren't thrown away. With a consistent one, f never decreases along a path. Each state is first expanded by a cheapest path, so none is reopened, and graph search stays optimal.

Verification

Testing the Map's Heuristic

The map's heuristic passes both tests. Admissible: 5 at S is below the true 7, 2 at A is below 9, and B, C and G match their true costs exactly. Consistent: on every road, h is at most the cost plus the next h. S to A: 5 against 3 plus 2. A to G, B to C, and C to G pass the same way.

Counterexample

Admissible but Inconsistent at S

Now change h of S to 7. It's still admissible, since the true cost from S is 7. But the road from S to A breaks the triangle rule: 7 is more than 3 plus 2. You can see it in f. Along that road, f falls from 7 to 3 plus 2, which is 5. When f can fall along a path, the heuristic is inconsistent. In practice, natural heuristics, like straight-line and grid distance, are consistent.

Heuristic Design

Relaxing the Problem's Rules

How do you invent an admissible heuristic? Relax the problem: remove some rules, and use the exact cost of the easier problem as the estimate. Fewer rules can only make solutions cheaper, or equal. So the estimate never overestimates, and relaxed costs are consistent, too. Let a tile jump straight to its goal square, and you get misplaced tiles. Let it slide onto any neighbor, even an occupied one, and you get the sum of distances. Let roads run straight between any two places, and you get straight-line distance.

Worked Example

Misplaced Tiles Versus Summed Distances

Here's an eight-tile puzzle. Top row: 4, 1, 3. Middle row: 2, a blank, then 5. Bottom row: 7, 8, 6. The goal has 1 through 8 in order, with the blank last. The first heuristic, h1, counts misplaced tiles. Tiles 4, 1, 2, 5 and 6 are out of place, so h1 is 5. The second, h2, adds each tile's distance. Tile 2 is two squares away, and the other four are one away each. So h2 is 6. Six moves are enough to solve this puzzle, and h2 never overestimates. So here, 6 is exactly right.

Dominance

Why Summed Distances Dominates

Both are admissible, but h2 is never smaller than h1, because every misplaced tile adds at least 1 to the distance total. When that holds for every state, and both are admissible, h2 dominates h1. A* with the dominating heuristic is still optimal, and it expands no more states, apart from ties. In classic experiments on puzzles needing about 24 moves, summed distances examined more than twenty times fewer states than misplaced tiles.

Evaluation

What Makes a Heuristic Good

A good heuristic is admissible, ideally consistent, close to the true cost, and cheap to compute. h equals zero gives no guidance: A* acts like uniform-cost search. Misplaced tiles is cheap, but weak. Summed distances is stronger, and still cheap. Twice the summed distances is often faster, but a puzzle one move from the goal gets an estimate of 2. It overestimates, so optimality is lost.

Trade-Offs

Combining Heuristics and Memory Limits

With several admissible heuristics, take the largest value for each state. That's still admissible, and at least as informative. But a perfect heuristic costs as much as solving the problem, and a slow one can lose more than it saves. And A* keeps every generated state in memory, so on large problems, memory often runs out first.

Quick Check

Admissible but Not Consistent

Quick check. A road runs from P to Q, costing 2, and from Q to the goal, costing 6. So the true cost to go is 8 from P, and 6 from Q. Three estimates. X gives 7 at P, and 6 at Q. Y gives 8 at P, and 3 at Q. W gives 6 at P, and 7 at Q. All three give 0 at the goal. Which estimate is admissible, but not consistent? Pause, and decide. Y. It never overestimates: 8 is not above 8, and 3 is not above 6. But the step from P to Q breaks the triangle rule: 8 is more than 2 plus 3, which is 5. X passes both tests. W is the tempting one, because 6 at P looks modest. But 7 at Q is more than the true 6, so W isn't even admissible.

Key Takeaways

Greedy, A-Star, and Admissibility Summed Up

To sum up. A heuristic, h of n, estimates the cost left to a goal. Greedy uses h alone, and can return a costly route. A* uses g plus h, and tests for the goal when a state leaves the frontier. An admissible estimate never overestimates, and keeps A* optimal. Relaxing a problem designs admissible heuristics, and a dominating heuristic expands no more states.

Reflection

A River in the Way

Here's something to think about. You're walking across a city, and your phone shows only the straight-line distance. When could that number alone lead you astray, say with a river in the way? And which part of A* would fix it?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Heuristic Approaches: Guided Problem Solving

What is a heuristic function in AI search?
A heuristic function, h(n), estimates the cost of the cheapest path from a state n to the nearest goal. It is a quick rule of thumb, never negative, and zero at the goal. Common examples are straight-line distance for road routes, the number of misplaced tiles or the sum of tile distances for a sliding-tile puzzle, and rows plus columns for a robot on a grid.
What is the difference between greedy best-first search and A*?
Greedy best-first search expands the state with the lowest h, the estimate alone, while A* expands the lowest f equals g plus h, adding the cost already paid. Greedy is fast but can be lured onto a route that looks close yet costs more. With an admissible heuristic, A* returns a cheapest path, usually at the price of expanding more states.
What is the difference between an admissible and a consistent heuristic?
An admissible heuristic never overestimates the true cost to a goal, while a consistent one also obeys a triangle rule: h(n) is at most the step cost to a successor plus h of that successor. Consistency implies admissibility, but not the reverse. With a consistent heuristic, f never decreases along a path, so A* graph search never needs to reopen a state.
How do you create an admissible heuristic?
Relax the problem by removing some rules, then use the exact cost of the easier problem as the estimate. Fewer rules can only make solutions cheaper or equal, so the estimate never overestimates. Letting puzzle tiles jump straight home gives misplaced tiles; letting them slide onto any neighbor gives summed distances, which dominates misplaced tiles and usually makes A* expand far fewer states.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →