1 00:00:01,100 --> 00:00:01,580 Hi, guys. 2 00:00:02,240 --> 00:00:08,210 Previously we saw how Dice was able to find the shortest path from the given point to the goal. 3 00:00:08,870 --> 00:00:11,330 Surely nothing could get better than that. 4 00:00:11,870 --> 00:00:13,100 Here's where you're wrong. 5 00:00:13,670 --> 00:00:20,060 Dice Star does always find the shortest path, but it does so at the expense of wasting too many unnecessary 6 00:00:20,060 --> 00:00:25,310 nodes, meaning a lot of time and resources are wasted to tackle this problem. 7 00:00:25,550 --> 00:00:31,790 We'll be coding another algorithm that not only finds the shortest path, but it does so in wasting 8 00:00:31,790 --> 00:00:32,410 the least. 9 00:00:32,450 --> 00:00:34,130 No is required here. 10 00:00:34,130 --> 00:00:37,610 I must ask you to try out coding style yourself. 11 00:00:38,300 --> 00:00:39,350 You know, stop. 12 00:00:39,530 --> 00:00:42,830 And you understand where it started before dried out. 13 00:00:43,070 --> 00:00:45,920 And if you still couldn't do it, keep watching. 14 00:00:46,940 --> 00:00:52,010 So here we are at what partly angered by the reprieves to define the disaster algorithm. 15 00:00:52,400 --> 00:00:54,860 And now we'll be developing the instant algorithm. 16 00:00:55,310 --> 00:00:59,180 As I mentioned earlier, estar is just a modification of disaster. 17 00:00:59,840 --> 00:01:06,410 So there are two approaches that we can take because either code is start from scratch or we could simply 18 00:01:06,410 --> 00:01:11,730 import the functionality of the dice to algorithm, modify it a little bit to reach the final estar 19 00:01:11,750 --> 00:01:12,290 algorithm. 20 00:01:12,770 --> 00:01:17,750 The second approach is much better, and it requires a pillar of all known as inheritance. 21 00:01:18,170 --> 00:01:24,170 And the way inheritance works is that we right class is start right. 22 00:01:24,170 --> 00:01:26,120 The brick is inside the record. 23 00:01:26,120 --> 00:01:28,520 We re passing in the object of the dice the class. 24 00:01:31,990 --> 00:01:37,480 So what happens here is that the dice to algorithm functionality gets passed or inherited inside the 25 00:01:37,480 --> 00:01:43,390 instant algorithm, and we can now use a disaster algorithm and modify our algorithm. 26 00:01:43,990 --> 00:01:49,990 So the dice star is basically the parent clause and that is the child clause which inherits the functionality 27 00:01:50,110 --> 00:01:52,480 of a spinning clause that is the dice for algorithm. 28 00:01:53,080 --> 00:01:59,410 So insight inside the class definition of estar we could now earn in the modification that we want for 29 00:01:59,410 --> 00:02:04,930 the estar algorithm, the very first function that we want or the instant algorithm that we want to 30 00:02:04,930 --> 00:02:07,380 modify it would be the initialization function. 31 00:02:07,870 --> 00:02:11,500 So we could use the initialization function provided by the dice to algorithm. 32 00:02:11,680 --> 00:02:17,530 But we wanted to add a new instance variable along with all instance variable provided by its spin class. 33 00:02:17,530 --> 00:02:18,160 That was dice. 34 00:02:18,730 --> 00:02:22,960 And that can be done with a keyboard of super brackets. 35 00:02:23,650 --> 00:02:24,880 And we do it here in it. 36 00:02:26,560 --> 00:02:32,410 So what happens here is that we are simply saying use the same initialization function as provided by 37 00:02:32,410 --> 00:02:33,180 superclass. 38 00:02:33,220 --> 00:02:34,570 That was a spin class. 39 00:02:34,750 --> 00:02:35,540 That is dice drop. 40 00:02:35,860 --> 00:02:41,170 And here we define in the new instance variable that we want to add for this class. 41 00:02:41,560 --> 00:02:48,250 And that would be basically just a counter that is is to know is visited that tells how many nodes have 42 00:02:48,250 --> 00:02:53,520 been visited to find the shortest path to the goal using the estar algorithm, then liberal set into 43 00:02:53,530 --> 00:02:55,720 defining the next function for the class. 44 00:02:55,960 --> 00:03:00,250 And that would be basically the heuristic function that is required for the IS algorithm. 45 00:03:00,820 --> 00:03:07,210 As I mentioned earlier here, the total cost of reaching any goal does not simply equal the cost of 46 00:03:07,210 --> 00:03:09,380 reaching that goal from the start like distro. 47 00:03:09,640 --> 00:03:13,720 Instead, we add in the hubristic cost of that particular node from the end. 48 00:03:14,380 --> 00:03:19,330 So the heuristic function that we define for this class is the Euclidean distance. 49 00:03:19,420 --> 00:03:22,300 So we need to define that function, which will define right here. 50 00:03:22,720 --> 00:03:28,630 So if doing distance is basically just taking two inputs that are two points and it finds including 51 00:03:28,630 --> 00:03:35,800 distance and return that to the it, then we proceed in on defining the third function for our class. 52 00:03:36,130 --> 00:03:41,800 And that would be just the same function that we define for our distance algorithm, that is. 53 00:03:42,730 --> 00:03:43,740 Fine by stealth. 54 00:03:44,500 --> 00:03:49,990 Now, the reason we are defining this function inside is the algorithm that is already defined inside 55 00:03:50,180 --> 00:03:54,910 the algorithm, because we want to adding a new modification for the instant algorithm. 56 00:03:55,390 --> 00:03:58,480 And because we want to add a new functionality inside this function. 57 00:03:59,020 --> 00:04:02,650 So we could not just use that function and add a new functionality. 58 00:04:03,220 --> 00:04:05,140 We want to modify it from within. 59 00:04:05,410 --> 00:04:08,110 So we need to redefine that function by copying it over. 60 00:04:08,440 --> 00:04:13,000 And we simply what we do is, is known as function overwriting. 61 00:04:13,690 --> 00:04:19,930 So when we modify this function, what would happen is when we call this function from the same class 62 00:04:20,080 --> 00:04:20,650 is done. 63 00:04:20,890 --> 00:04:25,990 What would happen is that this particular function that is defined inside the instant algorithm will 64 00:04:25,990 --> 00:04:30,670 override the function or functionality provided by the class of distro. 65 00:04:30,910 --> 00:04:36,460 So this function would get called when the star calls this function of fine vessels instead of a spin 66 00:04:36,460 --> 00:04:38,000 class function or find the stop. 67 00:04:38,650 --> 00:04:42,190 So we can now add in the new functionality that we required for the instant algorithm. 68 00:04:42,820 --> 00:04:48,040 So right here we were defining the tools that were necessary for the ISDA or master algorithm. 69 00:04:48,340 --> 00:04:52,180 That was the distance and finishes instead of the distance list. 70 00:04:52,210 --> 00:04:56,320 We now add a new list that is basically the cost to nought. 71 00:04:57,820 --> 00:05:04,360 Now the cost to note is basically the list that restore the cost of reaching any node from start in 72 00:05:04,360 --> 00:05:05,410 the dice to algorithm. 73 00:05:05,860 --> 00:05:11,380 This was known as the total cost of reaching that note, as that was the cause of reaching that note 74 00:05:11,380 --> 00:05:12,070 from START. 75 00:05:12,490 --> 00:05:18,010 But for the ISDA algorithm, this cost to note is just a component of the total cost of reaching that 76 00:05:18,010 --> 00:05:18,280 note. 77 00:05:18,580 --> 00:05:23,110 So we need to define separate list for the instant algorithm that we named as cause to note. 78 00:05:23,620 --> 00:05:26,500 And the total cost would still be named as the distance. 79 00:05:26,500 --> 00:05:28,180 And this witness ties to an empty list. 80 00:05:28,750 --> 00:05:34,780 Then we proceed on to where we are initializing or adding an infinity to our distance list. 81 00:05:35,320 --> 00:05:36,190 So this does list. 82 00:05:36,190 --> 00:05:38,620 Here is the total cost for that particular node. 83 00:05:38,770 --> 00:05:43,450 And this is initialized to infinity because we don't know the total cost of any node at the start. 84 00:05:43,870 --> 00:05:46,990 And the same would be done for the new list that we have just added. 85 00:05:47,440 --> 00:05:48,730 That is cost to note. 86 00:05:48,880 --> 00:05:56,020 So we append here one is seven, which is basically just infinity that we don't know the cost of reaching 87 00:05:56,020 --> 00:05:58,930 that note from the start for any node at this moment. 88 00:05:59,740 --> 00:06:06,010 So we added or appended infinity for the cost to note and the total cost. 89 00:06:06,580 --> 00:06:13,360 Then we proceed on to where we were simply decreasing the cost of our start node from infinity to zero. 90 00:06:13,480 --> 00:06:14,680 And that was the total cost. 91 00:06:15,220 --> 00:06:18,760 But for the ISDA algorithm, we have two components for the total cost. 92 00:06:19,000 --> 00:06:21,130 So we need to first define that particular component. 93 00:06:21,490 --> 00:06:27,940 So the thing that we define as zero for the ISDA algorithm will not be the total cost, but rather the 94 00:06:27,940 --> 00:06:29,280 cost of reaching that node. 95 00:06:29,290 --> 00:06:35,590 And that is known as cost to not so cost to reaching the start node from the start is basically now 96 00:06:35,590 --> 00:06:36,640 equals to zero. 97 00:06:36,880 --> 00:06:39,460 So this has been decreased from infinity to zero. 98 00:06:39,940 --> 00:06:44,890 Then we now proceed on to define the total cost of reaching the start node because we haven't defined 99 00:06:44,890 --> 00:06:45,580 it as of yet. 100 00:06:45,670 --> 00:06:52,930 So we draw a distance of reaching the start start node and that would be adding in the cost to node 101 00:06:53,200 --> 00:06:59,500 or cost of reaching the start node from the start and in the heuristic cost of that particular node 102 00:06:59,530 --> 00:07:00,100 with the end. 103 00:07:00,460 --> 00:07:03,550 So that is defined by using the function that we just defined. 104 00:07:03,550 --> 00:07:09,760 You gain distance, we pass in the start as the vertex and the end of the vertex. 105 00:07:09,760 --> 00:07:15,370 We want to find the function or the distance or Euclidean distance between the start node and node. 106 00:07:15,550 --> 00:07:19,690 And this is the basically the hubristic function that gets added to the cost of reaching that particular 107 00:07:19,690 --> 00:07:22,960 node from the start to get the total cost of the start not. 108 00:07:23,880 --> 00:07:29,070 And if you see here, the start node is the vortex or the actual vortex that is being passed instead 109 00:07:29,070 --> 00:07:31,650 of the index that was being passed for the cross to note. 110 00:07:32,010 --> 00:07:37,440 And the reason is that you can distance simply find the distance between two points, and that is the 111 00:07:37,440 --> 00:07:40,560 tuples provided by the verses of that particular note. 112 00:07:40,890 --> 00:07:46,470 And this is why we are not passing in the index that is an integer, but rather the actual vertex of 113 00:07:46,470 --> 00:07:46,950 the tuple. 114 00:07:48,010 --> 00:07:50,320 Then we proceed on to simply decrease the key. 115 00:07:50,350 --> 00:07:51,130 That was a start. 116 00:07:51,370 --> 00:07:57,460 What happens here is that a start node goes right to the top and it is ready to getting up from our 117 00:07:57,460 --> 00:07:58,150 priority queue. 118 00:07:58,510 --> 00:08:04,300 So when we enter our value, where we are starting to check if the buy loop is empty or not and if it 119 00:08:04,300 --> 00:08:11,260 is not empty, we first first do is simply modify this node of that is a counter that checking how many 120 00:08:11,260 --> 00:08:13,420 rows every visited for that particular algorithm. 121 00:08:13,630 --> 00:08:18,820 And because this is the algorithm, you modify this to the start and was visited. 122 00:08:19,060 --> 00:08:21,970 So this gets increased every time this by loop runs. 123 00:08:22,690 --> 00:08:28,690 Then it will sit on and it will see it on to where we we are twisting the neighbor nodes for our current 124 00:08:28,690 --> 00:08:28,990 node. 125 00:08:29,320 --> 00:08:34,210 And we simply before visiting the neighbor node for our current or you are performing the extract when 126 00:08:34,480 --> 00:08:37,540 it is basically extracting the top nor for our priority queue. 127 00:08:37,750 --> 00:08:42,850 And at the start the top node would be just a stock node because it is just distance. 128 00:08:42,850 --> 00:08:48,940 Estoril cost is basically just equal to zero and with a Euclidean distance, so basically always less 129 00:08:48,940 --> 00:08:49,630 than infinity. 130 00:08:49,840 --> 00:08:54,250 So the first thing that gets popped in for the extraction function will be the start note. 131 00:08:54,730 --> 00:09:00,460 Once we expect that start node, what happens is that we visit the neighbor node for our start node 132 00:09:00,610 --> 00:09:01,720 and visiting the neighbor node. 133 00:09:01,720 --> 00:09:02,500 For our start node. 134 00:09:02,740 --> 00:09:04,150 We perform a few checks. 135 00:09:04,810 --> 00:09:06,970 And what the check here is that? 136 00:09:08,060 --> 00:09:12,060 If that is not the case, then we proceed further and proceeding further. 137 00:09:12,080 --> 00:09:17,860 We check if that particular neighbour or form a starting or a current node is part of the mean heap. 138 00:09:18,140 --> 00:09:22,220 So we maintain this check what our algorithm as it is. 139 00:09:22,640 --> 00:09:28,910 And the same thing that we do is checking whether the distance of our current node is not equal to infinity, 140 00:09:29,150 --> 00:09:34,070 because that is a strong if it is equal to infinity, because adding anything to infinity to just give 141 00:09:34,070 --> 00:09:39,770 us back infinity, the second or a third thing that we would be checking here, that if we have found 142 00:09:39,770 --> 00:09:45,560 a shorter row that reaches the neighbor node, then the previously known shout out to the to the, to 143 00:09:45,560 --> 00:09:46,160 the neighbor node. 144 00:09:46,280 --> 00:09:51,640 Then we have, then we need to update the distance or the total cost of reaching that neighbor note. 145 00:09:52,190 --> 00:09:58,080 So the way this works is in the district algorithm, we would simply taking the total cost of the, 146 00:09:58,330 --> 00:10:04,910 of the, of the current node and adding in that there was some cost of the neighbor node with the current 147 00:10:04,910 --> 00:10:05,180 node. 148 00:10:05,660 --> 00:10:10,880 And if it is less than the cost of raising the neighbor node, then we have found a shorter out than 149 00:10:10,880 --> 00:10:11,360 they were not. 150 00:10:11,690 --> 00:10:17,990 So we update that the neighbor not current cost but here what we track here is that we simply track 151 00:10:17,990 --> 00:10:19,100 instead of the total cost. 152 00:10:19,130 --> 00:10:21,620 We track here the cost of reaching that node from the start. 153 00:10:21,950 --> 00:10:24,860 So we modify this from the current cost to cost to node. 154 00:10:26,170 --> 00:10:34,030 For coastal road for the for the drive north and if Gorleston or of course submitting the grant note 155 00:10:34,180 --> 00:10:37,930 on the start added with a proposal cost of reaching the neighbour note from the start. 156 00:10:38,140 --> 00:10:42,540 If it is less than the cost of reaching that neighbourhood node from the start, then we have found 157 00:10:42,640 --> 00:10:43,360 a shorter go. 158 00:10:43,540 --> 00:10:47,200 So we need to update the cost of reaching that node from the start. 159 00:10:47,530 --> 00:10:52,840 So instead of the distance we update the cost of reaching that node or neighbour node from the start. 160 00:10:53,410 --> 00:10:59,820 And this the way this works is updating works is that we are adding the troublesome cost of visiting 161 00:10:59,830 --> 00:11:06,040 the neighbour node, our start node with the cost of reaching the the current node from the start. 162 00:11:06,760 --> 00:11:13,090 So because we have updated the cost to new, we also need to add or modify the total cost of reaching 163 00:11:13,090 --> 00:11:18,160 that or neighbour node because cost to node is just a component of the total cost of reaching their 164 00:11:18,160 --> 00:11:18,450 total. 165 00:11:18,820 --> 00:11:25,630 So we need to also modify the total cost by writing distance and passing the neighbour index. 166 00:11:26,230 --> 00:11:31,090 And what happens is we add in the cost of reaching that particular node or the neighbour node from the 167 00:11:31,090 --> 00:11:39,580 start with the standard Euclidean distance and this takes in the two nodes that was the first node is 168 00:11:39,580 --> 00:11:44,680 basically the way the neighbour node and the distance between the neighbour node and the end. 169 00:11:45,400 --> 00:11:51,340 So basically the total cost of the neighbour node is now getting modified with the cost of reaching 170 00:11:51,340 --> 00:11:56,950 the neighbour node from the start with adding to the Euclidean distance of the neighbor node the end. 171 00:11:57,430 --> 00:11:59,740 So this is how we modify the estar algorithm. 172 00:11:59,920 --> 00:12:01,360 Then we simply decrease the key. 173 00:12:01,720 --> 00:12:07,900 This node goes right to the top where in the next iteration its guess fork until this algorithm or this 174 00:12:07,900 --> 00:12:14,050 function or this loop stops when we have visited our goal node, when our neighbor node on our current 175 00:12:14,050 --> 00:12:18,730 node is the goal node, then we have visited the goal node and we have found this chart to start with 176 00:12:18,730 --> 00:12:19,060 the goals. 177 00:12:19,060 --> 00:12:25,720 Note So this is where the estar algorithm modification to the data algorithm completes and we have developed 178 00:12:25,930 --> 00:12:27,190 our estar algorithm. 179 00:12:27,760 --> 00:12:34,090 So what we need to do, we go right to the top where we were defining the path planner and here we add 180 00:12:34,090 --> 00:12:40,340 in the new functionality or the new method that we can now access from inside the board authenticate. 181 00:12:40,570 --> 00:12:47,800 And that is that the same as the distro we simply add in as if method of estar and the same way that 182 00:12:47,800 --> 00:12:49,370 we were calling the saved or die star. 183 00:12:49,600 --> 00:12:55,090 When we added the the object for the to algorithm, we are adding the object of the estar algorithm. 184 00:12:55,360 --> 00:13:01,420 And then we simply say that if the surfboard estar showed up us, but the phone is not. 185 00:13:01,630 --> 00:13:06,520 So if the shortest path is not found is in the estar algorithm, then find the shortest path by using 186 00:13:06,520 --> 00:13:08,590 the instead functionality of find results. 187 00:13:08,980 --> 00:13:15,520 Now notice here the Find Bustos is not the find Bustos that was provided by the dice to algorithm because 188 00:13:15,820 --> 00:13:18,610 we have ordered in this function inside that is class. 189 00:13:18,970 --> 00:13:22,350 So this takes in the same arguments that was taken by the Dijkstra algorithm. 190 00:13:22,360 --> 00:13:28,090 Find out that this graph started then and it finds the best out of this that is sure to spot. 191 00:13:28,480 --> 00:13:33,970 And if you notice the shortest path variable and the shortest path found variable but not defined inside 192 00:13:33,970 --> 00:13:37,720 the estar class, but they were inherited from a spin class of Dijkstra. 193 00:13:37,990 --> 00:13:42,070 So still the algorithm has these function at its disposal. 194 00:13:42,370 --> 00:13:48,280 The short spot when found after computing defined results, the shortest path gets updated. 195 00:13:48,640 --> 00:13:51,910 We add that to the path to display, and then we display that we use it. 196 00:13:52,330 --> 00:13:56,260 So the instant algorithm development has been completed. 197 00:13:56,710 --> 00:14:02,830 Now all that is left for us to do is to simply run this project by integrate it inside the main solver 198 00:14:03,070 --> 00:14:10,780 and see if we have done a better job encoding the algorithm to perform the analysis of the estar algorithm 199 00:14:10,990 --> 00:14:13,390 we head on over the maze Salvador part. 200 00:14:13,840 --> 00:14:18,880 We will scroll down where we have called the fine path and display function that was part of the board 201 00:14:19,180 --> 00:14:24,130 part plan, a class where we have used the dice to algorithm to find the shortcuts for the goal. 202 00:14:24,700 --> 00:14:31,420 We copy all the slime head on over to the next line, based this and modify the method from destruct 203 00:14:31,630 --> 00:14:32,440 to stop. 204 00:14:33,040 --> 00:14:36,580 So what we are doing here is that we first find the shortest path to the goal. 205 00:14:36,610 --> 00:14:41,440 Using the dice to algorithm and then use is the algorithm to find the shortest path for the goal. 206 00:14:41,980 --> 00:14:47,890 Then we perform the comparison between both algorithms by printing out the amount of both nodes visited 207 00:14:48,460 --> 00:14:49,690 by either algorithms. 208 00:14:50,080 --> 00:14:53,390 Then we save this over head on over to Terminal Reader. 209 00:14:53,530 --> 00:14:55,240 I have already started a simulation. 210 00:14:55,840 --> 00:14:56,620 Build the project. 211 00:14:58,160 --> 00:15:00,200 And run them in solar. 212 00:15:02,640 --> 00:15:08,490 We get the output of localizing stage dressing space for you, get the map and stage output pressing 213 00:15:08,490 --> 00:15:09,240 spacebar again. 214 00:15:09,510 --> 00:15:13,740 We found the shortest path using dice to algorithm and pressing spacebar again. 215 00:15:14,290 --> 00:15:16,260 Oops, we have landed on an error. 216 00:15:17,040 --> 00:15:20,250 The error is the name square function is not defined. 217 00:15:21,060 --> 00:15:21,860 Now square. 218 00:15:21,930 --> 00:15:27,210 It was defining the Euclidean distance and the square is basically the function provided with an umpire 219 00:15:27,210 --> 00:15:27,780 library. 220 00:15:28,230 --> 00:15:33,450 So we basically have not performed the import of this function inside the more popular class. 221 00:15:33,990 --> 00:15:36,210 So we head on over to the board, passing our part. 222 00:15:38,150 --> 00:15:42,470 Reformed import from the number of starting from number import. 223 00:15:43,640 --> 00:15:44,870 Square root function. 224 00:15:45,840 --> 00:15:49,620 Once we performed this import, we now head back over to the terminal. 225 00:15:50,560 --> 00:15:54,020 Build the project again and run the missile. 226 00:15:56,240 --> 00:15:58,700 And hopefully this time the error goes away. 227 00:16:00,160 --> 00:16:01,900 We get the output of the local and state. 228 00:16:02,380 --> 00:16:04,750 We get the output of the mapping state wrestling space. 229 00:16:04,750 --> 00:16:08,950 But again, we get the output of the algorithm finding the shortest path to the goal. 230 00:16:09,640 --> 00:16:12,940 And then we have the shortest part of the goal using is the algorithm. 231 00:16:13,840 --> 00:16:19,630 And as you can see, this sort of smartphone with instant algorithm is exactly the same that was found 232 00:16:19,630 --> 00:16:20,770 by the dinosaur algorithm. 233 00:16:21,190 --> 00:16:27,160 Now the difference lies in the fact when you press the spacebar again, you see a new line that has 234 00:16:27,160 --> 00:16:28,330 been printed, the terminal. 235 00:16:28,810 --> 00:16:33,760 This line sees that the amount of noise visited by either algorithms are different. 236 00:16:34,480 --> 00:16:40,450 So I still used or visited one 6 to 3 nodes to find the shortest route out of the goal. 237 00:16:41,030 --> 00:16:47,470 Whereas is the algorithm only required 118 nodes to visit to find the shortest route out of the goal. 238 00:16:47,980 --> 00:16:52,240 So a digital algorithm and the algorithm would find the shortest out. 239 00:16:52,510 --> 00:16:57,580 But the instant algorithm found the shortest zone by boosting the least amount of notes. 240 00:16:58,210 --> 00:17:04,120 So basically the shortest all from the miss entry to the mistake taxi was found by visiting list nodes 241 00:17:04,330 --> 00:17:08,260 using the estar algorithm very provided the appropriate listings. 242 00:17:08,830 --> 00:17:12,040 So this is why Star does always find the shortest path. 243 00:17:12,340 --> 00:17:16,270 What is done does the same job in a much less time. 244 00:17:16,900 --> 00:17:21,480 So it takes less resources, takes less time to find the same chance. 245 00:17:21,490 --> 00:17:24,130 But so is time if appropriate. 246 00:17:24,220 --> 00:17:32,530 This is provided does find the shortest path in minimum possible time and visiting minimum or at least 247 00:17:32,530 --> 00:17:33,340 among nodes. 248 00:17:33,940 --> 00:17:39,790 So this one is die is preferable if the die is question that you don't want to lose. 249 00:17:40,540 --> 00:17:43,030 So you later do that. 250 00:17:43,540 --> 00:17:43,930 But.