# A* Search | A Star Search algorithm Solved Example in Artificial Intelligence by Magesh Huddar

**Channel:** Mahesh Huddar
**Source:** https://www.youtube.com/watch?v=lusRf5v-TI0
**Transcript page:** https://www.withtranscript.ai/video/lusRf5v-TI0

## Chapters

- 0:00 — Estar Search Overview and Example Setup
- 1:43 — Expanding Initial Nodes and Choosing B
- 3:37 — Comparing Frontier Nodes and Selecting D
- 6:37 — Expanding D and Reaching G
- 8:55 — Goal Path and Final Cost

## Transcript

**[0:00]:** welcome back in this video I will discuss how to find an optimal path from initial state to the goal State using estar search algorithm with the help of simple solid example AAR search algorithm is a inform search technique which is used to find an optimal path from the initial state to the goal state in esta search algorithm the cost of each node is evaluated using the following function f of n is equal to G of n + h of n where G of N is a cost from initial state to the current node at n here similarly h of n is the estimated cost from node n to the goal State here so using these two things we will calculate the cost of each node based on this cost we will select a node and then we will do the same thing until we reach the goal node to understand the esta search algorithm I

**[0:52]:** will consider this example in this case we have been given different nodes the actual cost is given as well as the h values were given here the value one which is written on the path from A to B indicates the actual cost from A to B this three indicates the actual cost from B to D and so on and A5 means the estimated or the htic value of a that means the estimated cost from node a to the goal state that is g in this case G is the goal State here similarly for all other nodes the values are given here given this graph we we need to apply the estra search algorithm and then we need to find the optimal path from the initial state in this case the initial state is a to the goal state in this case the goal state is equalent to G here now we will apply the EST

**[1:43]:** search algorithm step by step and then we will find an optimal path here now we will start with the initial state that is a first we need to check whether the initial state is the goal state or not the initial state is a and the goal state is G here so a is not a goal state so what we need to do is we need to expand this a once you expand a there are two possible paths are there or there are two reachable nodes are there they are B and C here so what we need to do is we need to calculate the cost for b as well as cost for c as said earlier we use this equation that is f of n is equal to G of n plus h of n to calculate the cost for each nodes here so first we will calculate the cost for B in this case

**[2:29]:** that is cost for B is equal to F of B is equal to G of B plus h of B where G of B is what the cost from initial state to B and H of B is the estimated cost from B to Gold node here so in this case if you notice this graph the actual cost from initial state that is a to B is equalent to 1 here so that is what I have written similarly the estimated cost from B to Gold node it is present here which is equalent to how much six in this case so the total value is equal to 7 here similarly for c f of C is equal to G of C plus h of C the true cost from initial state to C is equalent to how much you can see here which is equalent to four here and H of C that is a estimated cost

**[3:16]:** is how much four here 4 + 4 is equal 8 in this case now we got the cost for both the nodes that is B and C the cost for B is equal to 7 and cost for C is equal to 8 here between these two 7 is minimum so at this point of time we will select b as the node for further expansion now once you select B what we need to do we need to

**[3:37]:** check whether B is a goal node or not right now B is not a goal node because G is the goal node here now what we do is from B we will find all reachable nodes in this case from B there are two reachable nodes are there one is D another one is C here so what we do we will calculate the cost for this C that is the C which is reached from b as as well as this D to calculate the cost again we use the same equation here so for this particular c f of C is equal to G of C plus h of C now what is the value of G of C the parent of C is equal to B here so from A to B the cost is equal to 1 from B to C the cost is equal to two addition of these two things is equal to

**[4:23]:** three here now what is h of c h of C is the htic value or the estimated value of C which is equal to 4 so the total value in this case is equal to 7 similarly F of d f of D is equal to G of D what is g of d g of D is the cost from A to B is equal to 1 and from B to D is equal to 3 the total cost is equal to four here from D the estimated cost is equalent to how much that is three here so 4 + 3 is equal to 7 in this case now we have calculated the cost for c as well as D from the parent B in this case now we have to one among the leaf nodes which are having the minimum the cost so in this case the cost of C is equal to 7 here cost

**[5:08]:** of D is equal to 7 and the cost of C where the parent is equal to a is equal to 8 in this case among these three both uh F of C and F of D are having the same value so what we can do is we can select any one of these two things and then we can continue from here onwards so I will select this C once I select this C what is the next thing we need to do we need to see whether C is a goal node or not right now C is not a goal node so what we do is we will find all reachable nodes from C there is only one reachable node that is e here so once you get this node we need to find the uh cost for this particular node so the cost for this node e is equal to F of e is equal

**[5:50]:** to G of e plus h of e what is the value of G of e so this e is reached from where C who is the parent of C B here so that's the reason G of e is equal to 1 + 2 + 5 so that is equalent to 8 in this case plus h of e h of e is equalent to how much three in this case so the total value is equalent to 11 here now there is only one reachable node from C the cost for that we have calculated now we need to compare the cost for each of these Leaf nodes there are three leaf nodes are there c d and e between these three the cost of D is minimum that is seven here so we need to select this node and then we need to continue from here onwards before we continue we need to check whether D is

**[6:37]:** a goal node right now D is not a goal node so we need to find all reachable nodes from D here so how many reachable nodes are there one is f and another one is equal to G here now we need to calculate F of f as well as F of G here now if you want to calculate F of f uh we need to calculate the cost till F what is the cost till f the parent of f is D the parent of D is B here and the parent of B is equal to a the meaning is we have followed this F that means 1 + 3 + 2 that is equalent to 6 here and H of f h of f is equalent to how much one in this case so the total value is equal to 7 here similarly F of g f of G is equal to G of G

**[7:23]:** plus h of G what is g of g g of G is nothing but 1 + 3 + 4 which is equal 8 8 + h of G is equal to Z so the total value is equal to 8 in this case now we got one 2 3 and four leaf nodes now we need to compare the cost for each of these Leaf nodes once you compare it uh the cost of leaf node f is minimum here that is seven here so what we need to do we need to select F and then we need to continue from here onwards once you select F what is the thing we need to do we need to check whether f is a gold node or not right now f is not a goal node so what we do is we will expand F here expand means we need to find the reachable nodes so what are the

**[8:07]:** reachable nodes are there from if there is only one reachable node that is g here so what we need to do we need to calculate the value of f of G here so F of G is equal to G of G plus h of G so for this G of G uh we have followed this path that is a to b b to d d to F and F to G you can notice that particular thing from here now if you add all these things 1 + 3 + 2 + 1 that is equalent to 7 and H of Z is equal to zero the total value is equalent to 7 here now once you calculate the cost for this Leaf note G there are four leaf nodes are there and if you compare the cost this Leaf node has the minimum cost here so we will select this Leaf node for further expansion so

**[8:55]:** the leaf node is what G here so once you select G for further expansion we we need to check whether G is a goal node or not right now G is a goal node because it is a goal node we need to stop here the meaning of this one is we have reached the goal node from initial State now the question is what is the path so the path followed in this particular case is a to b b to d d to F and F to G here so that is what I have written in this case and what is the path cost for this one the path cost is equal to 1 + 3 + 2 + 1 which is equal to s in this case so what we did in this case is uh we have applied esta search algorithm for the given graph and we found the optimal path from initial State

**[9:39]:** a to the goal State G as well as we have calculated the path cost I hope the concept of esta search algorithm is clear if you like the video do like and share with your friends press the Subscribe button for more videos press the Bell icon for regular updates thank you for watching