Route finding related problems using the below map:

1. Use the greedy search strategy.

2. Use the A* search strategy.

3. Use the hill climbing search strategy.

4. Is the heuristic function you used above admissible? (Does the heuristic give you information that helps you efficiently move towards the goal?) Why or why not? Can you think of a better (more informed) heuristic function?

Please write search tree and do 1~5(based on search tree)

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.

6. A* search is essentially a uniform cost BFS heuristic search technique. What characteristics of the search space and of the heuristic function could make it better to use uniform cost BFS than to use A* search? (Hint: consider the total cost of searching to find a solution.)

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: 2 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. a number denoting the order in which it is expanded (not the order generated); 3. the ffunction (evaluation function) value for the node - given in parenthesis. 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. Recall that for the informed heuristic searches, your evaluation function, f(node), will be some combination of: g(node)- the actual path cost from the initial state to the node; h(node)-the heuristic function, the estimated cost of the least cost path to a goal from the node. For these problems: g(node) should be based on the costs associated with the lines in the map figure. For example, 8(B) on the path starting at A and going directly to B is 4 because it costs 4 to go from city A to city B; h(node) should be the minimum cost to reach the next city (that does not introduce a cycle into the path, in other words, does not go back to a city that has already been visited), or if the node is a goal state. For example, h(A) is 3 since 3 is the minimum of the costs (3, 4, 5, 5) to reach another city from A. Note, this is called the nearest neighbor heuristic and is NOT the same as the straight line heuristic we used on our sample problems in class. 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