home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 16813 < prev    next >
Encoding:
Text File  |  1992-12-13  |  1.7 KB  |  43 lines
  1. Newsgroups: sci.math
  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: <13DEC199216424426@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:42 MST  
  10. Lines: 31
  11.  
  12.  
  13.  
  14.  
  15. Does anyone know if this is a solved problem ?
  16.  It seems like it ought to be.
  17. There are n arbitrary locations on the surface of the earth, each of which must
  18. be visited
  19. once and only once, starting from any one of them.
  20. At the end of the trip one is back at the starting point.
  21. It seems to me that the choice of the starting point does not matter,
  22. i.e. there is a unique shortest chain, and you should be able to find it
  23. irrespective of where you start on it.
  24. Is this assertion correct ?
  25. Is there an algorithm for determining the shortest path efficiently,
  26. and the second shortest, etc ?
  27. I recall from a network optimization class taken 2 decades ago, that
  28. a chain network is the dual problem to a flow network
  29. Can this be used to setup the problem such that one could
  30. establich whether the primal or the dual is easier to solve, and to then solve
  31. the problem ?
  32. Distances are Euclidean on the sphere (or the Earth). LAts and Longs of the
  33. points are known , and the number of locations is also known a priori (i.e.
  34. this is not a stochastic process).
  35.  
  36. Any references, or suggestions to bodies of literature shall be appreciated.
  37. Deterministic  or Monte Carlo techniques would be fine.
  38.  
  39.  
  40. Thanks very much for your help
  41. Please respond to
  42. ulall@pub.uwrl.usu.edu 
  43.