GetRoute

function Route = GetRoute( CityCoordinates )
%GETROUTE Calculates a short route between a large (> 10) number of cities.
%   This function tries to find a reasonably short route that can be used
%   as a starting point for other further optimized functions. The route is
%   computed by sort of implementing a nearest neighbour method, by looking for the nearest city and travelling to that, until
%   all cities are visited.
%
%   Input: CityCoordinates, a N-by-2 matrix containing the X and Y coordinates
%   as columns for N cities. Note that this excludes the first city since the
%   first city is located at (0,0) and all other coordinates are relative to
%   the first city. Either type out the matrix by hand or use the function
%   GetCities(N) to read out a textfile with city coordinates.
%
%   Output: Outputs a reasonable short route as a row vector.

% Notes on performance: This implementation is rather crude. It computes
% every route
%

tic; % Starts a timer to measure the execution time of the script

N = length(CityCoordinates) ;    % The number of cities, retrieved by reading matrix CityCoordinates
Route = ones(1,N+1);             % Pre-allocation of Route

% First look at your current position, inital value 1.
location = 1;
% Next look at which cities are nearby
nearbyCities = 2:N;

for (j=2:1:N)
% Now compute the distance to every allowable city
% Every city that is not 1 and has not yet been visited is allowable
% Visited cities are removed from the possibilities at the end of the first
% loop
neighbours = length(nearbyCities);
clear Trip; % Trip has to be cleared before each loop, it shrinks every loop since the number of possibilities d
    for (i=1:1:neighbours)
        nearbyCity = nearbyCities(i);
        Trip(i , 1:2) = [location, nearbyCity];
        Trip(i , 3) = CalculateDistance(CityCoordinates,location,nearbyCity);
    end

% We now have a matrix
[shortestDistance,ind] = min(Trip(:,3));
nearestCity = Trip(ind,2);
location = nearestCity;

% Now remove the city from the list of possibilities
indexToBeRemoved = find(nearbyCities==nearestCity);
nearbyCities( indexToBeRemoved ) = [];
Route(1,j) = nearestCity;
end
exetime = toc % Execution time in seconds
end