Question 1 (30 points): Comparing Search Algorithms Consider the problem of finding the shortest path from a to z in the following directed graph: 13.0 10.0 0.0 11.0) Figure 1. Graph for question 1. Nodes are labeled with h values, and arcs are labeled with costs. Start at node a and use z as the goal node. When not considering costs, expand neighbours of a node in alphabetical order; and when considering costs break ties in alphabetical order. For example, suppose you are running an algorithm that does not consider costs, and you expand a; you will add the paths and to the frontier in such a way that is expanded before . Additional notes: We will say that a node is expanded when the algorithm checks to see if it is a goal node, then returns the path if it is (or adds its neighbor paths to the frontier if it is not). If a given node is expanded multiple times, it should appear in your list of expanded nodes multiple times. For the algorithms in questions 1.1-1.4, answer the following questions: (a) What nodes are expanded by the algorithm? Order the nodes from first expanded to the last. (b) What path is returned by the algorithm? (c) What is the cost of this path? 1.1. [5 points, Depth-first search 1.2. 15 points) Breadth-first search 1.3. 15 points A* 1.4. (5 points Branch-and-bound 1.5. [10 points) (a) [2 points) Did BFS and B&B find the optimal solution for this graph? (b) 14 points Are BFS and B&B optimal in general? Explain your answer. (c) [4 points) Did B&B expand fewer nodes than A*? Explain if your answer is true in general for these two algorithms and why