1
00:00:01,560 --> 00:00:07,140
In the previous video, we saw how destroyed the greedy algorithm found the shortcuts down to the goal.

2
00:00:08,070 --> 00:00:09,600
It was dependable, for sure.

3
00:00:10,470 --> 00:00:13,380
But efficiency wise, a lot was left to be desired.

4
00:00:14,680 --> 00:00:16,990
Four smaller cases, for example, over me.

5
00:00:17,410 --> 00:00:21,490
The problem of visiting extra nodes might not be more than a minor nuisance.

6
00:00:21,820 --> 00:00:28,480
But take this thing to a level like Google Maps and you'll understand why we need something far more

7
00:00:28,480 --> 00:00:29,140
intelligent.

8
00:00:29,530 --> 00:00:34,420
An algorithm that has some knowledge of whether we are going down the correct path or not.

9
00:00:35,350 --> 00:00:38,530
One such intelligent algorithm is to.

10
00:00:40,040 --> 00:00:42,950
Is START is the greedy best first search algorithm.

11
00:00:43,550 --> 00:00:49,820
It is simulated disaster, except for the difference lies in the fact that it uses a user defined heuristics

12
00:00:50,000 --> 00:00:51,920
to choose which path to visit next.

13
00:00:52,430 --> 00:00:59,060
So the best first search algorithm stops when the shortest path to the goal node has been found.

14
00:00:59,900 --> 00:01:03,830
Now the crux of a star working lies on its cost function.

15
00:01:04,960 --> 00:01:11,410
Now if you remember, the cost function for desktop was just the distance between the start node and

16
00:01:11,410 --> 00:01:13,870
the current node in estar.

17
00:01:14,620 --> 00:01:20,440
The total cost is computed as the traversal caused added with the heuristic function cost.

18
00:01:21,370 --> 00:01:24,910
Now the heuristic function restricts the information about the goal.

19
00:01:24,910 --> 00:01:28,090
Node is the new thing that makes estar intelligent.

20
00:01:29,250 --> 00:01:30,750
Now let's look at an example.

21
00:01:30,810 --> 00:01:33,120
To better understand the workings of Islam.

22
00:01:34,500 --> 00:01:35,910
We have a very simple graph.

23
00:01:36,000 --> 00:01:38,160
We'll start noticing and notice.

24
00:01:38,160 --> 00:01:38,570
See.

25
00:01:39,600 --> 00:01:42,440
We start by maintaining a table under the right way.

26
00:01:42,450 --> 00:01:43,530
We track two things.

27
00:01:43,950 --> 00:01:45,660
Number one, the shortest distance.

28
00:01:45,840 --> 00:01:50,310
And number two, the closest vertex or the vertex with which it has the shortest distance.

29
00:01:50,790 --> 00:01:55,800
Initially, the least cost to visit for all nodes except cell is set to infinity.

30
00:01:56,280 --> 00:02:01,710
Then for the next step, we relax the starting node by computing the total cost for all the adjacent

31
00:02:01,710 --> 00:02:02,070
nodes.

32
00:02:02,250 --> 00:02:03,090
For the start node.

33
00:02:03,960 --> 00:02:06,720
Now just the nodes for the start node or BCD.

34
00:02:07,590 --> 00:02:14,340
But before going towards that, let's understand what a total cost for a as we said to four instead

35
00:02:14,340 --> 00:02:14,820
of zero.

36
00:02:15,480 --> 00:02:23,010
The reason it is that because even though the devil still goes from eight to a zero, but the heuristic

37
00:02:23,010 --> 00:02:24,300
function goes from eight.

38
00:02:26,220 --> 00:02:32,700
Both for this is because it was the Euclidean distance between the current node and the gold node.

39
00:02:32,880 --> 00:02:34,630
And this is the touristic function cost.

40
00:02:34,950 --> 00:02:42,030
So it is not a total cost is computed as earning the reverse, of course, with the touristic function

41
00:02:42,030 --> 00:02:42,390
cost.

42
00:02:42,630 --> 00:02:47,550
So this is the reason for plus zero gives us the total cost for a two before.

43
00:02:48,180 --> 00:02:55,200
In the same way if we visit B, then its total cost now becomes 12 and not four because even though

44
00:02:55,240 --> 00:02:57,780
the table still calls from it to be was four.

45
00:02:58,110 --> 00:03:04,140
But adding that to the total cost of a four gives eight and then added to the touristic function cost

46
00:03:04,140 --> 00:03:06,840
of B there is another four which gives us 12.

47
00:03:07,820 --> 00:03:14,150
In the same way the rest of the business gets visited and their total cost gets computed as 11 and ten

48
00:03:14,150 --> 00:03:14,780
respectively.

49
00:03:15,200 --> 00:03:20,930
And because of all of these new additions to it and the previous vertex or the close vertex becomes

50
00:03:20,930 --> 00:03:25,610
it, and because he was not adjusting to it, so we left it as it is.

51
00:03:26,590 --> 00:03:33,190
Now in all of this total cost, the unwisely ignored will be silly and the lowest cost to traverse them

52
00:03:33,190 --> 00:03:34,150
was for me.

53
00:03:34,540 --> 00:03:35,020
So it was.

54
00:03:35,020 --> 00:03:35,680
It'd be next.

55
00:03:39,000 --> 00:03:44,010
Now, once it was unwise to do it, then we visit the unlisted Nord with the least of us.

56
00:03:44,010 --> 00:03:46,440
And of course, because we have relaxed now.

57
00:03:46,710 --> 00:03:52,830
So once we relaxed, you will see the total cost for visiting the E will now become the lowest in all

58
00:03:52,830 --> 00:03:53,480
of these countries.

59
00:03:53,490 --> 00:03:53,910
Did not.

60
00:03:54,240 --> 00:03:55,940
Let's see how that is for us.

61
00:03:55,950 --> 00:03:57,960
Five, nine, nine plus 110.

62
00:03:57,990 --> 00:03:58,710
That is for the.

63
00:03:59,100 --> 00:04:01,890
Then we go along, the one that is 11.

64
00:04:02,190 --> 00:04:04,230
So 11 is the cost of visiting it.

65
00:04:04,450 --> 00:04:06,870
So 11 is the minimum in all of these countries.

66
00:04:06,870 --> 00:04:07,320
Did not.

67
00:04:07,560 --> 00:04:09,090
So it is it e next.

68
00:04:10,340 --> 00:04:11,870
Once we relax the.

69
00:04:11,870 --> 00:04:14,120
And then it's unrest over the least of us, of course.

70
00:04:14,480 --> 00:04:20,240
So we find out that e is the the node with the least with the least total cost.

71
00:04:20,510 --> 00:04:21,620
So we visit E next.

72
00:04:21,920 --> 00:04:26,210
And this means because we have visited E, we have reached a good node.

73
00:04:26,600 --> 00:04:30,740
So the shortest part to the goal node was found by just visiting three nodes.

74
00:04:31,310 --> 00:04:34,880
Quite good results as comparison to describe.

75
00:04:36,540 --> 00:04:40,170
Now let's have a look at a few notable characteristics of a star.

76
00:04:41,220 --> 00:04:44,010
Now estar is both complete and optimal.

77
00:04:44,160 --> 00:04:51,270
If the heuristic is admissible now, it will be here means that it never overestimates the cost of reaching

78
00:04:51,270 --> 00:04:51,720
the goal.

79
00:04:52,860 --> 00:04:54,930
His daughter is also intelligent.

80
00:04:55,290 --> 00:05:00,900
This is because it uses some sort of information about the goal in deciding which node to be visiting

81
00:05:00,900 --> 00:05:01,320
next.

82
00:05:02,900 --> 00:05:06,980
Now there are several use cases of AIDS, but the most important are.

83
00:05:08,010 --> 00:05:13,590
Number one spot finding in games will end PCs find it out to their goal.

84
00:05:15,220 --> 00:05:22,180
And number two, for every cent made, solving the admissibility of plastic is ensured, then made solving

85
00:05:22,180 --> 00:05:23,980
will required minimum steps.