ltspsGreedyHeuristic.m

   1 function [route, totalDistance] = ltspsGreedyHeuristic (distanceMatrix, closestNeighbour)
   2 % ltsps-greedy
   3 % description: a greedy algorithm that usually finds decent solutions for
   4 % the TSP (travelling salesman problem) based on the closest (or optionally
   5 % the farthest) neighbour heuristic.
   6 % author: Laurens Van Houtven <lvh@laurensvh.be>
   7 % date: 28 Sep 2008
   8
   9 % Constants
  10 % Start at a random vertex?
  11 % if true: Pick a random vertex to start from.
  12 % if false: Start at the first vertex (ie order as given by distanceMatrix)
  13 RANDOM_START_VERTEX = 0;
  14
  15 if closestNeighbour==1
  16     CLOSEST_NEIGHBOUR_HEURISTIC=1;
  17 else
  18     CLOSEST_NEIGHBOUR_HEURISTIC=0;
  19 end
  20
  21 % Initialisation
  22 % How big is our set?
  23 matrixDims = size(distanceMatrix);
  24 setSize = matrixDims(2);
  25 % The route (vector of vertex indices). Preallocating means avoiding
  26 % in-looop growth. One city (the first one) occurs twice, hence n+1.
  27 route = zeros(1,setSize+1);
  28 % Unvisited cities. 1 if the city at that index is unvisited, 0 otherwise.
  29 unvisited = ones(setSize,1);
  30 % Route length
  31 totalDistance = 0;
  32 % What vertex do we start at?
  33 if (RANDOM_START_VERTEX)
  34         currentVertex = unidrnd(setSize);
  35 else
  36         currentVertex = 1;
  37 end
  38
  39
  40 for i = 1:(setSize)
  41     % Visit the city.
  42     unvisited(currentVertex) = 0;
  43
  44     % Add it to the route.
  45     route(i) = currentVertex;
  46
  47     % Get the source distance vector.
  48     % We assume that the distance matrix should be interpreted as follows:
  49     % rows   are where you're coming from (source)
  50     % colums are where you're going (destination)
  51     sourceDistances = distanceMatrix(currentVertex,:);
  52
  53     % Make the distances to nodes we've already visited zero.
  54     % unvisited is a column vector, sourceDistances is a row, it's slightly
  55     % more logical to have sourceDistances have the same dims as distances.
  56         distances = sourceDistances .* unvisited';
  57
  58     % Find index of the the closest city.
  59     if CLOSEST_NEIGHBOUR_HEURISTIC
  60         % Make the distances to each node we've already visited *really*
  61         % big. Motivation: interpret "distance" as "cost to get there", so
  62         % going back to a node where one has been already should be almost
  63         % infinitely expensive. In this case, the biggest real number
  64         % MATLAB knows about.
  65
  66             distances(distances==0)=realmax;
  67         [distance, distanceIndex] = min(distances); % closest
  68     else % FARTHEST_NEIGHBOUR_HEURISTIC
  69         [distance, distanceIndex] = max(distances); % farthest
  70     end
  71
  72     % Travel the distance to the next city.
  73     if distance ~= realmax
  74         totalDistance = totalDistance + distance;
  75     end
  76
  77         % Set the currentVertex to point to the next city.
  78         currentVertex = distanceIndex;
  79 end
  80
  81 % Make the route cyclic:
  82 route(end) = route(1);
  83
  84 end