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)

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

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)

I think 43:00 is a bit unclear.

Kya bol gaya bhai..upar se chala gaya ab kya hoga mera

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

At 12:28 Shouldn't it be "f*(S) = f*(n1)+f*(n2)+…..+f*(G) "?

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