RadioBanter - View Single Post

August 6th 04, 06:29 AM

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