From 97d2c93a87fc1b351eec678e16eb8c2ba1edd600 Mon Sep 17 00:00:00 2001
From: Laurens Van Houtven <lvh@laurensvh.be>
Date: Thu, 9 Oct 2008 20:52:15 +0200
Subject: [PATCH] Bugfix + new feature

You can now create random asymmetric distance matrices.

The enumerative solver always used 1 as a first vertex. This meant it
wasn't always entirely enumerative, and sometimes generated suboptimal
solutions. Currently the first vertex is also permuted. This means the
algorithm has one extra city to permute, and as such is slower -- this
is because the first one cut corners, not because this one is
inefficient.

On branch master

Changes to be committed:

	modified:   generateRandomCoordMatrix.m
	new file:   generateRandomDistanceMatrix.m
	modified:   ltspsEnumerativeSolver.m
---
 generateRandomCoordMatrix.m    |  3 +++
 generateRandomDistanceMatrix.m | 21 +++++++++++++++++++++
 ltspsEnumerativeSolver.m       | 16 ++++++++--------
 3 files changed, 32 insertions(+), 8 deletions(-)
 create mode 100644 generateRandomDistanceMatrix.m

diff --git a/generateRandomCoordMatrix.m b/generateRandomCoordMatrix.m
index 0a91d61..c9e4b61 100644
--- a/generateRandomCoordMatrix.m
+++ b/generateRandomCoordMatrix.m
@@ -1,4 +1,7 @@
 function coordMatrix = generateRandomCoordMatrix(n, max)
+    % generateRandomCoordMatrix
+    % description: Generates a random coordinate matrix.
+    % date: 8 Oct 2008
     coordMatrix = zeros(n,3);
     
     for i=1:n
diff --git a/generateRandomDistanceMatrix.m b/generateRandomDistanceMatrix.m
new file mode 100644
index 0000000..028822f
--- /dev/null
+++ b/generateRandomDistanceMatrix.m
@@ -0,0 +1,21 @@
+function distanceMatrix = generateRandomDistanceMatrix(coordMatrix,max)
+    % generateRandomDistanceMatrix
+    % description: Generates an asymmetrical distance matrix based on a
+    % coordinate matrix.
+    % date: 8 Oct 2008
+    
+    n = size(coordMatrix,1);
+    distanceMatrix = zeros(n,n);
+    
+    for i=1:n
+        for j=1:n
+            d = unidrnd(max);
+            
+            if j == i
+                distanceMatrix(i,j) = 0;
+            else
+                distanceMatrix(i,j) = d;
+            end
+        end
+    end
+end
\ No newline at end of file
diff --git a/ltspsEnumerativeSolver.m b/ltspsEnumerativeSolver.m
index 2f78147..eff2201 100644
--- a/ltspsEnumerativeSolver.m
+++ b/ltspsEnumerativeSolver.m
@@ -7,20 +7,20 @@ numCities = matrixDims(1,1);
 bestRoute = zeros(1,numCities+1);
 bestLength = realmax; 
 
-permutations = perms(2:numCities);
+permutations = perms(1:numCities);
 
 % This matrix has:
-%  * (n-1)! rows (the permutations, minus the one for the first vertex)
-%  * (n-1)  cols (the number of cities, minus the one for the first vertex)
+%  * n! rows (the permutations, minus the one for the first vertex)
+%  * n  cols (the number of cities, minus the one for the first vertex)
 
-rowLimit = factorial(numCities-1);
-colLimit = numCities-1;
+rowLimit = factorial(numCities);
+colLimit = numCities;
 
 for i = 1:rowLimit
     % Get the permutation (= the route minus the first and last vertex)
     thisRoute = permutations(i,1:colLimit);
     
-    currentCity     = 1;
+    currentCity     = thisRoute(1);
     currentDistance = 0;
     
     % While there are still cities to travel to...
@@ -34,11 +34,11 @@ for i = 1:rowLimit
     end
     
     % Finally, travel fron this city to the start vertex (1).
-    currentDistance = currentDistance + distanceMatrix(currentCity,1);
+    currentDistance = currentDistance + distanceMatrix(currentCity,thisRoute(1));
     
     if currentDistance < bestLength
         bestLength = currentDistance;
-        bestRoute = [1 thisRoute 1];
+        bestRoute = [thisRoute thisRoute(1)];
     end
 end
 
-- 
2.11.4.GIT