RE: "Elastic string" (type of traveling-salesman) paradigm for sampling discrete data sets
- To: mathgroup at smc.vnet.net
- Subject: [mg78206] RE: [mg78198] "Elastic string" (type of traveling-salesman) paradigm for sampling discrete data sets
- From: "King, Peter R" <peter.king at imperial.ac.uk>
- Date: Tue, 26 Jun 2007 04:06:40 -0400 (EDT)
There is a problem known as the probabilistic travelling salesman problem introduced by Jaillet (Operations Research vol 36 pp929-936, 1988) where the challeng is to find the optimal path when you have to visit each city with a probability p. I don't know if this is of any help to you. There is a modified kind of simulated annealing strategy for solving this (I'm sure there are others as well but I don't know them) devised by Fink and Ball (Physical Review E 68, 036703 (2003) & Physical Review Letters 91, 030201 (2003)). Thse refs should give the algorithm. I hope this helps, Peter > -----Original Message----- > From: Curtis Osterhoudt [mailto:cfo at lanl.gov] > Sent: 25 June 2007 12:08 > To: mathgroup at smc.vnet.net > Subject: [mg78198] "Elastic string" (type of > traveling-salesman) paradigm for sampling discrete data sets > > Dear MathGroup, > > This is a question which might open up far more cans of > worms than I'd like, but it has got me thinking, and I can > always use help with that. > Forgive the length of the post! > > I'm writing some code (in Mathematica) to calculate the fractal > dimension(s) of nominally 1D datasets; an example would be > discretely-sampled {time, single_coordinate} sets. This > brings me to my first question: other than the simple > approach described in "The Fractal Dimension of the Blues" > notebook[1], are there relatively accessible Mathematica > codes out there already? > > Regardless of the answer to the first question, I've another. > One way in which to sample a discrete data set (or even a > continuous function) is to imagine an elastic string > stretched between the first and last data points. Then, > specify how many (straight) sections the string is allowed to > be deformed in. > For just one section, the string just goes straight from the > first to the last point. For two sections, the string goes > from the first point, to somewhere on the dataset, and then > from there to the last point. > The "elastic" part of the wording is to imply that the > string's length is required to be the shortest possible, > passing through the first, last, and any intermediate > sampling points. (The possibility of allowing for > interpolation between data points causes massive > problems---at least in my mind---as to how sample things > correctly, so I'll leave that concept aside for the moment.) > This is a sort of "free" traveling-salesman problem, with the > salesman picking and choosing a set number of points to visit > between the first and last. > I'm imagining a rather icky optimization problem > (especially for large datasets), and wonder if anyone has > some hints or suggestions as to how to make relatively quick > code. I'm totally open to the spewing-forth of ideas, whether > or not they're very carefully considered. > As a first guess at the algorithm, I can fix the first and > last points of the string, then run a "bead" affixed to the > string along each of the remaining points, and see which one > ends up minimizing the string length (obviously a point > between the first and last points in both dimensions, _if_ > the sampled data allows for such a thing). As more points are > allowed to be sampled, it's almost certain that > previously-affixed points will have to become unglued, and > attach themselves elsewhere. > > Any suggestions? This may be a common problem with some > famous and efficient solutions, but I'm not familiar with > them. Even some good websites or journal article suggestions > would be very welcome. > > Best wishes, > Curtis O. > > > > > [1] Available as > http://calcand.math.uiuc.edu/courseware/Old%20Stuff/Pictures_a > nd_Math_Fun/Fowler's%20Neat%20Graphics/13fracBluWRI.nb > -- > = ========================== ========================== ======== > Curtis Osterhoudt > cfo at remove_this.lanl.and_this.gov > PGP Key ID: 0x4DCA2A10 > Please avoid sending me Word or PowerPoint attachments See > http://www.gnu.org/philosophy/no-word-attachments.html > = ========================== ========================== ======== > >