home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / stat / 2587 < prev    next >
Encoding:
Internet Message Format  |  1992-12-13  |  3.2 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!spool.mu.edu!yale.edu!not-for-mail
  2. From: yan-dicky@cs.yale.edu (Dicky Yan)
  3. Newsgroups: sci.math.stat
  4. Subject: Re: shortest chain on a sphere / shortest around the world trip
  5. Date: 13 Dec 1992 23:01:25 -0500
  6. Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
  7. Lines: 58
  8. Distribution: world
  9. Message-ID: <1gh0ulINNi9m@DOLPHIN.ZOO.CS.YALE.EDU>
  10. NNTP-Posting-Host: dolphin.zoo.cs.yale.edu
  11.  
  12. In article <13DEC199216365553@cc.utah.edu> lallu@cc.utah.edu (Upmanu Lall, Civil Eng) writes:
  13. >Does anyone know if this is a solved problem ?
  14. > It seems like it ought to be.
  15. >There are n arbitrary locations on the surface of the earth, each of which must
  16. >be visited
  17. >once and only once, starting from any one of them.
  18. >At the end of the trip one is back at the starting point.
  19. >It seems to me that the choice of the starting point does not matter,
  20. >i.e. there is a unique shortest chain, and you should be able to find it
  21. >irrespective of where you start on it.
  22. >>?Is this assertion correct ?
  23. >Is there an algorithm for determining the shortest path efficiently,
  24. >and the second shortest, etc ?
  25. >I recall from a network optimization class taken 2 decades ago, that
  26. >a chain network is the dual problem to a flow network
  27. >Can this be used to setup the problem such that one could
  28. >establich whether the primal or the dual is easier to solve, and to then solve
  29. >the problem ?
  30. >Distances are Euclidean on the sphere (or the Earth). LAts and Longs of the
  31. >points are known , and the number of locations is also known a priori (i.e.
  32. >this is not a stochastic process).
  33. >
  34. >Any references, or suggestions to bodies of literature shall be appreciated.
  35. >Determinitic  or Monte Carlo techniques would be fine.
  36. >
  37. >
  38. >Thanks very much for your help
  39. >Please respond to
  40. >ulall@pub.uwrl.usu.edu
  41.  
  42. The problem you have described is called the "Traveling Salesman Problem".
  43. It is a fairly well known problem in operations research and theoretical
  44. computer science. There is a vast amount of literature on it.
  45. You should be able to find references to it in a lot of textbooks on
  46. O.R., algorithms, and perhaps other CS theory books.
  47. The problem can come in different flavors. The one you described is
  48. the symmetric traveling salesman. In the unsymmetric traveling
  49. salesman problem the distance going from point A to point B may be
  50. different from that going from point B to point A.
  51.  
  52. It is fairly well known that TSP is a hard problem. (It is called
  53. NP-complete. In brief, it means if you can solve this problem
  54. with an algorithm that runs in polynomial time, you will be able
  55. to solve a large number of other difficult problems efficiently.
  56. But so far, no human being has found such an algorithm (that runs
  57. in polynomial time.)). Although no polynomial time algorithm is
  58. known, a lot of heuristics and approximation solutions are known.
  59. (I am not sure whether for the particular metic you have
  60. described the problem is also NP-complete. I guess it is.)
  61.  
  62. If you post the question in the newsgroup "comp.theory", a lot of
  63. people should be able to give you referenes on this problem.
  64. I am not familiar with reference papers in research journals,
  65. but my text book has mentioned some known (old) results for this
  66. problem. If you need them, let me known.
  67.  
  68. Hope this helps.
  69. Dicky Yan.
  70.