hghu

Suppose there are two friends living in different cities on a map, such as the Romania map of the course textbook. On every turn, we can move each friend simultaneously to a neighboring city on the map. Assume the amount of time needed to move from city i to neighbor j is equal to the road distance d(i,j) between the cities, but on each turn the friend that arrives first must wait until the other one arrives before the next turn can begin. We want the two friends to meet as quickly as possible. Formulate this as a search problem. a) What is the state space? In particular, how would you (concisely) represent a state? b) What is the successor function? c) What is a/the goal state? d) What is the step cost function? e) 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) (ii) 2SLD(i,j) (iii) SLD(i,j)/2 f) Are there completely connected maps for which no solution exists. Justify your