home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / stat / 2585 < prev    next >
Encoding:
Text File  |  1992-12-13  |  1.7 KB  |  41 lines
  1. Newsgroups: sci.math.stat
  2. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!caen!hellgate.utah.edu!fcom.cc.utah.edu!cc.utah.edu!lallu
  3. From: lallu@cc.utah.edu (Upmanu Lall, Civil Eng)
  4. Subject: shortest chain on a sphere / shortest around the world trip
  5. Message-ID: <13DEC199216365553@cc.utah.edu>
  6. News-Software: VAX/VMS VNEWS 1.4-b1  
  7. Sender: news@fcom.cc.utah.edu
  8. Organization: University of Utah Computer Center
  9. Date: 13 Dec 1992 16:36 MST  
  10. Lines: 29
  11.  
  12.  
  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.