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.

Â