Transcript
Use with ChatGPT / Claude Auto-scroll A
Introduces the A* search idea, the cost function f(n)=g(n)+h(n), and the example graph used to demonstrate the algorithm. Explains the meaning of the edge costs and heuristic values before starting the search.
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 techniquewhich 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 thesetwo 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
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 Bindicates 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 ato 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 thenwe 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
Walks through the first expansion from the start node A, computes costs for B and C, and selects B because it has the lower estimated total cost. This section sets up the next frontier for continued search.
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 notthe 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 possiblepaths 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 saidearlier 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
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 theestimated 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 writtensimilarly 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 equalto 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
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 Cis 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
Expands B, evaluates the reachable nodes C and D, and compares them with the existing frontier. After considering the costs, the search continues by selecting D as the best next node.
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 casefrom 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 aswell 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 Gof 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
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 ofd 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 totalcost 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 aswell 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
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 thesame 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 nextthing 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 isonly 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
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 isequal 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 11here 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 ande 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
Expands D, calculates the costs for F and G, and then chooses F because it has the minimum cost. F is expanded next, leading directly to G with the best total cost.
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 herenow 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 theparent 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 to6 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
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 to8 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 minimumhere 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 tocheck 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
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 toG 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 thingfrom 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 youcalculate 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
Confirms that G is the goal node and stops the search. The speaker summarizes the final optimal path A to B to D to F to G and its total cost.
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 goalnode 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 tob 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
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 Subscribebutton for more videos press the Bell icon for regular updates thank you for watching