> From: Erik Reuter <[EMAIL PROTECTED]>
> On Tue, Nov 19, 2002 at 05:06:02AM -0600, The Fool wrote:
> > But the number of possible pathways between any two nodes is the
> > factorial. ^^^^^^^All
> By the way, I don't think even that is right.
>
> Consider three nodes, A,B,C.
>
> We have:
>
> {no connections}
> {AB}
> {AC}
> {BC}
> {AB,AC}
> {AB,BC}
> {AC,BC}
> {AB,AC,BC}
>
> for a total of 8, which is 2^3, not factorial.
Know ye not basic computer science P / NP problems?
--
Traveling salesman problem
>From Wikipedia, the free encyclopedia.
The traveling salesman problem (TSP) is a prominent illustration of a
class of problems in computational complexity theory. The problem can be
stated as: Given a number of cities and the costs of travelling from one
to the other, what is the cheapest roundtrip route that visits each city
exactly once and then returns to the starting city?
The most direct answer would be to try all the combinations and see which
one is cheapest, but given that the number of combinations is N! (the
factorial of the number of cities), this solution rapidly becomes
impractical.
How fast are the best known deterministic algorithms?
The problem has been shown to be NP-hard, and the decision version of it
("given the costs and a number x, decide whether there is a roundtrip
route cheaper than x") is NP-complete.
The problem is of considerable practical importance, and various
approximation algorithms, which "quickly" yield "good" solutions with
"high" probability, have been devised. An approximative solution for
15,112 cities in Germany was found in 2001 by Princeton University
scholars.
The first algorithm used to solve the traveling salesman problem is the
nearest neighbour algorithm, which is normally fairly close to the
optimal route, and doesn't take too long to execute. Upper and lower
bounds for the length of the optimal route can be found using the minimum
spanning tree of the network. Another algorithm is an insertion
algorithm, the Dakin Branch and Bound algorithm, which can be used to
process TSPs containing 40-60 cities. Yet another, progressive
improvement algorithm which uses techniques reminiscent of linear
programming works well up to 120-200 cities. Optimised Markov Chain
algorithms which utilise local searching heuristical sub-algorithms can
find a route extremely close to the optimal route for 700-800 cities.
However, the only way to be completely confident of finding the optimal
route is to check every route, which is completely impractical for TSPs
with more than 25-30 cities.
http://www.wikipedia.org/wiki/Traveling_salesman_problem
_______________________________________________
http://www.mccmedia.com/mailman/listinfo/brin-l
