2015
04.06

tspHere’s an appropriate example of where recursion is absolute gold. How about a searching problem? Have you ever heard of the Traveling Salesman problem? The idea is that a traveling salesman must visit several cities. His time is valuable, so he wants to find the shortest route through all the cities. This problem is about as practical as they come.

Airlines, delivery services, the post office, and just about any businesses that move things welcome the discovery of a more efficient route. It’s worth a lot of money to them. How about yourself? If you travel, wouldn’t it be worthwhile to find faster routes?

An interesting application that finds the shortest routes, not by using factorials, but by applying other means, is Automap, from Automap, Inc., Phoenix, AZ, (602) 893-2400. The Automap program contains road information for the entire U.S. and can find either the shotest route (within its database tables), the quiest route (by referencing other tables), or a mixture of routes. It can then display the routes as directions, or graphically on a map.

The program we’ll study does this very thing, albeit much, much simpler. Given a set of cities, it will find the shortest path that makes a complete tour (returning to the starting city). Of course, this is a small program, designed to demonstrate the method behind the code, but with modification, perhaps it could shave some time off of your daily commute.

Make no mistake, this is not a trivial problem. Much research is directed to discovering better solutions faster. Why is it so hard? Because while there may be billions of routes, there is only one shortest route. For N cities, there exist (N-1)! routes. (There’s that factorial again!)

Where did that formula come from? Let’s say you’ve got to establish a route that visits five citites. Pick a city to begin at; any one will do, since the route will end up at the point of origin. Now, you’ve got four choices for the next city on the route. After you select one of those, you’ve got three cities left–then two–then only one, and then you return to the starting city. That’s where the factorial comes in. With five cities, we have 4*3*2*1 = 24 possible routes.

Cities             Routes
3                  2
4                  6
5                  24
6                  120
7                  840
8                  6,720
9                  60,480
10                 604,800
11                 6,652,800
12                 79,833,600

As you can see, the numbers start to get out of hand fast. This is known as exponential explosion and is the bane of some of the most interesting programs in computer science. (Chess-playing programs are another example of exponential explosion.) Even the fastest computer in the world cannot find the provable shortest path in a network of 50 cities. The program presented here has an upper practical limit of about 15 cities (on a fast PC), unless you want to let it run for a week or two.

Listing 3 presents the program written in Turbo C. If you have just a little experience, you can easily convert the source to Quick C. The only differences will be in the graphics calls. Build the program with the command line “TCC TRAVEL.C GRAPHICS.LIB.” Be certain that the appropriate BGI graphics driver is on your path.

THE ASSUMPTIONS TAKEN

This program makes a few assumptions. Graphically, it assumes an aspect ratio of 1:1 (100 units on the X-axis is the same distance as 100 units on the Y-axis). If you have a VGA display, this will be no problem, but if you have an EGA or other display, it may appear distorted.

For simplicity, it takes into account only the distance between two cities and assumes travel in a straight line in any direction. In real life, though, you usually cannot travel in a straight line, and there may be factors other than merely distance to determine the cost of traveling between two cities. These elements are not difficult to incorporate, but make the program more complex than an example should be, or has room to be.

The first thing that main() does is attempt to enter graphics mode. If that fails, it prints an error message and exits. Next, it sets the drawing mode to XOR[underscore]PUT. This effects duplicating a drawing operation, which becomes the equivalent of performing an erase. You’ll see how this is used in the Search() function.

Listing 2: C Factorial Loop Code

long Factorial (long i) { long Result; for (Result = 1; i > 0; i-) { Result *=i; } return (Result); }

Next, the programs determines the number of cities. The default is six, but a number can be passed on the command line. Technically, this program can handle up to 50 cities, yet you’ll grow very old before it finds a solution to even 30, so I recommend experimenting with just a few cities and working your way up (to the limit of your patience) from there.

Next, main() calls CreateRandom-Cities(), which builds the list of cities and draws each one as a little circle on the screen.

CreateRandomCities() also builds the mileage matrix that contains the distance between each city. The mileage matrix could be generalized into a “cost” matrix, which would take into account not only distance, but other factors such as road conditions, tolls, etc. This data (the city locations and the cost matrix) could be read from a “map” file for a real-world problem, rather than generated randomly.

After the cities are created, the Search() function is called to find the shortest path through the cities. Finally, the solution is displayed on the screen in DrawMinPath().

ENTER RECURSION

erThe heart of this program is the recursive Search() function. It takes three arguments: the next city to search, the current distance traveled, and the number of cities visited so far. Search() first makes a quick check to make sure it hasn’t already traveled further than the distance of the shortest route found so far. Without such a check, the program may end up wasting time on unproductive routes.

Next, it examines the keyboard to see if a key has been hit (which is the program’s fast alternative to rebooting), and then the current city is stored in the path. If Search() has made a complete route, it saves the current path in the minimum path array. Otherwise, Search() must continue by examining the remaining cities.

This is where recursion comes in beautifully, and transforms what would otherwise be a monster-sized program into a small set of code. If the city hasn’t been visited, the program flags it as such as draws a line between the current city and the next one on the screen. Then, it just Search()s it! Search() calls cits (recursion) and conveys to itself the new city to search, the current distance in the path, and the count of the number of cities visited so far. When it comes back from the search, it flags the city as unvisited and redraws the line. Remember that the graphics drawing mode is XOR [underscore] PUT, so this erases the line.

That’s all there is to it. Really! Recursion makes searching a path much simple (I wouldn’t want to do it any other way). There is room for improvement in this program, and you may enjoy enhancing its sophistication and its ability to handle even larger problems.

I can think of one improvement right off the bat. As written, the code blindly chooses the next city to search by simply going through the list and taking them in order. It would be much smarter to choose the next closest city instead. Another improvement would be to generate a reliable (lower-bound) estimate of the remaining distance to travel in an incomplete route in order to detect ahead of time that the route leads to a dead end.

Even the best programs on the fastest computers cannot completely solve much larger routes than this program can, so they use heuristics and other settle for “good” solutions rather than the optimum.

You may wish to experiment and comment-out the line-drawing code in the Search() function, since most of its time is spent just drawing lines. A great deal time time is spent in the kbhit() routine as well, so applying some method to check if less often would speed things up.

Good luck, and happy motoring.

No Comment.

Add Your Comment