Hi, guys.
Previously we saw how Dice was able to find the shortest path from the given point to the goal.
Surely nothing could get better than that.
Here's where you're wrong.
Dice Star does always find the shortest path, but it does so at the expense of wasting too many unnecessary
nodes, meaning a lot of time and resources are wasted to tackle this problem.
We'll be coding another algorithm that not only finds the shortest path, but it does so in wasting
the least.
No is required here.
I must ask you to try out coding style yourself.
You know, stop.
And you understand where it started before dried out.
And if you still couldn't do it, keep watching.
So here we are at what partly angered by the reprieves to define the disaster algorithm.
And now we'll be developing the instant algorithm.
As I mentioned earlier, estar is just a modification of disaster.
So there are two approaches that we can take because either code is start from scratch or we could simply
import the functionality of the dice to algorithm, modify it a little bit to reach the final estar
algorithm.
The second approach is much better, and it requires a pillar of all known as inheritance.
And the way inheritance works is that we right class is start right.
The brick is inside the record.
We re passing in the object of the dice the class.
So what happens here is that the dice to algorithm functionality gets passed or inherited inside the
instant algorithm, and we can now use a disaster algorithm and modify our algorithm.
So the dice star is basically the parent clause and that is the child clause which inherits the functionality
of a spinning clause that is the dice for algorithm.
So insight inside the class definition of estar we could now earn in the modification that we want for
the estar algorithm, the very first function that we want or the instant algorithm that we want to
modify it would be the initialization function.
So we could use the initialization function provided by the dice to algorithm.
But we wanted to add a new instance variable along with all instance variable provided by its spin class.
That was dice.
And that can be done with a keyboard of super brackets.
And we do it here in it.
So what happens here is that we are simply saying use the same initialization function as provided by
superclass.
That was a spin class.
That is dice drop.
And here we define in the new instance variable that we want to add for this class.
And that would be basically just a counter that is is to know is visited that tells how many nodes have
been visited to find the shortest path to the goal using the estar algorithm, then liberal set into
defining the next function for the class.
And that would be basically the heuristic function that is required for the IS algorithm.
As I mentioned earlier here, the total cost of reaching any goal does not simply equal the cost of
reaching that goal from the start like distro.
Instead, we add in the hubristic cost of that particular node from the end.
So the heuristic function that we define for this class is the Euclidean distance.
So we need to define that function, which will define right here.
So if doing distance is basically just taking two inputs that are two points and it finds including
distance and return that to the it, then we proceed in on defining the third function for our class.
And that would be just the same function that we define for our distance algorithm, that is.
Fine by stealth.
Now, the reason we are defining this function inside is the algorithm that is already defined inside
the algorithm, because we want to adding a new modification for the instant algorithm.
And because we want to add a new functionality inside this function.
So we could not just use that function and add a new functionality.
We want to modify it from within.
So we need to redefine that function by copying it over.
And we simply what we do is, is known as function overwriting.
So when we modify this function, what would happen is when we call this function from the same class
is done.
What would happen is that this particular function that is defined inside the instant algorithm will
override the function or functionality provided by the class of distro.
So this function would get called when the star calls this function of fine vessels instead of a spin
class function or find the stop.
So we can now add in the new functionality that we required for the instant algorithm.
So right here we were defining the tools that were necessary for the ISDA or master algorithm.
That was the distance and finishes instead of the distance list.
We now add a new list that is basically the cost to nought.
Now the cost to note is basically the list that restore the cost of reaching any node from start in
the dice to algorithm.
This was known as the total cost of reaching that note, as that was the cause of reaching that note
from START.
But for the ISDA algorithm, this cost to note is just a component of the total cost of reaching that
note.
So we need to define separate list for the instant algorithm that we named as cause to note.
And the total cost would still be named as the distance.
And this witness ties to an empty list.
Then we proceed on to where we are initializing or adding an infinity to our distance list.
So this does list.
Here is the total cost for that particular node.
And this is initialized to infinity because we don't know the total cost of any node at the start.
And the same would be done for the new list that we have just added.
That is cost to note.
So we append here one is seven, which is basically just infinity that we don't know the cost of reaching
that note from the start for any node at this moment.
So we added or appended infinity for the cost to note and the total cost.
Then we proceed on to where we were simply decreasing the cost of our start node from infinity to zero.
And that was the total cost.
But for the ISDA algorithm, we have two components for the total cost.
So we need to first define that particular component.
So the thing that we define as zero for the ISDA algorithm will not be the total cost, but rather the
cost of reaching that node.
And that is known as cost to not so cost to reaching the start node from the start is basically now
equals to zero.
So this has been decreased from infinity to zero.
Then we now proceed on to define the total cost of reaching the start node because we haven't defined
it as of yet.
So we draw a distance of reaching the start start node and that would be adding in the cost to node
or cost of reaching the start node from the start and in the heuristic cost of that particular node
with the end.
So that is defined by using the function that we just defined.
You gain distance, we pass in the start as the vertex and the end of the vertex.
We want to find the function or the distance or Euclidean distance between the start node and node.
And this is the basically the hubristic function that gets added to the cost of reaching that particular
node from the start to get the total cost of the start not.
And if you see here, the start node is the vortex or the actual vortex that is being passed instead
of the index that was being passed for the cross to note.
And the reason is that you can distance simply find the distance between two points, and that is the
tuples provided by the verses of that particular note.
And this is why we are not passing in the index that is an integer, but rather the actual vertex of
the tuple.
Then we proceed on to simply decrease the key.
That was a start.
What happens here is that a start node goes right to the top and it is ready to getting up from our
priority queue.
So when we enter our value, where we are starting to check if the buy loop is empty or not and if it
is not empty, we first first do is simply modify this node of that is a counter that checking how many
rows every visited for that particular algorithm.
And because this is the algorithm, you modify this to the start and was visited.
So this gets increased every time this by loop runs.
Then it will sit on and it will see it on to where we we are twisting the neighbor nodes for our current
node.
And we simply before visiting the neighbor node for our current or you are performing the extract when
it is basically extracting the top nor for our priority queue.
And at the start the top node would be just a stock node because it is just distance.
Estoril cost is basically just equal to zero and with a Euclidean distance, so basically always less
than infinity.
So the first thing that gets popped in for the extraction function will be the start note.
Once we expect that start node, what happens is that we visit the neighbor node for our start node
and visiting the neighbor node.
For our start node.
We perform a few checks.
And what the check here is that?
If that is not the case, then we proceed further and proceeding further.
We check if that particular neighbour or form a starting or a current node is part of the mean heap.
So we maintain this check what our algorithm as it is.
And the same thing that we do is checking whether the distance of our current node is not equal to infinity,
because that is a strong if it is equal to infinity, because adding anything to infinity to just give
us back infinity, the second or a third thing that we would be checking here, that if we have found
a shorter row that reaches the neighbor node, then the previously known shout out to the to the, to
the neighbor node.
Then we have, then we need to update the distance or the total cost of reaching that neighbor note.
So the way this works is in the district algorithm, we would simply taking the total cost of the,
of the, of the current node and adding in that there was some cost of the neighbor node with the current
node.
And if it is less than the cost of raising the neighbor node, then we have found a shorter out than
they were not.
So we update that the neighbor not current cost but here what we track here is that we simply track
instead of the total cost.
We track here the cost of reaching that node from the start.
So we modify this from the current cost to cost to node.
For coastal road for the for the drive north and if Gorleston or of course submitting the grant note
on the start added with a proposal cost of reaching the neighbour note from the start.
If it is less than the cost of reaching that neighbourhood node from the start, then we have found
a shorter go.
So we need to update the cost of reaching that node from the start.
So instead of the distance we update the cost of reaching that node or neighbour node from the start.
And this the way this works is updating works is that we are adding the troublesome cost of visiting
the neighbour node, our start node with the cost of reaching the the current node from the start.
So because we have updated the cost to new, we also need to add or modify the total cost of reaching
that or neighbour node because cost to node is just a component of the total cost of reaching their
total.
So we need to also modify the total cost by writing distance and passing the neighbour index.
And what happens is we add in the cost of reaching that particular node or the neighbour node from the
start with the standard Euclidean distance and this takes in the two nodes that was the first node is
basically the way the neighbour node and the distance between the neighbour node and the end.
So basically the total cost of the neighbour node is now getting modified with the cost of reaching
the neighbour node from the start with adding to the Euclidean distance of the neighbor node the end.
So this is how we modify the estar algorithm.
Then we simply decrease the key.
This node goes right to the top where in the next iteration its guess fork until this algorithm or this
function or this loop stops when we have visited our goal node, when our neighbor node on our current
node is the goal node, then we have visited the goal node and we have found this chart to start with
the goals.
Note So this is where the estar algorithm modification to the data algorithm completes and we have developed
our estar algorithm.
So what we need to do, we go right to the top where we were defining the path planner and here we add
in the new functionality or the new method that we can now access from inside the board authenticate.
And that is that the same as the distro we simply add in as if method of estar and the same way that
we were calling the saved or die star.
When we added the the object for the to algorithm, we are adding the object of the estar algorithm.
And then we simply say that if the surfboard estar showed up us, but the phone is not.
So if the shortest path is not found is in the estar algorithm, then find the shortest path by using
the instead functionality of find results.
Now notice here the Find Bustos is not the find Bustos that was provided by the dice to algorithm because
we have ordered in this function inside that is class.
So this takes in the same arguments that was taken by the Dijkstra algorithm.
Find out that this graph started then and it finds the best out of this that is sure to spot.
And if you notice the shortest path variable and the shortest path found variable but not defined inside
the estar class, but they were inherited from a spin class of Dijkstra.
So still the algorithm has these function at its disposal.
The short spot when found after computing defined results, the shortest path gets updated.
We add that to the path to display, and then we display that we use it.
So the instant algorithm development has been completed.
Now all that is left for us to do is to simply run this project by integrate it inside the main solver
and see if we have done a better job encoding the algorithm to perform the analysis of the estar algorithm
we head on over the maze Salvador part.
We will scroll down where we have called the fine path and display function that was part of the board
part plan, a class where we have used the dice to algorithm to find the shortcuts for the goal.
We copy all the slime head on over to the next line, based this and modify the method from destruct
to stop.
So what we are doing here is that we first find the shortest path to the goal.
Using the dice to algorithm and then use is the algorithm to find the shortest path for the goal.
Then we perform the comparison between both algorithms by printing out the amount of both nodes visited
by either algorithms.
Then we save this over head on over to Terminal Reader.
I have already started a simulation.
Build the project.
And run them in solar.
We get the output of localizing stage dressing space for you, get the map and stage output pressing
spacebar again.
We found the shortest path using dice to algorithm and pressing spacebar again.
Oops, we have landed on an error.
The error is the name square function is not defined.
Now square.
It was defining the Euclidean distance and the square is basically the function provided with an umpire
library.
So we basically have not performed the import of this function inside the more popular class.
So we head on over to the board, passing our part.
Reformed import from the number of starting from number import.
Square root function.
Once we performed this import, we now head back over to the terminal.
Build the project again and run the missile.
And hopefully this time the error goes away.
We get the output of the local and state.
We get the output of the mapping state wrestling space.
But again, we get the output of the algorithm finding the shortest path to the goal.
And then we have the shortest part of the goal using is the algorithm.
And as you can see, this sort of smartphone with instant algorithm is exactly the same that was found
by the dinosaur algorithm.
Now the difference lies in the fact when you press the spacebar again, you see a new line that has
been printed, the terminal.
This line sees that the amount of noise visited by either algorithms are different.
So I still used or visited one 6 to 3 nodes to find the shortest route out of the goal.
Whereas is the algorithm only required 118 nodes to visit to find the shortest route out of the goal.
So a digital algorithm and the algorithm would find the shortest out.
But the instant algorithm found the shortest zone by boosting the least amount of notes.
So basically the shortest all from the miss entry to the mistake taxi was found by visiting list nodes
using the estar algorithm very provided the appropriate listings.
So this is why Star does always find the shortest path.
What is done does the same job in a much less time.
So it takes less resources, takes less time to find the same chance.
But so is time if appropriate.
This is provided does find the shortest path in minimum possible time and visiting minimum or at least
among nodes.
So this one is die is preferable if the die is question that you don't want to lose.
So you later do that.
But.