Physics – Computational Physics
Scientific paper
2000-11-13
Physics
Computational Physics
Updated to: 10 pages, 7 figures, submitted to PRE Updated from: 7 pages, 7 figures
Scientific paper
We show that Stochastic Annealing can be successfully applied to gain new results on the Probabilistic Traveling Salesman Problem (PTSP). The probabilistic "traveling salesman" must decide on an a priori order in which to visit n cities (randomly distributed over a unit square) before learning that some cities can be omitted. We find the optimized average length of the pruned tour follows E(\bar{L}_{pruned}) = \sqrt{np} (0.872-0.105p) f(np) where p is the probability of a city needing to be visited, and f(np) -> 1 as np -> infinity. The average length of the a priori tour (before omitting any cities) is found to follow E(L_{a priori}) =\sqrt{n/p}\beta (p) where \beta (p)=1/(1.25-0.82 ln(p)) is measured for 0.05 < p < 0.6. Scaling arguments and indirect measurements suggest that \beta (p) tends towards a constant for p<0.03. Our stochastic annealing algorithm is based on limited sampling of the pruned tour lengths, exploiting the sampling error to provide the analogue of thermal fluctuations in simulated (thermal) annealing. The method has general application to the optimization of functions whose cost to evaluate rises with the precision required.
Ball Robin C.
Bowler Neill E.
Fink Thomas M.
No associations
LandOfFree
Characterisation of the probabilistic travelling salesman problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Characterisation of the probabilistic travelling salesman problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterisation of the probabilistic travelling salesman problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-381074