The following sections of this BookRags Literature Study Guide is offprint from Gale's For Students Series: Presenting Analysis, Context, and Criticism on Commonly Studied Works: Introduction, Author Biography, Plot Summary, Characters, Themes, Style, Historical Context, Critical Overview, Criticism and Critical Essays, Media Adaptations, Topics for Further Study, Compare & Contrast, What Do I Read Next?, For Further Study, and Sources.
(c)1998-2002; (c)2002 by Gale. Gale is an imprint of The Gale Group, Inc., a division of Thomson Learning, Inc. Gale and Design and Thomson Learning are trademarks used herein under license.
The following sections, if they exist, are offprint from Beacham's Encyclopedia of Popular Fiction: "Social Concerns", "Thematic Overview", "Techniques", "Literary Precedents", "Key Questions", "Related Titles", "Adaptations", "Related Web Sites". (c)1994-2005, by Walton Beacham.
The following sections, if they exist, are offprint from Beacham's Guide to Literature for Young Adults: "About the Author", "Overview", "Setting", "Literary Qualities", "Social Sensitivity", "Topics for Discussion", "Ideas for Reports and Papers". (c)1994-2005, by Walton Beacham.
All other sections in this Literature Study Guide are owned and copyrighted by BookRags, Inc.
Imagine that a salesman must travel to n cities and wants to take the shortest route possible. Assume that the salesman can start from any city on his itinerary and that the distance from city X to city Y is the same as the distance from Y to X (i.e., there exist no one-way shortcuts).
For small values of n, the traveling salesman problem (TSP) is simple. With three cities, for example, there is only one possible route; with four cities, three routes exist. Unfortunately, as the number of cities increases, the number of possible routes grows immensely. In general, for n cities, there exist ((n - 1)!) / 2 routes to consider. (The factorial (n - 1)! = (n - 1) ⋅ (n - 2) ⋅ ... ⋅ 3 ⋅ 2 ⋅ 1.) For a tour of nine cities, there are 20,160 different routes; for n = 15, the number of possible routes surpasses one trillion.
Although the traveling salesman problem has been solved for some large values of n, the best algorithm known to date is of order 2n, which means that the time required to solve the TSP grows exponentially with the size of the problem. For each 30 cities added to the salesman's route, the time required to solve the problem with today's algorithms increases by a factor of one billion, since 230 is approximately 109.
Since an exponential algorithm requires too much time to produce a precise answer to the TSP, one might instead turn to a heuristic or greedy algorithm. A heuristic is a rule or procedure that almost always delivers the right answer. Almost always won't be good enough in some circumstances, but in many occasions a fast, almost-certain-to-be-correct answer will be better than a slow, absolutely correct one.
The TSP is equivalent to a class of mathematical problems called N-P ("nondeterministic polynomial") complete problems, which are often used to create security features on computers and networks. No one has proved that a fast algorithm for the TSP, or N-P complete problems in general, doesn't exist, and in the unlikely event that one is discovered, alternative security measures would have to be put into place quickly.