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(1:numCities);
  11
  12 % This matrix has:
  13 %  * n! rows (the permutations, minus the one for the first vertex)
  14 %  * n  cols (the number of cities, minus the one for the first vertex)
  15
  16 rowLimit = factorial(numCities);
  17 colLimit = numCities;
  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     = thisRoute(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     if currentDistance < bestLength
  37         bestLength = currentDistance;
  38         bestRoute = [thisRoute thisRoute(1)];
  39     end
  40 end
  41
  42 end