Navigation  without Java Scripts

A Simple Routing Distance Problem

Suppose you want to construct a prototype computer system to find the best route between two U.S. cities.
You could use Visual Prolog to build a miniature initial version of the system since it will then be easier to explore and investigate alternative ways of solving the problem. The complete system will be able to answer 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 is the simplified map used for the prototype:

Execute the program as a CGI script by pressing the "Submit Query" button on the form below:

What is the distance from  to  

Show Source  to Route-application.

Show Source to Route-application incl. cgi-support.

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

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).

route(Town1,Town2,Distance):-
  road(Town1,Town2,Distance).

route(Town1,Town2,Distance):-
        road(Town1,X,Dist1),
        route(X,Town2,Dist2),
        Distance=Dist1+Dist2,!.

Each clause for the road predicate is a fact that describes a road (and its 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:

route(Town1,Town2,Distance):-
   road(Town1,Town2,Distance).

In this case the total distance is merely the length of the road.

A route from Town1 to Town2 could also be created by first driving 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.

route(Town1,Town2,Distance):-
    road(Town1,X,Dist1),
    route(X,Town2,Dist2),
    Distance=Dist1+Dist2,!.

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 an idea of how to get this routing program to make a list of towns visited en route. 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.