summaryrefslogtreecommitdiff
path: root/tsp.py
diff options
context:
space:
mode:
authorGuillaume Seguin <guillaume@segu.in>2007-12-17 03:05:44 +0100
committerGuillaume Seguin <guillaume@segu.in>2007-12-17 03:05:44 +0100
commitf92251f0d3081b5ebf0c9e9497f236f5b1857e62 (patch)
tree6aa581bfee99dbcba1388b0bab0fe117f9a634f3 /tsp.py
parent89dc12dfefc692f0108abef4a13d0be4aab8bc8d (diff)
downloadtsp-f92251f0d3081b5ebf0c9e9497f236f5b1857e62.tar.gz
tsp-f92251f0d3081b5ebf0c9e9497f236f5b1857e62.tar.bz2
* Improve 2opt algorithm (don't enforce i to be lower than j)
Diffstat (limited to 'tsp.py')
-rwxr-xr-xtsp.py13
1 files changed, 9 insertions, 4 deletions
diff --git a/tsp.py b/tsp.py
index b6f702c..55278a8 100755
--- a/tsp.py
+++ b/tsp.py
@@ -219,10 +219,15 @@ class Algo_2opt (Algo):
best = path
def do_2opt (self, path):
- i, j = sorted (random.sample (path, 2))
- segment = path[i + 1:j]
- segment.reverse ()
- return Path (self.context, path[0:i + 1] + segment + path[j:])
+ i, j = random.sample (path, 2)
+ if i < j:
+ segment = path[i + 1:j]
+ segment.reverse ()
+ return Path (self.context, path[:i + 1] + segment + path[j:])
+ else:
+ segment = path[i + 1:] + path[:j]
+ segment.reverse ()
+ return Path (self.context, path[j:i + 1] + segment)
class AlgoThread (threading.Thread):