Please use each of the following search algorithms to plan the route for Alice. For each algorithm, write down (1) the order of the nodes expanded when executing the tree search version of the algorithm, and (2) the path that Alice actually will visit according to results from the search. As you plan the routes, if multiple options are available when expanding the next node, use alphabetical order for tie-breaking. For compactness, please use the abbreviation in the parenthesis for each node, e.g., Alice's Home → A.

i. (4pts) Breadth-first search

 ii. (4pts) Depth-first search

iii. (4pts) Uniform cost search
iv. (4pts) Greedy search with the provided heuristic values

v. (4pts) A* search with the provided heuristic values
(b) (6 pts) Suppose Alice has a good friend Bob who has just finished his shift in Harmony Hair Salon. After hearing that Alice plans to go to Cyber Caf ́e, Bob proposes to drive her from Harmony Hair Salon to Cyber Caf ́e. Bob will buy her drink on their way. Assume the possible get-together journey and free drink mean a reward of 8 to Alice. To represent this, we add an edge from Harmony Hair Salon to Cyber Caf ́e with a cost of -8 and plan the route again based on this new graph.

i. (3pts) Can we get an optimal trip plan in the new graph using the A* algorithm with the provided heuristic values? What is your reasoning?

ii. (3pts) What is the optimal trip plan in the new graph? What is its overall cost? 2. (14 pts) Admissible and consistent heuristics

(a)  (8pts) Prove that if a heuristic is consistent, it must be admissible. (Hint: A heuristic function h(n) is consistent if the estimated cost h(n) for any node n is no greater than the sum of the step cost from node n to any neighbor nodes n′ (n → n′) and the estimated cost h(n′) for node n′.)

(b)  (6pts) Construct a heuristic function that is admissible but not consistent on a small search graph. Show the search graph and explain why the heuristic function you construct is admissible but not consistent. (Feel free to draw the graph in whatever software you prefer and use the command \includegraphics to place it in LATEX)

E! Alice plan her route using the map in Fig. 1. Byte Boutique (B) 12 Luna Lounge (L) 6 2 Data Depot (D) 11 7 Java Junction (J) 5 Fusion Fitness 3 2 3 Alice's Home (A) 15 3 Kaleidoscope Kids (K) Cyber Caf (C) 0 4 Echo Electronics (E) 10 4 2 3 Galaxy Groceries (G) Harmony Hair Salon (H) 7 Caf 2 6 Infinite Ink (1) 5 12