|
In this installment you will start by conducting an experiment. (I really want you to do this.) Take a clean piece of paper, about half of an 8 1/2 by 11, and place it on a table in front of you. Now, with a pen or pencil, and with your eyes shut, make twenty “x” marks on the paper in random locations. It helps for you to turn the paper as you do this to make sure you are not placing the marks in any particular pattern. Now open you eyes, and with a pen or pencil, connect all of the marks without your pen leaving the paper, in a single line that you believe represents the shortest line that will connect all of the marks. You will probably end up with something that looks like a constellation. Every time I do this, it ends up looking like a dog drawn by James Thurber. Easy enough. Now write a computer algorithm that will connect the dots in the shortest possible path, just as you have done. That will not be so easy. The problem that you solved is well known in mathematical circles as the “Traveling Salesman Problem,” or TSP. mathematically, the problem is only solved when you have tested all possible paths and found one to be the shortest. How many paths are there? With twenty marks, after you start anywhere you choose, you will then have 19 marks choose from, then 18 and so on. Let’s see: 19 times 18 times 17 ... that is 19 factorial, and that total is 1.2 times 10 to the 17th power. Now if we add just one more mark, that number increases by a twenty times, to 2.4 times ten to the 18th power. Why bother to look at all possible paths? To a mathematician, that is the only way of knowing for sure that you have found the absolute best. Your eyeball solution, while it may be a good one, is not necessarily the best one mathematically until you have proven that there is none better. Mathematicians are not stupid, of course. For example, they hold conferences on just the solution to this problem, allowing professors of mathematics a chance to travel at school expense to interesting destinations around the world. And furthermore, mathematicians can create computer solutions that can solve the problem, exactly, without searching the whole set of possibilities. But as the problems get larger, the cost of the exact solution eventually grows unreasonably, because the factorial function is one of the fastest increasing functions that there is. There are two reasons why your eyeball solution is so much easier: The computer processes the information as a collection of numbers using mathematical and logical operations. Using symbols like 0 and 1 it makes images out of symbols. By contrast, the mind processes images directly, and makes symbols out of images. The mind, working with images, is able to process visual information faster than a computer. For example, I’ll bet that your diagram has no lines that cross. It was easy for you to do it that way, and by doing this, you automatically eliminated a very large percentage of solutions that are sub-optimal. But the imaging power of the mind doesn’t stop there. The mind can actually process visual information in more than two dimensions, for example, by imagining the operation of a teeter-totter, or the operation of a clock, or of a train wreck, or in Einstein’s case, the process of light traveling through space. It can even process the possible interaction between individuals in a social situation, including what someone might say, or more subtly, how someone might feel. This ability to process this kind of multidimensional information is what a computer can not do ... today. But even with this image-oriented problem there are times when the computer beats the human. Take our Traveling Salesman Problem and add the following. Consider that there is time spent traveling between any pair of marks. Some must be visited between certain hours of the day. Some connections may be only one-way and some points may have to be visited before others. Sound familiar? This is the problem for routing the UPS truck on a typical daily route. With these limits and time constraints, it is not a solution that can easily be solved by just looking at a map. Computers can and do solve these problems faster and better than humans. The ability to solve them can give one delivery company a competitive advantage over another by offering customers more choices when the pick-up or delivery will occur. Or, suppose the marks exist in three dimensions, like stars in the sky. Even with the mind’s ability to visualize in three dimentions, the eyeball method would have limits visualizing a shortest path as would be seen in a two-dimensional representation. Also, we were not demanding that you prove that your solution was exactly the best. We were seeking a good solution, but not the mathematically perfect or exact solution. As we learned in the poker game, sometimes good enough is, well, good enough. Which brings up the old joke: Two campers look out of their tent and see an angry bear. Fearing that they are going to have to run for it, one camper starts to put on his running shoes. The other camper says “No use doing that; even with your running shoes you can’t outrun the bear.” The other camper replies “I don’t have to outrun the bear. I only have to outrun you.” If one is looking for a good solution, the Traveling Salesman Problem can be solved by computer easily enough using the swapping technique that was used finding the magic square. The path to be followed consists of a list of points to be visited in order. Swapping any two points on the path creates a new path that is either better or poorer than the one before. If it is better, keep the swap; otherwise, restore to the previous path and swap another pair. This method does not care about path limits or time constraints if they are built into the evaluation algorithm. A simple-minded solution, indeed, but it finds a good path. Several tricks may be employed to help it find a good solution faster, but these tricks use knowledge about the specific problem being solved. What is interesting is that in its pure form, that is without any tricks, the swap and test algorithm actually works. It is fun to see the process in operation on the computer screen. Starting with a path that consists of a completely random connection of points, the screen shows a mess of straight lines, like a dropped pile of pick-up sticks. As the process continues, the mess magically straighten itself out, into a neat and organized pattern. Sometimes it looks like a dog. In this example, we looked at two sides of a fence that separates human from machine creativity: On the human side, processing image information is a uniquely human capability. Dealing with overwhelming complexity and huge numbers of options is the realm of the computer. What remains consistent between the two approaches is the key ingredient — a quick and effective evaluation method. As you proved to yourself, the evaluation method can be a visual process as well as an arithmetic one. |
|
Richard Ten Dyke, a member of the Danbury Area Computer Society, has previously contributed to this newsletter on the topic of Digital Photography. He is retired from IBM and can be reached at tendyke@bedfordny.com. All opinions are his own, and he welcomes comments. |
|