I would like to kind of give you a drastic thing, right?

If you want to go from A to B, say from Edinburgh to Zabrokan or Alangan or so, it doesn't matter.

Then you have the problem of finding a route.

Something that Google does for you.

And it will say, start in Edinburgh, go to Leeds, London, Birmingham, go somewhere there.

Which is a non-trivial problem.

If you want to relax it, one way of doing this is to throw away the map.

And you can do it.

So, by the way, Google can do that too.

So without a map, we know we just drive in a straight line and that gives us the solution.

The solution to the relaxed problem.

And that's really the effect we want to use.

Relaxed problems can be easier to solve.

And we can use the exact solutions to this problem.

In this case, 1000 kilometers as a heuristic.

And if you think about it, the exact solution to the relaxed problem gives you quite a good estimate of what you want to do.

There are problems with that.

The exact solution doesn't actually work.

For instance, there's no ferry that goes from here to here.

There are ferries that go from here to here.

There's a tunnel that goes from here to here.

And those kind of things.

So the solution to the relaxed problem will usually not be a solution to the actual problem.

But it will give us an estimate of the costs.

If the relaxation was right, and if your domain is such that it admits good relaxations,

you can actually make domains where you cannot meaningfully relax.

The game is always if you throw away too much information, if you relax too much, your estimate will become bad.

And if you don't relax enough, then computing the exact solution will be too costly.

OK.

And by the way, this is essentially what Google tells you.

So we kind of lift this a little bit.

We have a problem class, P, which is in this case, example of route finding.

We have, remember, H star.

H star is always the perfect heuristic, the length of the actual solution.

And if we have that, problem solving is easy.

But we don't.

Well, actually, we can always get it, but it's more expensive than actually solving the problem.

So you shoot yourself into the foot if you do it.

So what you do, you make a simpler problem class here, finding a route in an empty map.

Right.

There we have a perfect solution.

Think about instead of doing this in Europe, you do this in Antarctica or some flam.

Well, in the Arctic, where you have flat ice, where it's very easy, you can just make the perfect solution.

You can just drive from here to here.

OK.

So we have the perfect heuristic, H star P prime, which is something we can in this example actually compute.

And we're going to use H star P prime, which is the perfect heuristic for the relaxed problem.

We're going to use that as a heuristic for the original problem.

OK.

Let's do that in a slightly more interesting problem.