Exercise 3.5 [two-friends-exercise]
Suppose two friends live in different cities on a map, such as the Romania map shown in . On every turn, we can simultaneously move each friend 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 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.
-
Write a detailed formulation for this search problem. (You will find it helpful to define some formal notation here.)
-
Let $D(i,j)$ be the straight-line distance between cities $i$ and $j$. Which of the following heuristic functions are admissible? (i) $D(i,j)$; (ii) $2\cdot D(i,j)$; (iii) $D(i,j)/2$.
-
Are there completely connected maps for which no solution exists?
-
Are there maps in which all solutions require one friend to visit the same city twice?