summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGuillaume Seguin <guillaume@segu.in>2007-12-18 02:03:57 +0100
committerGuillaume Seguin <guillaume@segu.in>2007-12-18 02:03:57 +0100
commit8de4e77c4054978b06aef0bc51a8461bde67e2fd (patch)
tree47dd72c21f302ffa57d2c8dc0e73b746ccf1295d
parentfbbe4cf3710777bd394e201602f27b031f0abfeb (diff)
downloadtsp-8de4e77c4054978b06aef0bc51a8461bde67e2fd.tar.gz
tsp-8de4e77c4054978b06aef0bc51a8461bde67e2fd.tar.bz2
* Move Algo_MonteCarlo code-wise for consistency with the combo box
-rwxr-xr-xtsp.py58
1 files changed, 29 insertions, 29 deletions
diff --git a/tsp.py b/tsp.py
index 6bdc1e3..5c9b2cb 100755
--- a/tsp.py
+++ b/tsp.py
@@ -301,6 +301,35 @@ class Algo_2opt (Algo):
def do_2opt (self, path):
return self.random_reverse (path)
+class Algo_MonteCarlo (Algo_2opt):
+ '''2opt-based algorithm with Monte-Carlo perturbations'''
+
+ unsuccessful_loops = 0
+ MAX_UNSUCCESSFUL_LOOPS = 1000
+
+ def run (self, path = None):
+ '''Algorithm main loop'''
+ if not path:
+ path = self.context.nearest_neighbours_best ()
+ current = path
+ while True:
+ yield path
+ path = self.do_2opt (current)
+ if path.length < current.length:
+ current = path
+ self.unsuccessful_loops = 0
+ else:
+ '''If we did not find a better result, increment this'''
+ self.unsuccessful_loops += 1
+ '''After MAX_UNSUCCESSFUL_LOOPS, perturbate the current path'''
+ if self.unsuccessful_loops > self.MAX_UNSUCCESSFUL_LOOPS:
+ path = current = self.perturbate (current)
+ self.unsuccessful_loops = 0
+
+ def perturbate (self, path):
+ '''Perturbate a path by exchanging two points'''
+ return self.random_swap (path)
+
class Algo_Annealing (Algo_2opt):
'''Simulated annealing algorithm'''
@@ -344,35 +373,6 @@ based on the current number of iterations (or so)'''
'''Temperature law: t = t0 - accepted_updates * 0.001 (min'd to 0.1)'''
return max (self.t0 - self.updates * 0.001, 0.1)
-class Algo_MonteCarlo (Algo_2opt):
- '''2opt-based algorithm with Monte-Carlo perturbations'''
-
- unsuccessful_loops = 0
- MAX_UNSUCCESSFUL_LOOPS = 1000
-
- def run (self, path = None):
- '''Algorithm main loop'''
- if not path:
- path = self.context.nearest_neighbours_best ()
- current = path
- while True:
- yield path
- path = self.do_2opt (current)
- if path.length < current.length:
- current = path
- self.unsuccessful_loops = 0
- else:
- '''If we did not find a better result, increment this'''
- self.unsuccessful_loops += 1
- '''After MAX_UNSUCCESSFUL_LOOPS, perturbate the current path'''
- if self.unsuccessful_loops > self.MAX_UNSUCCESSFUL_LOOPS:
- path = current = self.perturbate (current)
- self.unsuccessful_loops = 0
-
- def perturbate (self, path):
- '''Perturbate a path by exchanging two points'''
- return self.random_swap (path)
-
class AlgoThread (threading.Thread):
'''Threading running a given algorithm'''