WRITE LAB REPORT ON THIS SEARCH ALGORITMS DOING ALL THE TASK INDICATED WITH THE CODES.
Implementing Uninformed Search Techniques Objective: Finding shortest path using BFS, DFS and IDS search technique in python. Breadth- First Search (BFS) Breadth-First Search (BFS) is an algorithm used for traversing graphs or trees. Traversing means visiting each node of the graph. Breadth-First Search is a recursive algorithm to search all the vertices of a graph or a tree. BFS starts from a node, then it checks all the nodes at distance one from the beginning node, then it checks all the nodes at distance two, and so on. So as to recollect the nodes to be visited, BFS uses a queue. The steps of the algorithm work as follows: 1. Start by putting any one of the graph's vertices at the back of the queue. 2. Now take the front item of the queue and add it to the visited list. 3. Create a list of that vertex's adjacent nodes. Add those which are not within the visited list to the rear of the queue. 4. Keep continuing steps two and three till the queue is empty. Task 1: Apply Breadth First Search on following graph considering the initial state is 5 and final state is 8 . DEPTH-FIRST SEARCH (DFS) The Depth-First Search is a recursive algorithm that uses the concept of backtracking. It involves thorough searches of all the nodes by going ahead if potential, else by backtracking. Here, the word backtrack means once you are moving forward and there are not any more nodes along the present path, you progress backward on an equivalent path to seek out nodes to traverse. All the nodes are progressing to be visited on the current path until all the unvisited nodes are traversed after which subsequent paths are going to be selected. The recursive method of the Depth-First Search algorithm is implemented using stack. A standard Depth-First Search implementation puts every vertex of the graph into one in all 2 categories: 1) Visited 2) Not Visited. The only purpose of this algorithm is to visit all the vertex of the graph avoiding cycles. The DSF algorithm follows as: 1. We will start by putting any one of the graph's vertex on top of the stack. 2. After that take the top item of the stack and add it to the visited list of the vertex. 3. Next, create a list of that adjacent node of the vertex. Add the ones which aren't in the visited list of vertexes to the top of the stack. 4. Lastly, keep repeating steps 2 and 3 until the stack is empty. Tasks 2: Apply Depth First Search on the graph in Figure 1 above considering the initial state is 5 and final state is 8 . ITERATIVE DEEPENING SEARCH (IDS) The Iterative Deepening Depth-First Search (IDS) algorithm is an algorithm used to find a node in a tree. This means that given a tree data structure, the algorithm will return the first node in this tree that matches the specified condition. The IDS algorithm follows as: 1. For each child of the current node. 2. If it is the target node, return. 3. If the current maximum depth is reached, return. 4. Set the current node to this node and go back to 1 . 5. After having gone through all children, go to the next child of the parent (the next sibling) 6. After having gone through all children of the start node, increase the maximum depth and go back to 1 . 7. If we have reached all leaf (bottom) nodes, the goal node doesn't exist. Task 3: Apply Iterative Deepening Search on the graph in Figure 2 below considering the initial state is 0 and the final state is 6
