ltspsEnumerativeSolver.m

   1 function [bestRoute, bestLength] = ltspsEnumerativeSolver (distanceMatrix)
   2 matrixDims = size(distanceMatrix);
   3 numCities = matrixDims(1,1);
   4
   5 % Initialisations
   6 % Shortest route until now and its length
   7 bestRoute = zeros(1,numCities+1);
   8 bestLength = realmax;
   9
  10 permutations = perms(2:numCities);
  11
  12 % This matrix has:
  13 %  * (n-1)! rows (the permutations, minus the one for the first vertex)
  14 %  * (n-1)  cols (the number of cities, minus the one for the first vertex)
  15
  16 rowLimit = factorial(numCities-1);
  17 colLimit = numCities-1;
  18
  19 for i = 1:rowLimit
  20     % Get the permutation (= the route minus the first and last vertex)
  21     thisRoute = permutations(i,1:colLimit);
  22
  23     currentCity     = 1;
  24     currentDistance = 0;
  25
  26     % While there are still cities to travel to...
  27     for j = 1:colLimit
  28         % Find the new distance and travel it.
  29         newDistance = distanceMatrix(currentCity,thisRoute(1,j));
  30         currentDistance = currentDistance + newDistance;
  31
  32         % Place yourself in the next city.
  33         currentCity = thisRoute(1,j);
  34     end
  35
  36     % Finally, travel fron this city to the start vertex (1).
  37     currentDistance = currentDistance + distanceMatrix(currentCity,1);
  38
  39     if currentDistance < bestLength
  40         bestLength = currentDistance;
  41         bestRoute = [1 thisRoute 1];
  42     end
  43 end
  44
  45 end