# Beam Search Algorithm Solved Example in Artificial Intelligence | Beam Search in AI by Mahesh Huddar

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

## Chapters

- 0:01 — Beam Search Overview and Setup
- 1:19 — Expanding the First Frontier
- 3:22 — Selecting Best Successors Iteratively
- 5:57 — Reaching the Goal and Result

## Transcript

**[0:01]:** welcome back in this video I will discuss how to use beam search algorithm in artificial intelligence to find an optimal path from the initial node to the goal node with the help of simple solid example in this case we have been given this graph in this case we have been given this graph where s is the initial State and G is the goal State here for Simplicity only age weights are used for evaluating each and every node that is f of n is equal un to G of n in this case sometimes F of n is equal to H of n may be given that is nothing but each and every node is evaluated using chastic values sometimes we may use both that is f of n is equal to G of n + h of n in this case we are using only G of n that is nothing but the H WS here

**[0:55]:** a beam width of beta is equal to 2 is given the meaning of this one is at a given point of time if we have more than two successes we will select only top two successors and then we will continue from there onwards so that is the meaning of beam width of beta is equal to 2 in this case now we will apply the stepbystep procedure and then we will find an optimal path from the initial

**[1:19]:** state to the goal State here the initial state is yes here what we do is we will create a tree with initial node that is nothing but s and then we will add this s to the Clos list that is the first thing we do and what is the G of n or G of s g of s is equal to zero because from s to S the true cost is equal to zero in this case and uh the node which is reachable from s is what from s we can reach only I in this case so that is what we have added in node data structure that is I and its cost is equal to six here now what we do is because s has only one adjacent node or the reachable node there is no point in selecting the top two or something like that in this case beta is equal to two

**[2:15]:** the meaning is we need to select a top two but here as there is only one node what we need to do is we need to select that node and then we will add that to the tree here now we need to find all adjacent nodes to this I how many adjacent nodes are there for i n is the first adjust node H is the second one C is the third one here for each of these we need to calculate the uh true cost here that is nothing but for n you can see here n can be reached from s to I and I to n uh that is s to I is 6 here 6 + 7 is equal to 13 so that is what I have written here similarly for H H is 6 + 8 that is 14 and for uh C 6 + 31 that is 37 that is what I

**[3:01]:** have written in this uh data structure now what we need to do we need to select top two nodes because beta is equal to two here so what are the top two nodes in this case n and H so we will add those two things to the tree and n and H will be added to Clos list over here this is how the tree will look like once we add n and H in this case now

**[3:22]:** once you add n and H to the tree what we need to do is from n and H we need to find all the adjacent nodes from n there is only one adjacent node that is L so we need to find the cost of L uh to find the cost of L how did we reach this L here s to I I to n the cost to reach n is already known to us that is 13 here now 13 + 18 which is equal to uh 31 in this case that is what I have added into this data structure from H there are two reachable nodes are there one is K another one is f here up to H that is s to I and I to H the cost is 14 here 14 + 5 that is equalent to 19 that is the cost of f here and for k 14 + 33 that

**[4:14]:** is nothing but 37 + 10 that is 47 that is what I have added here now once you add all these things in node data structure we need to find the top two nodes uh in this case f and L are the top two nodes f is coming from uh H here and L is coming from n in this case f is reachable f is adjacent to H and L is adjacent to n in this case so once we add those two things to the search tree the search tree will look something like this again we have to add L and F to this close this here now we need to find all adjacent nodes from L and F so L is present here and F is present here from L there is only one reachable node that is C up to L the cost is known to us what is that 31 that is

**[5:03]:** nothing but 6 + 7 + 18 that is equal to 31 plus this 9 that is equalent to for this C we got the cost as equalent to 40 in this case now from F we need to find the adjacent nodes uh the adjacent nodes are L here M here and G these are the three adjacent nodes are there up to M the cost is equal to 19 19 + 35 that is equalent to 54 for L that is what I have written here for M 19 + 11 that is 30 and for G 19 + 22 that is 41 that is what I have written here again we need to find the top two nodes what are the top two nodes in this case M and C so m is reachable from where m is reachable from F and C is reachable from l in this case now we need to add those two

**[5:57]:** things to this search tree the search tree will look something like this now we need to find all reachable nodes from C and A from C we don't have any reachable nodes from M we have one reachable node that is g so what is the cost of G now up to M we have 30 as the cost and from M to G the cost is 16 so 30 + 16 is equal to 46 that is what we have added here now what we need to do we need to select top two nodes right now we have only one so we have to s it because we don't have any other option in this case now we will select this G and we will add it to search tree the search tree will look something like this because G is reachable from here this G is reachable from M so that's the reason I have added

**[6:43]:** it here again we will try to expand C and G here we don't have any successors or the adjacent noes for C from G we don't have again any uh adjacent nodes and G is the goal node the meaning of this one is what we have reached the goal node here so because we have reached the goal node we have to stop here we need to find the final path the final path is nothing but s to I I to H H to f f to m m to G here so that is what I have drawn with red color here and what is the cost of this path the cost of this path is equal to 46 the meaning of this one is uh the optimal cost from initial node to goal node is 46 in this case so in this video I have discussed how can we apply beam search algorithm in artificial

**[7:34]:** intelligence for the given graph to find the optimal path as well as the optimal cost from initial state to goal State here I hope the concept of beam 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 okay