TSP nearest neighbor

nearest_neighbor.m

function [ path, cost ] = nearest_neighbor( start, map )
%NEAREST_NEIGHBOR Solves the traveling salesman problem using the nearest
%neighbor method

%% Preparation
if diff(size(map)) ~= 0
    error('The width and height of the Map has to be the same');
end

% Replace diagonal elements with infinite value so we don't stay in the
% same city all the time
map2=map;
map2(eye(size(map2))~=0) = inf;

%% Solution

n = length(map2);
path_data = zeros(n, 2);

% Set start index
current = start;

% Travel through n cities
for i=1:n,
    % Find nearest neighbor (smallest value)
    [v, c] = min(map2(current,:));
    % Check if the smallest value is infinite, that means we've been to every city
    if v == inf
        % Set the next city to start, so we return home
        c = start;
        % Get the path cost to get home from the original unchanged map variable
        v = map(current, c);
    end
    % Update path variable with path lengh and new city
    path_data(i, :) = [v, c];
    % Set the path cost from every city to the current city to infinite
    % so we don't come here again
    map2(:, current) = inf;
    % Set the next city index to the current
    current = c;
end

%% Output

path = path_data(:,2)';
cost = path_data(:,1)';

end

tsp.m

% Simple TSP solver which uses the nearest neighbor method.
% Note: If at one point there are two (ore more) paths with the lowest
% cost, the script just takes the first one and doesn't check the other
% paths.

close all;          % Closes all the open figure windows
closepreview;       % Close Video Preview window
clear;              % Removes all variables from the workspace
clc;                % Clears the command window and homes the cursor

%% Problem

% City names
cities = {'7', 'I', 'L', 'N', 'D', 'S', 'A', 'O', 'U', '0', 'P', 'B', '5', 'T'};

% List with path cost (should be symetrical)
map = [
    00, 02, 34, 13, 16, 20, 22, 30, 05, 83, 06, 08, 31, 22;
    02, 00, 50, 15, 30, 31, 12, 08, 25, 17, 19, 20, 86, 13;
    34, 50, 00, 42, 56, 35, 64, 65, 30, 10, 79, 81, 37, 39;
    13, 15, 42, 00, 13, 22, 23, 50, 40, 52, 17, 10, 29, 20;
    16, 30, 56, 13, 00, 09, 01, 62, 91, 70, 22, 14, 26, 07;
    20, 31, 35, 22, 09, 00, 18, 70, 25, 27, 16, 32, 31, 14;
    22, 12, 64, 23, 01, 18, 00, 73, 09, 20, 30, 03, 24, 86;
    30, 08, 65, 50, 62, 70, 73, 00, 53, 64, 67, 88, 70, 84;
    05, 25, 30, 40, 91, 25, 09, 53, 00, 92, 30, 21, 93, 15;
    83, 17, 10, 52, 70, 27, 20, 64, 92, 00, 30, 50, 20, 21;
    06, 19, 79, 17, 22, 16, 30, 67, 30, 30, 00, 84, 31, 16;
    08, 20, 81, 10, 14, 32, 03, 88, 21, 50, 84, 00, 35, 20;
    31, 86, 37, 29, 26, 31, 24, 70, 93, 20, 31, 35, 00, 40;
    22, 13, 39, 20, 07, 14, 86, 84, 15, 21, 16, 20, 40, 00];

%% Solution (All-Nearest-Neighbor)

% Find the nearest neighbor solution with the lowest cost
% (--> All-Nearest-Neighbor)
n = length(map);
path = zeros(1,n)+inf;
cost = zeros(1,n)+inf;
for i=1:n,
    [p, c] = nearest_neighbor( i, map );
    if sum(c) < sum(cost)
        path = p;
        cost = c;
    end
end

clearvars p c

%% Display

disp(['Path cost: ', num2str(sum(cost))]);

s = cell(1,n);
for i=1:n,
    s(i) = cities(path(i));
end
disp('Path:');
disp(s);

clearvars i n s