A* Algorithm

To access the translated content:
The video course content can be accessed in the form of regional language text transcripts, books which can be accessed under downloads of each course, subtitles in the video and Video Text Track below the video.
2. Regional language subtitles available for this course
To watch the subtitles in regional languages:
1. Click on the lecture under Course Details.
2. Play the video.
3. Now click on the Settings icon and a list of features will display
4. From that select the option Subtitles/CC.
5. Now select the Language from the available languages to read the subtitle in the regional language.

[radhakrishnanaishwarya]

Prof. Khemani, your teaching is truly crisp & made it easier to understand the subject.

[malharjajoo]

Regarding admissibility of A*, it is imp to understand why underestimating the actual value works -

Consider the example in the video at 25:00.
Try and use a simple number line to visualize the explanation below.

1) firstly, the underestimate can be different for different nodes ( ie, h(n) is not underestimated by a fixed decrementing amount for all nodes )

2) Hence, we might try to find a counter example by underestimating h(n) for the Wrong node ( "B" in the example ) by a large value.
Hence we will choose this as optimal node ( the node will be part of our answer )
and we will obtain estimate - f(n)

3) But once we reach the goal, it is time to remove the assumption and check the actual value of f(n)

4) the fact that you had underestimated h(n) earlier will now lead to an increase in the value of f(n) .

5) What this actually does is - It now allows us to "CONSIDER" the other path ( which involves node "A" ) since f(n) ( estimated along )along A will be lesser than our actual f(n) along B.

NOTE -

The key idea here is understanding what happens to f(n) when we reach the goal along some path, is

i) actual f(n) > estimated f(n) - This is good since it allows step 5)
ii) actual f(n) < estimated f(n) - This is bad since it might not allow step 5)

[a.s.]

So far the best lecture on A* algorithm. Even better than MIT lecture on A*

[kunwarprashant]

captions are not auto-generated and the person who typed it is using more 'essentially' than prof actually used

[studentcommenter]

At 12:28 Shouldn't it be "f*(S) = "?

[CrazyHeartWizard]

10:23 Lol forever single. (don't take it seriously :P)