[0:00]Hello friends, welcome to Gate Mash. Aaj ki is video mein hum discuss karne ja rahe hain A star algorithm.
[0:08]Artificial intelligence ke agar hum syllabus ki baat kare to heuristic search mein ya informed search technique mein sabse important algorithm hai ye hamare paas A star algorithm. To jaisa ki maine sabse pehla important point yahan pe bataya ki A star algorithm kya hai? Informed searching technique ka part hai. Informed searching technique ka matlab hai jahan pe mujhe problem ke bare mein already kuch knowledge hai matlab mere ko problem statements ke bare mein domain ke bare mein already kuch knowledge hai aur us knowledge ko hum bolte hain heuristic. Jisme hum kahi na kahi goal state ko apne mind mein leke chalte hain aur iske opposite kya hoti hai uninformed ya blind search jaisa ki humne DFS aur BFS breadth first search, depth first search mein discuss kiya tha jisme hum goal state ko mind mein leke nahi chalte, hum simply traverse karte hain. Ya to hum breadth ki taraf traverse karte hain ya phir depth ki taraf traverse karte hain without knowing anything. Hum sirf current state ke bare mein jante hain. Woh current state hume kahan leke ja raha hai, kitni estimation hai, kya heuristic hai, iske bare mein koi knowledge nahi hai. To heuristic jo search technique hai ya informed search technique hai, usme jo pehli search technique hum discuss karne ja rahe hain, that is A star algorithm. Second point main yahan pe batana chahta hu A star algorithm mein ye equation hum use karte hain f(n) = g(n) + h(n). Aur sahi batau to A star algorithm sara ka sara A star ki jo kahani hai woh is equation ke around hi revolve karti hai. Matlab kehne ka ki agar aapko ye equation clear hai, ye pata lag gaya to aapko ek tarah se A star ka sara funda clear ho gaya. To yahan pe f(n) matlab hume cost find kar rahe hain which is equal to g(n) + h(n). g(n) kya hai actual cost from start node to the n and estimation of the cost from n to the goal node. Matlab kehne ka kya hai ki hamare paas ek start node hai aur us start node se hamare paas goal state mein jana hai. Aur goal state mein jane ke liye mere paas kya hai different different nodes hain in between.
[2:08]To in between jo nodes hain hum unko bol diya let's say this is a list of n number of nodes. To yahan pe agar mere ko S se N jana hai S se N kya hai actual cost hai us path ki cost hai jo mujhe ek intermediate node jo ki N hai us pe leke ja rahi hai jisko hum bolte hain g(n). Lekin woh N node koi bhi ho sakti hai ye N node mujhe goal state pe leke ja rahi hai ye bhi mujhe goal state pe leke ja rahi hai ye bhi mujhe goal state pe leke ja rahi hai. Baaki ki sari jo mujhe kya pe leke ja rahi hai goal state mein leke ja rahi hai. Woh goal state mein kitni cost mein leke ja rahi hain uska estimation actual value nahi optimal value nahi uski heuristic value ya estimate value. Jisme hum kai bar heuristic value ko kya bol dete hain kisi node ki property bhi bol sakte ho kisi node ki aap characteristic ko bhi kya bol sakte ho ek heuristic value hai ek estimation hai. Woh kehta hai ki main yahan se yahan is cost mein jata hu this is the actual cost lekin ye mujhe aage goal state mein particular kisi cost mein leke ja rahi hai. That is the estimate lekin baad mein hum usko kya karte hain optimal convert karne ki koshish karte hain ya shortest find out karne ki koshish karte hain. That is why A star mein jo star hai usko hum generally bolte hain yahan pe iska matlab kya hai admissible. Matlab A star ek admissible algorithm hai iska matlab kya hai ki guarantee deta hai ye ki optimal solution aayega hi aayega. To yahan pe hum start karte hain f(n) = g(n) + h(n) se to sabse pehle hamare paas yahan pe aap graph bhi le sakte ho, tree bhi to generally hum data structure yahan pe graph lete hain aur maine yahan pe directed liya hai aap undirected graph bhi le sakte ho. To yahan pe mere paas jo start node hai woh hai yahan pe S, S ko maine naam diya hai start node ka aur jo G hai woh hai meri goal state. Matlab mujhe S se goal state mein pahunchna hai to ye beech mein jo bhi hai B, C, F, E, D ye sari kya hai N nodes hai. Simple sa point hai aur yahan pe mere paas ye kya diya hua hai ki S se B jaane ki cost hai 4. Ye hai actual cost ki mujhe pata hai ki S se B agar jana hai to char cost lagegi. Lekin ye jo red mein aapko dikh rahe hain ye red mein kya hai estimation of the value matlab heuristic value hai aur generally hum estimation find out kaise karte hain like best first search algorithm ke use ki help se hum unko find out kar sakte hain heuristic value. To ye ek property hai ek node ki ki mere paas S se B pe jaane ki cost hai 4 matlab main S se B jana hai to 4 cost hai. Aur B keh raha hai ki main tere ko S, G pe le jaunga B S ko bol raha hai ki main tere ko G pe le jaunga with the cost of 12 lekin again ye uski estimation value hai. Jisko hum baad mein convert karenge optimal se ya aap keh sakte ho hume optimal ki taraf jana hai. To sabse pehle agar hum baat kare S se to S se hamare paas jo hai already agar aap nikalna chahte ho f(S) matlab sabse pehle aap is value ko nikalna chahte ho S ke liye to hamare paas g(n) matlab S se S mein jane ki cost kya hai?
[4:58]Ek node se ussi pe jane ki cost obviously kya hogi zero plus what is the h(n) h(n) matlab us node ki heuristic value that is what 14. To aap isko kya bol sakte ho the cost is what 14 next hamare paas yahan pe waise bhi agar aap find out karna chahte ho to kar sakte ho otherwise main next node se start kar rahe hain matlab S hume kahan pe leke ja raha hai B aur C pe. To aap kaise mention kar sakte ho S se hum kahan pe ja sakte hain ya to B pe aur ya hum S se kahan ja sakte hain C pe. Do taraf hum yahan pe ja sakte hain. To agar hum S se B jaate hain let's say agar main S se B jata hu what is the cost of S to B four that is a g(n). Ye kya hai g which is actual cost aur B ki heuristic value B ki heuristic value humne yahan pe add ki to ye kya agaya 16. 4 + 12 that is 16 aur agar hum niche ja rahe hain S se C ki jo actual cost hai g(n) woh kya hai 3 plus C ki jo heuristic value hai woh kya di hui hai 11 to 3 + 11 that is what 14. To obviously yahan pe 16 aur 14 mein se kaun sa kam hai 14 to yaani main kaun si cost pe jaunga ya kaun si taraf move karunga S se C ki taraf move karunga. To ab mere paas ek tarah se kya cost ban gayi kya path ban gaya SC kyuki ye combined keh sakte ho aap SC ban gaya ab SC mujhe kahan pe leke ja raha hai E pe leke ja raha hai. Aur SC mere ko kahan pe leke ja raha hai SC se main E pe bhi ja sakta hu aur SC se main yahan pe D pe ja sakta hu. Do taraf matlab C se main E pe bhi ja sakta hu C se main D pe bhi ja sakta hu to aap isko SC bol sakte ho kyuki humne S se C ki already jo hai woh value find out kar li f(n) already find out kar liya that is what 14. To maine isko choose kiya ab hum baat kare agar S se S C se E matlab yahan se mujhe E pe jana hai to cost kya hui 3 + 10. S se C, C se E to kya hui 3 + 10 this is the actual cost plus what is the heuristic value of E, heuristic value of E is 4.
[7:03]To yaani ye total cost kya agayi 3 + 10 + 4 that is 17. Aise hi hum dusri cost find out karte hain SC se hume kahan pe leke ja rahi hai D pe to S se C ki cost kya hai 3. C se D ki cost kya hai 7 to aap isko kya bol sakte ho 3 + 7 SC to already 3 hai na SC 3 plus D pe hume jana hai to kya hogi 3 + 7 is 10. Plus D ki heuristic value aapko calculate karni hai to D ki heuristic value hamare paas already given hai that is 6 to ye kya cost hogi total 7 + 3 10 + 6 16. To yahan pe cost aayi ek 17 ek 16. Ab yahan pe aapko kya mind mein rakhna hai ki 16 cost yahan bhi hai 17 bhi hai dono mein se minimum kya hai 16. Lekin jab humne S se B ki taraf gaye the wahan pe bhi humari cost kya aayi thi 16 to ye bhi ek hai hamare mind mein aur dusri ye bhi hai. To in dono ko hi aap explore kar sakte ho matlab dono ko alag alag explore kar sakte ho to in dono ko agar explore kare hum to yahan pe kya ban gaya S se B matlab S B to already hai hamare paas kyuki iski bhi cost kya aayi thi 16 aur iski bhi cost hamare paas kya aayi hai 16 aayi hai to dono ki cost jo hai woh kya hai similar. To yahan pe S B se hum gaye kahan pe F pe aur S B se hum kahan pe ja sakte hain E pe.
[8:28]To in dono ki value hum yahan pe find out kar rahe hain. Dhyan se dekho S B se hum F pe bhi ja sakte hain S B se hum E pe bhi ja sakte hain to S B ki cost kya hai 5 plus. B mujhe F pe kitne mein leke ja rahi hai 4 + 5 plus F ki jo heuristic value hai. What is the F heuristic value 11 to total kya ho gaya yahan pe 9 + 11 that is 20. This is a point aur hum F pe pahunch jayenge then agar hum baat kare E ki to S se B ki cost kya hai 4 which is already there aur B se E ki cost kya hai 12 plus E pe pahunch gaye to E ki cost kya hai matlab E bol raha hai ki main tere ko G pe le jaunga with the cost of heuristic value of 4 to 4 hum isme add kar dete hain to ye bhi kya aayi value 20. Dono value jo hain yahan pe kya aayi 20 to obviously ye values jyada hai hamare paas ek aur value thi yahan pe 16 wali kaun si ye. S se C, C se D ye bhi kya aayi thi 16 hum isko bhi explore karte hain kyuki already other values jo hain woh badi a rahi hain. To agar hum isko explore kare to ye kya agaya SC D matlab ye teen ho gayi SC D. Ab D mujhe kahan pe leke ja rahi hai E pe. SC D aur D mujhe kahan pe leke ja rahi hai E pe to SC kya hai 3 which is already we have calculated main again dobara calculate kar raha hu but ye humne already calculate ki hui hai plus 7 kyuki ye S se D pe jane ki cost kya hai 3 + 7 that is 10.
[9:58]Aur mujhe D se E pe jana hai to uski cost kya hai 2. To ye wali jo hai actual cost hai which is what g(n) plus what is the heuristic value of E that is 4. To 3 + 7 10 + 2 12 + 4 that is 16. To yahan pe mere paas kya value aayi 3 + 7 10, 12 + 4 16 to yaani abhi bhi mere paas jo hai 16 isse kam hai 20 se bhi kam hai is 20 se bhi kam hai. Woh bhi mere ko leke ja rahi hai goal state pe lekin obviously main minimum wali ko choose karunga main kaun si choose ki 16 wali. To 16 wali agar main choose karta hu to 16 wali ye isiko hi hum aage explore kar rahe hain pehle SC se D gaye the ab SC D se hum E pe chale gaye. Ab hum next dekho yahan pe dhyan se SC D E se hum kahan pe jayenge E dekho hume kahan pe leke ja rahi hai G state pe leke ja rahi hai that is our goal state. To SC isko aap although main baar baar calculate kar raha hu lekin aap ek baar mein bhi kar sakte ho SC kya ban gayi ye 3 plus C se D 7 to 7 + 3 10 + 2 that is what 10 + 2 is what 12.
[11:10]12 se main ab dekho yahan pe hamare paas SC D ki cost to 12 agayi ab D yahan se E se main kahan pe ja raha hu G pe ja raha hu. What is the actual cost 5 plus G ki heuristic value kyuki hum hamesha g(n) + h(n) calculate karte hain to G ki matlab goal state ki heuristic value kya hogi. So by default assume karke chalo ki goal state ki heuristic value kya lete hain hum hamesha zero lete hain to yahan pe mere paas answer kya aaya 12 + 5 that is 17. To ye jo hai meri minimum value aayi 17 to 17 se main kahan pahunch gaya goal state pe pahunch gaya. Although aap inko bhi explore karna chahte ho aage kar sakte ho lekin ye already agar 20 20 le rahi hain to maximum aage bhi ho sakta hai possible hai ki ye jyada value hi le. Agar aap phir bhi ek check karna chahte ho to yahan pe check kar sakte ho let's say agar main S B F matlab S B F to ye kya hogi cost 9. Yahan se main gaya F se kahan pe jaunga main G pe jaunga to what is the cost of F to G 16. 9 + 16 and what is the goal heuristic value G heuristic value kya hai zero to 9 + 16 aapka aaya 25. Obviously 25 jo hai 17 se bahut jyada value hai aur aap koi bhi isme find out karoge to aapko ye wali jo value hai yahi aapko optimal value pe leke jayegi matlab minimum cost pe leke jayegi. To yahan pe answer kya hai aapka 17 cost jo hai usse hum is pe find out kar sakte hain ki kaise hume goal state mein pahunchna hai. So this is how bahut hi simple sa funda hai agar aap ek baar isko aur chala ke dekhoge ek baar dobara se check karoge in case nahi clear hua aapko easily clear ho jayega. To yahan pe hum last point yahan pe baat karte hain kyuki aapko jitna bhi material milega na iska online aapko ya to graph explain kiya hoga. Lekin hamara motive kya hai graph ke sath sath jo hai hum theoretical points bhi discuss karna chahte hain. To theoretical point bhi humne discuss kiye graph bhi discuss kiya aur ek last point yahan pe main time complexity ke bare mein batana chahta hu. What is the time complexity of the A star generally hoti hai order of V + E that is number of nodes plus number of edges. Woh to by default hogi jitne number of nodes aap sari nodes ko ya maximum sari edges ko hi traverse karoge isse jyada to kar hi nahi sakte. Lekin hum artificial intelligence ki term mein isko bolte hain order of B ki power D where B is the branch factor. Branch factor matlab kitne kitne mere paas children hai kisi bhi particular node ke kitne children hai that is called the branch factor aur D yahan pe kya hai depth. So D ki power B ki power D is what that is the time complexity and space complexity is also what B ki power D which is same as compared to the time complexity. To ye algorithm time bhi jo hai woh B ki power D le rahi hai aur space jo hai matlab kitne space ye cover kar rahi hai to run this all algorithm again B ki power D this is the maximum value which can be true. So this is all about lekin ek last point yahan pe main aur batana chahta hu ki jo A star hai A star is admissible aur isme jo under estimate aur over estimate ki hum baat karte hain. To under estimate aur over estimate main next video mein explain karunga with example aur ye bahut hi important point hai. To ye basic ho gaya aur under estimate kya hota hai over estimate kab ye heuristic value deta hai kab nahi deta kab optimal deta hai kab nahi deta ye hum next video mein check karenge so this is all about the basics of A star.
