ltspsRandomHeuristic.m

   1 function [route, distance] = ltspsRandomHeuristic (distanceMatrix)
   2 % ltspsRandomHeuristic
   3 % description: a heuristic tsp solver that picks random vertices
   4 % author: Laurens Van Houtven <lvh@laurensvh.be>
   5 % date: 28 Sep 2008
   6
   7 % What are the dimensions of the distance matrix? (or: # of cities?)
   8 matrixDims = size(distanceMatrix);
   9 % How many cities are there?
  10 nCities = matrixDims(2);
  11 % Preallocate the route.
  12 route = zeros(1,nCities+1);
  13 % Potential city candidates.
  14 source = 1:nCities;
  15
  16 for i = 1:nCities
  17     % How many cities do we still get to pick from?
  18     sourceSize = size(source);
  19     citiesLeft = sourceSize(2);
  20
  21     % Pick a random index.
  22     thisIndex = unidrnd(citiesLeft);
  23
  24     % Find the new city.
  25     newCity = source(thisIndex);
  26
  27     % Add it to the route.
  28     route(i) = newCity;
  29
  30     % Remove it from the pool of potential candidates.
  31     source = source(source ~= newCity);
  32 end
  33
  34 % Make the route cyclic
  35 route(end) = route(1);
  36
  37 distance = calculateRouteDistance(route, distanceMatrix);
  38
  39 end