2. (20 pts.) Search Suppose there are two friends living in different cities on a map, such as the Romania map shown in AIMA and lectures. On every turn, we can move each friend simultaneously to a neighboring city on the map. The amount of time needed to move from city i to neighbor j is equal to the road distance d( between the cities, but on each turn the friend that arrives first must wait until the other one arrives (and calls the first on his/her cell phone) before the next turn can begin. We want the two friends to meet as quickly as possible. (Treat the call as though it takes no time.) Formulate this as a search problem. (a) (4) What is the state space? (You will find it helpful to define some formal notation here.) (b) (4) What is the successor function? (c) (2) What is the goal? (d) (2) What is the step cost function? (e) (6) Let SLD(i, j) be the straight-line distance between any two cities i and j. Which, if any, of the following heuristic functions are admissible? (If none, write NONE.) (i) SLD(i, j) (i) 2.SLD(i,j) (ii) SLD(i, j)/2 (f) (2) True/False: There are completely connected maps for which no solution exists 2. (20 pts.) Search Suppose there are two friends living in different cities on a map, such as the Romania map shown in AIMA and lectures. On every turn, we can move each friend simultaneously to a neighboring city on the map. The amount of time needed to move from city i to neighbor j is equal to the road distance d( between the cities, but on each turn the friend that arrives first must wait until the other one arrives (and calls the first on his/her cell phone) before the next turn can begin. We want the two friends to meet as quickly as possible. (Treat the call as though it takes no time.) Formulate this as a search problem. (a) (4) What is the state space? (You will find it helpful to define some formal notation here.) (b) (4) What is the successor function? (c) (2) What is the goal? (d) (2) What is the step cost function? (e) (6) Let SLD(i, j) be the straight-line distance between any two cities i and j. Which, if any, of the following heuristic functions are admissible? (If none, write NONE.) (i) SLD(i, j) (i) 2.SLD(i,j) (ii) SLD(i, j)/2 (f) (2) True/False: There are completely connected maps for which no solution exists