Suppose two friends live in different cities on a map such a

Suppose two friends live in different cities on a map, such as the Romania map shown in the figure below. 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.

a. Write a detailed formulation for this search problem. (You will find it helpful to define some formal notation here.)

b. 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 · D(i,j); (iii) D(i,j)/2.

c. Are there completely connected maps for which no solution exists?

d. Are there maps in which all solutions require one friend to visit the same city twice?

Oradea 71 zerind 151 Arad Sibiu 99 Fagaras 118 Rimnicu Vilcea Timisoara 211 97 Pitesti O Mehadia 146 138 Drobeta 120 Craiova Giurgiu Figure 3.2 A simplified road map of part of Romania. lasi Urziceni Vaslui Eforie

Solution

a) The searching can be started by defining the states of two friends ,which defines at which particular position or in which particular state a person is moving i,j is the pair of cities so inorder to define the states the successor function can be given as a,b ,so now the adjacent pairs o f cities and states can be given as (a.i) (b.j) .Now we have to achieve the position such that at i,j both the people should be at same location and the goal can be given from (a,b),(i,j) where at some point i should be equal to j .

b) option iii )D(i,j)/2. can be admissable becuase the way between two people is evenly laid

c) yes,there is a possibility of connected maps with no solutions only when two friends are moving in odd ways ,that is one taking a step forth and other a step back

d) Only if both of them are not from the same city ,or else one has to roam twice to the city which is not an efficient way