please a
answer all assignment
LAB-06: Informed search algorithms Objectives: - Implementation of an inform search algorithm (A-star) Lab Outcomes: Students should get familiar with- - How A+uses heuristics to reach a goal - How to write a program in python to solve a maze problem Lab Requirements: - Juarterc notebook (Anaconda 3) A-star search algorithm: Some common terminologies in A-star search algorithm: - Node (also called State) - All potential position or stops with a unique identification, - Transition - The act of moving between states or nodes. - Starting Node - Where to start seamching - Goal Node - The target to stop searching - Search Space - A collection of nodes, like all board positions of a board game - Cost - Numerical value (say distance, time, or financial expense) for the path from a node to another node. - g(n) - this represents the exact cost of the path from the starting node to any node n - h(n) - this represents the heuristic estimated cost from node n to the goal node, - f(n) - lowest cost in the neighboring node n Solving a maze problem with python: A brief description of the problem: Here you will solve a maze problem, You haye to find the shortest path in the maze from a start node to the end node. The problem's description For this problem, there are four moves [left, right, up, and down) from a maze position provided a valid step is available. In red square positions, no movement is allowed (like in start position only down motion is available since up and left move are blocked by the wall while for the right is a red square position thus no movement allowed). First, we will create a class for a node that will contain all the attributes associated with the node like the parent of the node, position of the node, and all three costs (glb \& f) for the node. We initialize the node and build a method for Each time A enters a node, it calculates the mont f(n)=g[n)+h(n) checking the equality of the node with another node. Now we will build the path function, which will be used to return the path from the start node to the target node (end node), Now we will define the search function, which has multiple steps. The first step will be to initialize nodes and lists that we will use in the function. Add the starting node to the "yet to visit list." Define a stop condition to avoid an infinite loop. Define movement in terms of relative position, which will be used to find the child node and other relative positions. 4 hen met atart was thay interiation of of (4 isinemitiou bier pritue Now we use the current node by comparing all f cost and selecting the lowest cost node for further expansion. We also check max iteration reached or not, Sat a message and stop execution (avoid infinite loop] wite ataratlane in 1 o liet ber furteret ade for indes, itan in truneiceiget_ti_pisit_ditt) Remove the selected node from "yet to visit list" and add this node to the visited list. Now we put a check if we found the target square. If we have located the target square, then call the path function and return. For the selected node, find out all children (use the move to find children). Get the current position for the selected node (this becomes the parent node for the children) a) check if a valid location exists (boundary wall will make few nodes invalid) b) if any node position is invalid (red square) then ignore that c) add to valid children node list for the selected narent Here in the diagram, we show the black circle node is the current node, and green circle nodes are correct children node, For all child node: a) if the child is in the visited list, then ignore it and try the next child node. b) calculate child node g,h, and f values. For h heuristic for the cost to reach the goal node for the current node is calculated here using euclidean distance. c) if the child in "yet to visit list" then ignore it else, move the child to "yet to visit list." Now finally, we will run the program from the main with the maze and obtain the path. Refer to the path also shown using the arrow. Final result path Assessment: You are required to implement this lab and submit your work showing the code and results. Optional: You may try to use a different distance measure as [Manhattan
