MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
> =
==========================
==========================
========
>
>


  • Prev by Date: Re: Why use Java in Mathematica?
  • Next by Date: Re: A Note of Thanks
  • Previous by thread: Re: ColorSchemes Palette
  • Next by thread: Another Question on Style Sheets