🚀 go-pugleaf

In article <13DEC199216365553@cc.utah.edu> lallu@cc.utah.edu (Upmanu Lall, Civil Eng) writes:
>Does anyone know if this is a solved problem ?
> It seems like it ought to be.
>There are n arbitrary locations on the surface of the earth, each of which must
>be visited
>once and only once, starting from any one of them.
>At the end of the trip one is back at the starting point.
>It seems to me that the choice of the starting point does not matter,
>i.e. there is a unique shortest chain, and you should be able to find it
>irrespective of where you start on it.
>>?Is this assertion correct ?
>Is there an algorithm for determining the shortest path efficiently,
>and the second shortest, etc ?
>I recall from a network optimization class taken 2 decades ago, that
>a chain network is the dual problem to a flow network
>Can this be used to setup the problem such that one could
>establich whether the primal or the dual is easier to solve, and to then solve
>the problem ?
>Distances are Euclidean on the sphere (or the Earth). LAts and Longs of the
>points are known , and the number of locations is also known a priori (i.e.
>this is not a stochastic process).
>
>Any references, or suggestions to bodies of literature shall be appreciated.
>Determinitic  or Monte Carlo techniques would be fine.
>
>
>Thanks very much for your help
>Please respond to
>ulall@pub.uwrl.usu.edu

The problem you have described is called the "Traveling Salesman Problem".
It is a fairly well known problem in operations research and theoretical
computer science. There is a vast amount of literature on it.
You should be able to find references to it in a lot of textbooks on
O.R., algorithms, and perhaps other CS theory books.
The problem can come in different flavors. The one you described is
the symmetric traveling salesman. In the unsymmetric traveling
salesman problem the distance going from point A to point B may be
different from that going from point B to point A.

It is fairly well known that TSP is a hard problem. (It is called
NP-complete. In brief, it means if you can solve this problem
with an algorithm that runs in polynomial time, you will be able
to solve a large number of other difficult problems efficiently.
But so far, no human being has found such an algorithm (that runs
in polynomial time.)). Although no polynomial time algorithm is
known, a lot of heuristics and approximation solutions are known.
(I am not sure whether for the particular metic you have
described the problem is also NP-complete. I guess it is.)

If you post the question in the newsgroup "comp.theory", a lot of
people should be able to give you referenes on this problem.
I am not familiar with reference papers in research journals,
but my text book has mentioned some known (old) results for this
problem. If you need them, let me known.

Hope this helps.
Dicky Yan.