Suppose you want to construct a computer system to help decide the best route between two U.S. cities. You could first use Visual Prolog to build a miniature version of the system (see 2), since it will then become easier to investigate and explore different ways of solving the problems involved. You will use the final system to investigate questions such as:

Is there a direct road from one particular town to another?

Which towns are situated less than ten miles from a particular town?

The following program is a classic example of using backtracking and recursion to solve route planning.

/* Program ch16e02.pro */

DOMAINS

    town     = symbol

    distance = integer

PREDICATES

    nondeterm road(town,town,distance)

    nondeterm route(town,town,distance)

CLAUSES

    road(tampa,houston,200).

    road(gordon,tampa,300).

    road(houston,gordon,100).

    road(houston,kansas_city,120).

    road(gordon,kansas_city,130).

    

        road(Town1,Town2,Distance).

    route(Town1,Town2,Distance):-

        road(Town1,X,Dist1),

        route(X,Town2,Dist2),

        Distance=Dist1+Dist2,

        !.

Figure 16.1 shows a simplified map for the prototype.

Figure 16.1: Prototype Map

Each clause for the road predicate is a fact that describes a road of a certain length (in miles) that goes from one town to another.

The route clauses indicate that it is possible to make a route from one town to another over several stretches of road. Following the route, the driver travels a distance given by the third parameter, distance.

The route predicate is defined recursively; a route can simply consist of one single stretch of road, as in the first clause. In this case, the total distance is merely the length of the road.

You can also construct a route from Town1 to Town2 by driving first from Town1 to X, then following some other route from X to Town2. The total distance is the sum of the distance from Town1 to X and the distance from X to Town2, as shown in the second clause for route.

Try the program with the goal:

    route(tampa, kansas_city, X).

Can the program handle all possible combinations of starting point and destination? If not, can you modify the program to avoid any omissions?

The next example will give you ideas about how to get this routing program to make a list of towns visited enroute. Making such a list prevents Visual Prolog from choosing a route that involves visiting the same town twice, thereby avoiding going around in circles, and ensures that the program doesn't go into an infinite loop. When you've solved problems of this type, you can enlarge the program by adding more cities and roads.