The
Assignment.docxwill be your guide for this assignment. This is a two part assignment, one section being non-code and the other section involving coding. This is to be done in
Java.
Also this is an AI based assignment.
I. Part 1: Non-coding problem You are given below a state-space graph that consists of nine states, the costs of the connections between them, and a heuristic, h(n), for each state. Your task is to find a path from start state S to goal state F. In order to find a solution path, one can use a number of different search methods. In the following questions, you are to find the path from S to F that the search algorithm given in the question would yield. 1.1 Using Depth First Search algorithm, please present the path from start state to the goal state. Expand the successors of a node in alphabetical order (e.g., if a node has 3 successors, A, B, and C, then A will be expanded before B, and B will be expanded before C). Show the search tree to find this solution 1.2 Using Breadth First Search algorithm, please present the path from start state to the goal state. Expand the successors of a node in alphabetical order (e.g., if a node has 3 successors, A, B, and C, then A will be expanded before B, and B will be expanded before C). Show the search tree to find this solution 1.3 Using Greedy Algorithm, please present the path from start state to the goal state. Show the search tree to find this solution 1.4 Using A* search algorithm, please present the path from start state to the goal state. Find the search tree to find this solution. II. Part 2: Coding problem: 2.1 Description: We are asked to develop a software agent that helps a user to find his way home from a given position. He is currently in Macau and his home is in USA. To accomplish this task, you will be given a map of possible flight connections. You will be required to create a program that finds the list of countries that the agent must travel on in order to get home.Macau China Hongkong Taiwan Japan Korea India France Russia USA Neitherland England Your program must take in an arbitrarily large list of intersections and find a napossible route to take. It will then output a list of each country taken in order (see example file). An example input (described in a text file) that would contain a list of connecting countries (edges): Macau China Macau Hongkong Macau Taiwan China Japan China India China France Hongkong Japan Hongkong Korea Taiwan India Korea Neitherland India Russia France England France USA Japan USA Your program would return the output of countries and other connecting locations traveled over including the starting and finishing countries, in order of travel. For example: Macau China Japan USA Your program also prints out the time that needed to find out the path using DepthFirstSearch (DFS), BreadthFirstSearch (BFS): For example: DFS10 (milliseconds) BFS11 (milliseconds) You can assume that country names will not have any white spaces in them. Additionally, the very first row has the starting state, while the very last row has the ending state just in the same way as the example. So, with other test cases, you must be able to help the agent find his way to other places as well. You must solve this problem using both depth first and breadth first search. Additionally, you should keep track of time requirements. Elapse time is computed by taking the difference between the time it finishes the search and the starting time. Your program should run as follows: · Assume that your agent is called pathfinder. · Run pathfinder from console. · Given the name of the file that contains the map (say map.txt) and the name of the country where the agent departs. · The screen output would looks like: Path: DFS: // Then you display the path using DFS here BFS: // Then you display the path using BFS here Time: DFS
BFS 2.2 Submission: What you should send back to me: (A) The source code, fully commented (*.java) (B) Create your own graph and send back your own data file: