Tuesday, September 17, 2024

Uninformed Search Strategies

• To understand this Breadth- First Search  lets take a graph with nodes A, B, C, D, E,F and G . here I expand the shallowest unexpanded node.
• Here the fringe you see is the FIFO(First In First Out) queue .i.e., New successors go at end
• Here in Graph Search method we create two lists open list and closed list.
• We will place the start node In open and as we expand we take A to the closed list and generates the successors of A.
• The successors of A that I get are placed in closed list. Here in this case I got B and C are the successors of A.
• In the next step I take B for expansion, As we take B for expansion , place it in the closed list and generates the successors and these successors are placed in open list . Here the successors of B are D and E these are placed after the C in the next step..i.e.,C,D,E
• In the next step we expand c not D or E. As we expand C we place that in closed list and generates the successors.
• These successors of C i.e., F and G are placed in open list

.

This is how break-first search  works. I expand  the slowest unexpanded node. The fringe is a first in first out queue that is the new  successors go at the end. First I check if A  is a goal state. If A is not a goal state, I get its successors which is B and C .So, the fringe for me is B, C now. Next I check if B is a goal node  if not I get its expansion . and the next node  to be expanded is C not D this must be noted clearly. And then next node to be expanded becomes D and so on and so forth.