summaryrefslogtreecommitdiff
path: root/tsp.py
diff options
context:
space:
mode:
authorGuillaume Seguin <guillaume@segu.in>2007-12-17 12:55:52 +0100
committerGuillaume Seguin <guillaume@segu.in>2007-12-17 12:55:52 +0100
commit6d1ea15cbff74e7acd461cf1d9571ccb944b6cc1 (patch)
tree348f80c3787fdead01ea9ef104532d8b3e2d5da7 /tsp.py
parentb28e2b83fa7541f764eb829daab47de48e9f999e (diff)
downloadtsp-6d1ea15cbff74e7acd461cf1d9571ccb944b6cc1.tar.gz
tsp-6d1ea15cbff74e7acd461cf1d9571ccb944b6cc1.tar.bz2
* Use simpler Greedy init and move the current one to "Greedy (Best)"
Diffstat (limited to 'tsp.py')
-rwxr-xr-xtsp.py21
1 files changed, 13 insertions, 8 deletions
diff --git a/tsp.py b/tsp.py
index 82e41c4..2bcc97c 100755
--- a/tsp.py
+++ b/tsp.py
@@ -45,12 +45,16 @@ CITY_RADIUS = 3 # Radius of the visual city points
SHOW_NAMES = True
-INITS = ["Random", "Greedy"] # Init methods choices
+INIT_RANDOM = "Random"
+INIT_GREEDY = "Greedy"
+INIT_GREEDY_BEST = "Greedy (Best)"
+
+INITS = [INIT_RANDOM, INIT_GREEDY, INIT_GREEDY_BEST] # Init methods choices
ALGOS = ["2opt", "Annealing"] # Algorithms choices
COUNTS = [10, 25, 50, 100, 250] # City counts choices
# Default settings
-DEFAULT_INIT = "Random"
+DEFAULT_INIT = INIT_RANDOM
DEFAULT_ALGO = "Annealing"
DEFAULT_COUNT = 50
@@ -327,17 +331,17 @@ class AlgoThread (threading.Thread):
algo = None
gui = None
canvas = None
- nearest = False
+ init = False
terminate = False
- def __init__ (self, context, algo, gui, canvas, use_nearest = False):
+ def __init__ (self, context, algo, gui, canvas, init = None):
'''Initialize the thread'''
threading.Thread.__init__ (self)
self.context = context
self.algo = algo
self.gui = gui
self.canvas = canvas
- self.nearest = use_nearest
+ self.init = init
def update_best (self, path):
'''Update GUI to reflect the finding of a better solution'''
@@ -354,13 +358,15 @@ the current settings) and run the algorithm on it until the stop () function
is called.'''
self.update_best (path = None)
best = None
- if self.nearest:
+ if self.init == INIT_GREEDY_BEST:
for i in self.context.map:
if self.terminate:
return
path = self.context.nearest_neighbours (start = i)
if not best or path.length < best.length:
best = path
+ elif self.init == INIT_GREEDY:
+ best = self.context.nearest_neighbours ()
else:
best = self.context.random_path ()
self.update_best (path = best)
@@ -527,9 +533,8 @@ class AlgoGui (gtk.Window):
self.stop ()
self.update_config ()
self.algo = eval ("Algo_%s" % self.get_algo ()) (self.context)
- use_nearest = self.init_box.get_active () == INITS.index ("Greedy")
self.thread = AlgoThread (self.context, self.algo, self, self.canvas,
- use_nearest = use_nearest)
+ init = self.get_init ())
self.thread.start ()
self.gen_button.set_sensitive (False)
self.start_button.set_sensitive (False)