Flight planning. This exercise uses the relation class implemented in section 9.6. Fly By Night airlines asks you to write a program that can plan flights for its passengers. We are given a database containing a set of facts of the form

The first two arguments represent a pair of cities served by Fly By Night airlines, the third argument is the great circle distance between the two cities, and the fourth argument is a boolean that is true if there is a direct flight between the two cities and false otherwise. For this exercise, do the following:

(a) Write a planner that, given a source city and a destination city, returns a path between the two cities that is noncircular, i.e., no city appears twice in the path. Define the planner as a function {Plan City1 City2} that returns a pair Distance#Path, where Distance is the total distance flown on the path from City1 to City2 and Path is a list of cities representing the path from City1 to City2.The function should be nondeterministic so that Solve can use it to generate different plans.

(b) Use the above planner to compute the shortest path between two cities. Define a function {Best Plan City1 City2} that returns the shortest path.

(c) The implementation of Best Plan will enumerate all solutions to find the best one. This can be very costly in time. To reduce the time, we can use a heuristic called best first. Whenever we need to choose a city, we choose first a connected city that has the shortest direct distance to the destination. Define a function {Good Plan City1 City2} that uses this heuristic.