0:00

Hi, these lesson rules tell you the A-star algorithm.

It is another optimization of the Dijkstra's algorithm for

the case when you have a specific source and specific target, and at any point,

we have an estimation of how long does it take to get from this point to the target.

This estimation doesn't have to be exactly precise, but

if it is good enough it can speed up your search a lot.

An example of such estimations is very simple.

If you have the coordinates of your target point, and

you have a phone with GPS controller, and you know the GPS coordinates of your

current point, you can have an estimation based on the distance

by the straight line between those two points and the speed of your car.

So,this is the kind of information we can use to

greatly improve the performance of the Dijkstra's algorithm.

0:52

So, let's first understand the notion of the directed search, and

to accomplish directed search, we will need the notion of potential function.

So, we can take any function mapping vertices to real numbers,

and it will be called a potential function, and then,

the value of this potential function on a vertex is called this vertex' potential.

This potential function defines new edge weights.

If we had edge weight L of u v on the initial graph,

then we can denote by L pi of u v the new edge weight,

which is equal to the old edge weight minus the potential of the starting

vertex, plus the potential of the ending vertex of that edge.

And it turns out that if we replace the old edge weights with these

new edge weights, it doesn't change the shortest paths.

Well, of course it does change the distances between vertices.

What I'm saying is only that the paths themselves,

which were shortest in the initial graph, they're also the shortest

paths between the same pair of vertices in the new graph and vice versa.

The shortest paths in the new graph with new edge weights are also the shortest

path between the same pair of vertices in the initial graph.

2:11

And to prove this, I need this lemma.

For any potential function mapping vertices to the real numbers, for

any two fixed vertices s and t in the graph and

any path P between them, the length of this path in the new graph with

new edge weights is equal to the length of this path in the initial graph minus

the potential of the starting vertex, and plus the potential of the ending vertex.

Why is this important?

Well, because if you fix the starting and ending vertex, then for any path it slacks

in the initial graph, and it slacks in the new graph, differed by a constant.

Because this constant only depends on the starting vertex and

the ending vertex, and we fixed that.

And so, if some path worth the shortest path between s and t,

then it will stay the shortest path between s and t In the new graph,

because all the paths just add a constant to their length.

And so, the paths which were shorter than others, they stay shorter than others.

And the same goes vice versa, if the path was shortest in the new graph,

it was also shown in the initial graph.

And now let's prove this lemma,

we consider some particular path P from s to t, and

we also denote s as v1 and t as Vk and the intermediate vertices V2,

V3 and so on, Vk minus one are the vertices of this path.

Now we consider the length of this path in the new graph, with the new edgeways.

By definition, it is equal to the sum of the length of the edges of this path,

which is l pi(v1,v2) + l pi (v2,v3), and so on.

3:55

And then we can rewrite each l pi from vi to vi plus 1 by definition,

and we know that l pi of v1 to v2 is equal to l of v1 to v2

minus the potential of v1 plus the potential of v2.

So, this first line is equal

to l pi (v1, v2).

4:21

And each of the next lines is similar, it corresponds to

the length of the edge in the new graph with the new edge weight.

So we write each edge on its own line, and

now we can notice that there are somes which cancel out.

For example pi(v2) here, and

pi(v2) here are with different signs, so they cancel out.

And the same will happen with pi(v3) and pi(v3) here and

the same and the same will happen with Pi (Vk-1)- Pi(Vk-1).

So, most of the terms, including this Pi(Vk-2) will cancel out.

The only thing that is left is the sum of the length of the initial

edges minus the first potential of the starting verdicts minus pi(v1) and

plus Plus pi(Vk), the last verdicts.

Those are the only two summons of the form pi of something which don't cancel out.

5:33

And then, we can rewrite this as

the first summoned is the length of this path in the initial graph.

l(P), minus the potential of the starting vertex,

because v1 is the same as s, and

plus the potential of the last vertex, and Vk is the same as t.

So, the length of the path in the new graph

is equal to the length of the path in the initial graph,

minus the potential of starting vertex, plus the potential of the target vertex.

So, we've proved our lemma, so we know that the shortest

path in the initial graph and in the new graph with new edge rates, are the same.

6:16

Although their lengths differ by some constant depending on the starting and

ending vertex of the path.

Now, we can formulate an algorithm which can be called Dijkstra with potentials.

So, we take some potential function pi, and we'll launch the Dijkstra

algorithm with new edge weights l pi instead of the initial edge weight l.

6:40

And the result endurance path is also a shortest path in the initial graph.

So, the result of this algorithm is the same as the result of the initial

Dijkstra algorithm.

But, depending on the result of the potential function pie maybe it will come

from the vertex to the target vertex t faster than with the initial edge weights,

because the order of vertices that this algorithm considers can be different.

7:19

Well, the answer is no, because for

any edge (u,v) the new length l pi(u,v) must be negative,

so that we can apply Dijkstra algorithm for these edge weights.

Such pie, such potential function for which this is true that

all the new edge lines will be non negative, is called feasible.

7:43

Now, the intuition behind the potential functions the following.

Pi(v) is going to be an estimation of the distance from

current the vertex v to the target vertex t, so how far is it from here to t?

If we have such estimation, we can often avoid going to wrong direction,

and that's why we'll get directed search.

And typically in practice,

pi(v) a lower bound on the distance from the current point to the target.

8:12

For example,

on a real map a path from the current point to target cannot be shorter than,

if you manage to go directly on a straight line from the current point to the target.

This is often not possible, because of houses or mountains,

but if this is possible, this is the shortest path possible at all.

And our real path cannot be shorter than the straight line

segment between the current point and the end point.

So A* algorithm is basically this Djikstra with potentials.

What does Djikstra with potentials do?

It goes in iterations, and at each iteration it

picks the vertex v which minimizes the current estimate of distance to v.

8:56

And what will be equal to?

We know that any path in the new graph differs from the same path in

the old graph by minus potential of the starting vertex,

plus potential of the ending vertex.

9:12

So, we are going to pick the minimizing dist of v,

which is the distance estimate if we ran the regular Djikstra algorithm on

the same graph, which is basically, the length of the best known path from

the source vertex to v minus pi(s) plus pi(v).

Now notice that pi of s summoned is the same for all v.

So, vertex v which minimizes this expression

is the same v that minimizes just dist[v] + pi(v).

In the some sense, this is basically the most promising vertex,

because pi of v is an estimate of the distance from v to the target.

And so, we pick vertex v with the minimum current estimate of the distance from

source vertex to v plus the distance from v to the target vertex.

And this is in term, an estimation of the shortest path from s to t going through v.

10:10

So this is why the search is directed.

We always go, not just to the closest vertex to s, which is

still not unprocessed, but we also want it to be close enough to the target.

And this is why while we're searching, we avoid going away directly from the target.

And then, as soon as we find the vertex t as the vertex minimizing

this expression in the Dijkstra's algorithm on this new graph, we stop.

So, of course, this algorithm could still go through the whole graph because before

it gets to the target.

But in practice, if you have a good estimate of the distance left

from the current point of the target, we will get to the target and

extract it much earlier.

And on the way there, we avoid a lot of turns in the wrong direction.