Breadth-first search is a graph traversal algorithm

Breadth-first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes.

1. BFS in AI
Lab Assignment 1
Dr.HiteshMohapatra
AssociateProfessor
School of Computer Engineering
KIIT Deemed to be University

2. Assignment-1: Maze Solver using BFS and DFS
Objective:ImplementBFSandDFStosolveamaze.
ProblemStatement:Givenagrid-basedmazewhere0representswallsand1representswalkablepaths,findthe
shortestpathfromastartcelltoanendcell.
Tasks:
•UseBFStofindtheshortestpath.
•UseDFStoexploreallpossiblepathsandreportonevalidpath(notnecessarilytheshortest).
•ComparethenumberofnodesexploredbyBFSandDFS.

3. AI Search
ArtificialIntelligencecanbereferredtoasanagentthatcanact
rationally,itcanperformsomekindofsearchalgorithmtoachieveits
tasksinsolvingasearchproblemsuchasaMazeproblem.

4. A search problem in Artificial Intelligence
consists of:
•State Spacerefers to all possible states where the agent can be.
•Start Staterefers to the state where the search begins.
•Goal Staterefers to the state where the search ends.
•Solutionrefers to the sequence of actions that shows how an agent
searches from the start state to the goal state.
•Costrefers to the effort of the agent in doing the searching task.

5. There are several algorithms can be used to
solve a search problem, such as:
•Breadth First Search (BFS)
•Depth First Search (DFS)
•Greedy Best First Search (GBFS)
•A* Search

6. Breadth First Search (BFS)
TheBreadthFirstSearch(BFS)algorithmisusedtosearchagraphdata
structureforanodethatmeetsasetofcriteria.Itstartsattherootof
thegraphandvisitsallnodesatthecurrentdepthlevelbeforemoving
ontothenodesatthenextdepthlevel.
Inshort,BFSwillvisitallcurrentdepthlevelnodesbeforeproceeding
tothenodesatthenextlevelofdepth.

7. Pseudocode of the algorithm:
1.Inputgraph,start node, andgoal node
2.Definesolutionas a list
3.Definefrontieras a queue
4.Definevisitedas a list
5.Appendstart nodetofrontierandvisited
6.While thefrontieris not empty:
7.Dequeue thefrontierand store the value in theselected node
8.If theselected nodeis equal to thegoal node, append theselected nodeto thesolution, break from the loop, and return thesolution.
9.If not, just append theselected nodeto thesolution.
10.Loop through allneighborsof theselected nodefrom thegraph, append eachneighborto thefrontierandvisitedif theneighboris not yet in
thevisitedlist.

8. Solve Maze Problem with BFS
What is thesolutionandcostof the above Maze problem if we want to move fromAtoN?

9. Graph representation of Maze

10. Below is the step-to-step visualization of solving
the search problem using the BFS algorithm:
AppendAto theFrontier.

11. AppendAto theVisitedandBFS, then appendA’s neighbor (B)
to theFrontier. Finally, popAfrom theFrontier.

12. AppendBto theVisitedandBFS, then appendB’s neighbor (C)
to theFrontier. Finally, popBfrom theFrontier.

13. AppendCto theVisitedandBFS, then appendC’s neighbor (D,
G) to theFrontier. Finally, popCfrom theFrontier.

14. AppendDto theVisitedandBFS, then appendD’s neighbor (E)
to theFrontier. Finally, popDfrom theFrontier.

15. AppendGto theVisitedandBFS, then appendG’s neighbor (H)
to theFrontier. Finally, popGfrom theFrontier.

16. AppendEto theVisitedandBFS, then appendE’s neighbor (F)
to theFrontier. Finally, popEfrom theFrontier.

17. AppendHto theVisitedandBFS, then appendH’s neighbor (K,
I) to theFrontier. Finally, popHfrom theFrontier.

18. AppendFto theVisitedandBFS. Finally, popFfrom
theFrontier.

19. AppendKto theVisitedandBFS, then appendK’s neighbor (L)
to theFrontier. Finally, popKfrom theFrontier.

20. AppendIto theVisitedandBFS, then appendI’s neighbor (J) to
theFrontier. Finally, popIfrom theFrontier.

21. AppendLto theVisitedandBFS, then appendL’s neighbor (M)
to theFrontier. Finally, popLfrom theFrontier.

22. AppendJto theVisitedandBFS. Finally, popJfrom
theFrontier.

23. AppendMto theVisitedandBFS, then appendM’s neighbor
(N) to theFrontier. Finally, popMfrom theFrontier.

24. AppendNto theVisitedandBFS. Finally, popNfrom
theFrontier.

25. The answer to the above question will be:
•Solution: [A, B, C, D, G, E, H, F, K, I, L, J, M, N]
•Costs: 13 (there are 13 nodes to step to reach theend nodefrom
thestart node)

26. Code (Python)
Link: https://github.com/hm18818/AI-with-Python.git