Project 1 - Traveling salesman problem

Travelling Salesman Problem

Project1.m

citypoints=20;
x=randi(100,citypoints,1);
y=randi(100,citypoints,1);
plot(x, y, 'bo', 'MarkerSize', 10);
title('Travelling Salesman Problem');
xlabel('x-distance from the city center(in km)');
ylabel('y-distance from the city center(in km)');
grid on;
% Compute the distance of each of the city points from origin(0, 0)
distances = sqrt(x.^ 2 + y.^ 2);
% Find the nearest one.
[minDistance, indexOfMin] = min(distances);
nearestX = x(indexOfMin);
nearestY = y(indexOfMin);
hold on;
plot(nearestX, nearestY, 'r*', 'MarkerSize', 8, 'LineWidth', 2);
line([0, nearestX], [0, nearestY], 'LineWidth', 2, 'Color', 'r');
% Go from that point to the nearest of the other points.
cityUsed = false(1, citypoints);
counter = 2;
maxIterations = citypoints;
cityUsed(indexOfMin) = true;
fprintf('The minimum distance path is:');
fprintf('(%d %d)-->',nearestX,nearestY);
while sum(cityUsed) <= (citypoints - 1) && (counter <= maxIterations)
previousx = x(indexOfMin(counter - 1));
previousy = y(indexOfMin(counter - 1));
x(cityUsed) = inf;
distances = sqrt((x - previousx) .^ 2 + (y - previousy) .^ 2);
[minDistance, indexOfMin(counter)] = min(distances);
nearestX = x(indexOfMin(counter));
nearestY = y(indexOfMin(counter));
line([previousx, nearestX], [previousy, nearestY], 'LineWidth', 2, 'Color', 'r');
cityUsed(indexOfMin(counter)) = true;
counter = counter + 1;
fprintf('(%d %d)-->',nearestX,nearestY);
end
print('Travelling sales man problem','-djpeg');

The minimum distance path is:(8 43)-->(26 43)-->(34 54)-->(50 46)-->(62 52)-->(56 62)-->(60 74)-->(52 82)-->(44 70)-->(20 70)-->(7 63)-->(40 35)-->(44 21)-->(89 16)-->(100 51)-->(94 57)-->(82 56)-->(83 73)-->(90 84)-->(89 97)-->