In the previous video, we saw how destroyed the greedy algorithm found the shortcuts down to the goal.
It was dependable, for sure.
But efficiency wise, a lot was left to be desired.
Four smaller cases, for example, over me.
The problem of visiting extra nodes might not be more than a minor nuisance.
But take this thing to a level like Google Maps and you'll understand why we need something far more
intelligent.
An algorithm that has some knowledge of whether we are going down the correct path or not.
One such intelligent algorithm is to.
Is START is the greedy best first search algorithm.
It is simulated disaster, except for the difference lies in the fact that it uses a user defined heuristics
to choose which path to visit next.
So the best first search algorithm stops when the shortest path to the goal node has been found.
Now the crux of a star working lies on its cost function.
Now if you remember, the cost function for desktop was just the distance between the start node and
the current node in estar.
The total cost is computed as the traversal caused added with the heuristic function cost.
Now the heuristic function restricts the information about the goal.
Node is the new thing that makes estar intelligent.
Now let's look at an example.
To better understand the workings of Islam.
We have a very simple graph.
We'll start noticing and notice.
See.
We start by maintaining a table under the right way.
We track two things.
Number one, the shortest distance.
And number two, the closest vertex or the vertex with which it has the shortest distance.
Initially, the least cost to visit for all nodes except cell is set to infinity.
Then for the next step, we relax the starting node by computing the total cost for all the adjacent
nodes.
For the start node.
Now just the nodes for the start node or BCD.
But before going towards that, let's understand what a total cost for a as we said to four instead
of zero.
The reason it is that because even though the devil still goes from eight to a zero, but the heuristic
function goes from eight.
Both for this is because it was the Euclidean distance between the current node and the gold node.
And this is the touristic function cost.
So it is not a total cost is computed as earning the reverse, of course, with the touristic function
cost.
So this is the reason for plus zero gives us the total cost for a two before.
In the same way if we visit B, then its total cost now becomes 12 and not four because even though
the table still calls from it to be was four.
But adding that to the total cost of a four gives eight and then added to the touristic function cost
of B there is another four which gives us 12.
In the same way the rest of the business gets visited and their total cost gets computed as 11 and ten
respectively.
And because of all of these new additions to it and the previous vertex or the close vertex becomes
it, and because he was not adjusting to it, so we left it as it is.
Now in all of this total cost, the unwisely ignored will be silly and the lowest cost to traverse them
was for me.
So it was.
It'd be next.
Now, once it was unwise to do it, then we visit the unlisted Nord with the least of us.
And of course, because we have relaxed now.
So once we relaxed, you will see the total cost for visiting the E will now become the lowest in all
of these countries.
Did not.
Let's see how that is for us.
Five, nine, nine plus 110.
That is for the.
Then we go along, the one that is 11.
So 11 is the cost of visiting it.
So 11 is the minimum in all of these countries.
Did not.
So it is it e next.
Once we relax the.
And then it's unrest over the least of us, of course.
So we find out that e is the the node with the least with the least total cost.
So we visit E next.
And this means because we have visited E, we have reached a good node.
So the shortest part to the goal node was found by just visiting three nodes.
Quite good results as comparison to describe.
Now let's have a look at a few notable characteristics of a star.
Now estar is both complete and optimal.
If the heuristic is admissible now, it will be here means that it never overestimates the cost of reaching
the goal.
His daughter is also intelligent.
This is because it uses some sort of information about the goal in deciding which node to be visiting
next.
Now there are several use cases of AIDS, but the most important are.
Number one spot finding in games will end PCs find it out to their goal.
And number two, for every cent made, solving the admissibility of plastic is ensured, then made solving
will required minimum steps.