1. Meeting in a city [Total 35 marks]

Suppose that Alice and Bob are two friends living in different cities in a country. They decide to meet each other in some city on the map of this country. On every turn, they can drive 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(i, j) between the cities, but on each turn the one who arrives first must wait until the other one arrives (and calls the first on his/her cell phone) before the next turn can begin. Alice and Bob want to meet as quickly as possible. Assume that there are totally n cities on the map. Let us formulate this as a search problem. The state space will be all possible city pairs (i,j).

(a) How many states are there in the state space? [5 marks]

(b) For a given state (i,j), what states are its successors? [5 marks]

(c) What is(are) the goal state(s)? [5 marks]

(d) What is the step cost function? [5 marks]

(e) Let SLD(i,j) be the straight-line distance between cities i and j. Which of the following heuristic functions are admissible? [5 marks] (i) SLD(i,j) (ii) SLD(i,j)/2 (iii) 2*SLD(i,j)

(f) Are there completely connected maps for which no solution exists? [5 marks]

(g) Are there any maps in which all solutions require one friend to visit the same city twice? [5 marks]