Route finding ProblemPlease write search tree and do 1~5 ( Based on the search tree

Below is a map of a group of cities (not drawn to scale), labeled with the cost (mileage) to go from one city to another F You are to use this map for the search problems, given later. For each of these problems, solve the route finding problem to determine a path from city A to city H, using the specified search strategy. Draw the search tree that would be produced by each search strategy. Make these tree searches by excluding operators that would result in a city being revisited on a path - i.e., avoid loops in the search paths. Each node in the search tree should be labeled with: 1. the state/city it represents; 2. the f function (evaluation function) value for the node - given in parenthesis. For the uninformed algorithms in this homework, this is either the step cost or the path cost, as determined by the algorithm's strategy. In addition to the search tree, list: 1. the solution that is found; 2. the cost of the solution found; 3. the number of nodes that were expanded; and 4. the depth of the tree when the solution was found. Additional information: You are to apply the search algorithms as written in the text. For example, do not "improve" breadth first search by terminating it as soon as a goal is generated. Consider that when you add nodes into the queue, you do so in alphabetic order. For example, when you first expand A, consider that the nodes are added so that they are in the order B, C, D. Route finding related problems using the above map: 1. Use the breadth first search strategy. 2. Use the depth first search strategy. 3. Use the uniform cost search strategy. 4. Use the iterative deepening search strategy. 5. Discuss the relative characteristics of each of the search strategies for this particular problem. That is, state if the solution was optimal, and how many "unnecessary nodes were expanded. Also explain in general, what is the best, expected, and worst case behavior of the algorithm. Also explain if certain assumptions lead to different behaviors. Below is a map of a group of cities (not drawn to scale), labeled with the cost (mileage) to go from one city to another F You are to use this map for the search problems, given later. For each of these problems, solve the route finding problem to determine a path from city A to city H, using the specified search strategy. Draw the search tree that would be produced by each search strategy. Make these tree searches by excluding operators that would result in a city being revisited on a path - i.e., avoid loops in the search paths. Each node in the search tree should be labeled with: 1. the state/city it represents; 2. the f function (evaluation function) value for the node - given in parenthesis. For the uninformed algorithms in this homework, this is either the step cost or the path cost, as determined by the algorithm's strategy. In addition to the search tree, list: 1. the solution that is found; 2. the cost of the solution found; 3. the number of nodes that were expanded; and 4. the depth of the tree when the solution was found. Additional information: You are to apply the search algorithms as written in the text. For example, do not "improve" breadth first search by terminating it as soon as a goal is generated. Consider that when you add nodes into the queue, you do so in alphabetic order. For example, when you first expand A, consider that the nodes are added so that they are in the order B, C, D. Route finding related problems using the above map: 1. Use the breadth first search strategy. 2. Use the depth first search strategy. 3. Use the uniform cost search strategy. 4. Use the iterative deepening search strategy. 5. Discuss the relative characteristics of each of the search strategies for this particular problem. That is, state if the solution was optimal, and how many "unnecessary nodes were expanded. Also explain in general, what is the best, expected, and worst case behavior of the algorithm. Also explain if certain assumptions lead to different behaviors