A traveling salesman wishes to make a number of sales calls in different
cities. Naturally he wants to spend as little time actually traveling as
possible (he is not paid for travel time).

He sets up the various cities he wants to visit and looks up the travel time
from each one to every other one. He writes a simple computer program to figure
out all of the possible routes and compare the total travel time in each route,
in order to find the fastest possible route. (The problem could also be worked
for minimum distance).

The program is written for any arbitrary number of cities. But the salesman
discovers that the program appears not to work for more than a certain number
of cities. Explain what the limit is and how it can be overcome.

73 de Jim, N2EY

This looks like a problem from Discrete Mathematics. To me it appears to be
a specific problem in finding what is called the minimum "Spanning Tree" for
a graph. For your problem the graph vertices would be the cities visited and
the distance, or what ever you want to minimize, assigned to the edges
connecting the vertices together.

Two known algorithms are used to find a set of edges connecting all the
vertices together that will minimize the item assigned to the edges as a
weight factor. The two algorithms are "Prim's" and Kruskal's". Their work
was done during the 1950's. At most (N-1) edges, where N is the total number
of edges in the graph, are selected during the course of the algorithm.
Nether algorithm has any limit on the size of the graph, vertices or number
of edges, that I can find.

(Robert Clay Prim born 1921 Swee****er Texas)
(Joseph Bernard Kruskal born 1928 New York city)

The book I have as a reference is:

Discrete Mathematics And Its Applications
(Third Edition 1995)
Published by McGraw Hill
By Kenneth H. Rosen
ISBN 0-07-053965-0

Look at pages 593 (section 8.6) to 598.

There are some older methods that use what is called "depth-first searches",
or "back tracking", and the other is called "breadth-first search". These
are covered under (section 8.5) pages 583 to 588.

The problem with writing code for graph transversals is two fold. The first
is keeping track of where you have been, and second is not getting stuck in
what is called a "cycle" or a loop in the graph. The way I've seen this done
is using recursive code while building a tree structure of the nodes
"visited", where each tree entry is for a graph node. The code starts at a
beginning node, or current node, then follows every path from the current
node to the next node if the path is not already listed in the tree entry
for the current node. The new path is entered in the path list for the
current node. If the path is already listed then it has already been
explored and should be skipped. If the next node is not in the tree then
enter it and make it the current node, other wise keep looking for another
path from the current node location to another node. If no more paths exists
from the current node then return to the previous node, making it the
current node, while marking the path as blocked. When no more paths exist to
explore at the current node then return to the previous node and explore the
next path not yet transversed. This procedure continues until either a path
to the destination node is found, or all nodes and paths have been explored.
Then doing a tree transversal "in order" looking for paths not marked as
blocked will generate a list of nodes and paths between nodes spanning from
the begining node to the destination node.

Graph theory is interesting and has a lot of practical applications in the
real world.

--
Leland C. Scott
KC8LDO

Wireless Network
Mobile computing
on the go brought
to you by Micro$oft

"N2EY" wrote in message
...
A traveling salesman wishes to make a number of sales calls in different
cities. Naturally he wants to spend as little time actually traveling as
possible (he is not paid for travel time).

He sets up the various cities he wants to visit and looks up the travel
time
from each one to every other one. He writes a simple computer program to
figure
out all of the possible routes and compare the total travel time in each
route,
in order to find the fastest possible route. (The problem could also be
worked
for minimum distance).

The program is written for any arbitrary number of cities. But the
salesman
discovers that the program appears not to work for more than a certain
number
of cities. Explain what the limit is and how it can be overcome.

73 de Jim, N2EY

nspam (WA3IYC) wrote in message ...
In article , "Leland C. Scott"
writes:

This looks like a problem from Discrete Mathematics. To me it appears to be
a specific problem in finding what is called the minimum "Spanning Tree" for
a graph. For your problem the graph vertices would be the cities visited and
the distance, or what ever you want to minimize, assigned to the edges
connecting the vertices together.

(snip of excellent discussion)

Yep, that's it!

Two properties emerge from the problem that are of interest in the discussion
with Steve, K4YZ:

First, it can be shown that the only way to find the minimal-length solution
for all possible values of intercity distance/time is to look at each and every
possible unique route. (You can eliminate half the routes as being identical
except for direction, which is immaterial if all you want is minimum distance
or time)

Second, the number of possible routes grows as factorially.

Third (and this is the point of the exercise) the number of routes with even a
moderate number of cities is so enormous that they cannot all be evaluated in a
'reasonable' time, even with the most powerful computing system imaginable.
This means there *is* an answer, but we cannot find it.

Example: With 10 cities, the number of routes is 3,628,800. Half of that is
1,814,400. A trivial computation for a computer.

But look at 60 cities: 4.16 x 10e81 routes! If we have a computer capable of
10e10 routes per second, it takes 4.16 x 10e71 seconds to find the solution.
Since there are approximately 31 million seconds in a year, (3.1 x 10e7) the
result is over 10e64 years! If we massively parallel 10e10 computers, the
solution still takes 10e54 years.

73 de Jim, N2EY

Splendid example of why Corporate America is wont to keep it's
incurable geeks bottled up in back rooms and as far away from
customers as possible and deploy their BusAd sales and marketing
professionals out into the the field do the peddling.

w3rv