CHOICE OF PROGRAMMING LANGUAGE You would only use the Python programming language to write the solution of this programming assignment. No other programming language should be used. ASSIGNMENT CONTENTS I. Introduction II. Algorithm Review III. What You Need to Submit IV. What Your Program Outputs V. Important Information VI. Before You Finish NOTE: This assignment incorporates material learned from both Uninformed search and Informed search (Chapter-3 of the textbook). I. Introduction I The Romania Map Problem asks us to apply the uninformed and informed search techniques to find the path and the path cost among two cities on the map. We would start from a certain city towards the search goal, and that would also be another city on the map. For this assignment, you would implement your search that asks you to define the start state (a city) and the goal state (another city). It then finds the path and the path cost from the start state to the goal state, II. Algorithm Review Recall from the lectures that search begin by visiting the root node of the search tree, given by the initial state. Among other book-keeping details, three major things happen in sequence to visit a node: First, we remove a node from the frontier (fringe) set. Second, we check the state against the goal state to determine if a solution has been found. Finally, if the result of the check is negative, we then expand the node. To expand a given node, we generate successor nodes adjacent to the current node, and add them to the frontier (fringe) set. Note that if these successor nodes are already in the frontier, or have already been visited, then they should not be added to the frontier again. Page 2 of 4 . This describes the life cycle of a visit and is the basic order of operations for search agents in this assignment- (1) remove (2) check, and (3) expand. In this assignment, we will implement algorithms as described here. III. What You Need to Submit Your job in this assignment is to write Python code that implements the rules as described in the Introduction and Review sections given above. When executed, the code would ask for the start state (a name of the city), and the goal state (a name of the city) and returns the path and the path cost of the search performed. You need to implement all three of the below given algorithms in performing the search: bfs (Breadth-First Search) dfs (Depth-First Search) ast (A-Star Search with the Straight-Line (Euclidean Distance) Heuristic) The map would be given as an input to these algorithms. The map itself could be implemented as a graph or any other data structure as per your choice. You may take the straight-line (Euclidean Distance) heuristic values as given in Chapter-3 for the A Search algorithm IV. What Your Program Outputs When executed, your program will create / write to a file called searchResults.txt, containing the following statistics for each of the above algorithms: . path_to_goal: the sequence of moves taken to reach the goal cost_of_path: the number of moves taken to reach the goal nodes_expanded the number of nodes that have been expanded search_depth: the depth within the search tree when the goal node is found max_search_depth: the maximum depth of the search tree in the lifetime of the algorithm running_time: the total running time of the search instance, reported in seconds V. Important Information Please read the following information carefully. Since this is the first programming assignment, you are being provided with many hints and explicit instructions. Before you post a clarifying question on the Google Classroom page, make sure that your question is not already answered in the following sections 1. Implementation You will implement the following three algorithms as demonstrated in lecture. In particular Breadth-First Search Use an explicit queue, as shown in lecture Depth First Search. Use an explicit stack, as shown in lecture A-Star Search Use a priority queue, as shown in lecture. For the choice of heuristic, use the straight-line NOTE For all data Page 3 / 4 Q + ctures in the Python language APL . distance function - 2. Order of Visits In this assignment, where an arbitrary choice must be made, we always visit child nodes in the Left-to-Right order 3. Tips on Getting Started Begin by writing a class to represent the state of the game at a given turn, including parent and child nodes. We suggest writing a separate solver class to work with the state class. Feel free to experiment with your design, for example including a map class to represent the low-level physical configuration of the cities, delegating the high- level functionality to the state class. When comparing your code with pseudocode, you might come up with another class for organizing specific aspects of your search algorithm elegantly You will not be graded on your design, so you are at a liberty to choose among your favorite programming paradigms. Your submission will receive full credit if your driver program outputs the correct information VI. Before You Finish Make sure your algorithms generate the correct solution for an arbitrary solvable problem instance of the map problem Make sure your program always terminates without crror and in a reasonable amount of time. You will receive zero points if your program fails to terminate. Running times of more than a minute or two may indicate a problem with your implementation, Make sure your program output follows the specified format exactly. For the path to goal, use square brackets to surround the list of items, use single quotes around each item, and capitalize the first letter of each item, Round floating-point numbers to 8 places after the decimal. You will not receive proper credit if your format differs from the provided examples above. PART-B: INSTRUCTIONS [251 In this part of the assignment, you are expected to give a complete description of the implementation strategy that you have followed in the PART-A. That is, you will need to describe the approach of the implementation for cach algorithm that you have implemented and the reason for choosing that approach. What other approaches that you have considered? Please make this part short but complete. Also, mention how to execute your code in numbered steps For answering this part, create one Word document having name as your ID. Finally, add the PDF of this file to the zip file END OF ASSIGNMENT 4 / 4 a + Page