I have a Traveling Salesman Problem, but I don't know how to do it...I'm just gonna post the question and see who wants to answer. I understand if you don't want to.

Here is how it will work. I am providing a script called HW6 on Moodle. In it, you will see that I define a matrix called “coord” that has the x and y coordinates of N cities (coord is sized Nx2). Some sample values are provided for N=5. The first row of coord is the location of city 1, the second row is city 2, and so on. So a route that went in order would be [1 2 3 4 5 1]. Your job is to write a function (mine is called tsp_mal)that has coord as an input, and three outputs [D_min,route_min,Dist], which are: the minimum distance of all possible routes (ie the optimal route distance) which is a scalar, the corresponding optimal route(i.e. the order of cities visited) which is a vector of size [1,N+1],and the distance of all possible routes which is a vector of size [(N-1)!,1]. Your function should be general and run for any number of cities defined by the coord matrix, although in the instructions below I will show you the results for the sample coordinates with N=5. Your function should do the following major steps. I recommend writing your function with clearly defined sections using %% to separate the section so that it is easy to grade.

1 – Using the city coordinates, which are the input to the function, create a distance matrix, an NxN matrix in which each element is the distance between two cities. So for example, the (1,2) element is the distance between city 1 and 2, the (3,5) element is the distance between cities 3 and 5, etc. The diagonal of this matrix will be all 0’s (distance from city 1 to 1 is 0), and it is a symmetric matrix (distance from city 2 to 4 is the same as 4 to 2). Use for loop(s) to create this matrix. Remember, it should work for any input coordinates.

2– Create a route permutation matrix. This matrix contains all possible routes, with each row being a particular route, e.g. 1 2 4 3 5 1. Remember that every route must start at 1 and end at 1, and that the TS may only visit a city once on a given route. Before doing this section, remind yourself how many routes are possible (described above). This step can be completed relatively easily using the “perms”command (which has nothing to do with hair).

3 – Using the distance matrix and the permutation matrix, use for loop(s) to calculate a column vector of the distances of each route.

4 – Determine the minimum distance and the optimal route among all possible routes and associated distances. For our example, these are D_min = 1.4537e+03, and route = [1 5 2 3 4 1].

5 – Plot the x-y coordinate location of each city using black asterix’s. On the same plot, plot the optimal route, which is just a series of lines connecting the cities in order of the optimal route.

6 – On a new figure, plot the distance of each route using red circles. Set the lower limit of the y-axis to 0.

7 - Once you are done, test out your function with other coordinates and number of cities. In the HW6.m file, you can comment out the given coordinates and uncomment the next section to generate an arbitrary number of random cities. Try this out for different values of N. In a comment at the bottom of your function, discuss how the computation time varies versus N. Also discuss now the number of routes varies. Is there an upper limit to the value of N that is realistic for your code and computer?

Provided code:

%%have this section uncommented to compare to my answers
% coordx = [0 100 200 100 -200]'; % x coordinate of cities
% coordy = [0 0 100 200 -400]'; % y coordinates of cities

%%havre this section uncommented to try different random configurations and number of cities. 
N = 12;
coordx = round(1000*rand(N,1))-500; % x coordinate of cities
coordy = round(1000*rand(N,1))-500; % y coordinates of cities
coord = [coordx coordy]; % x-y coordinates of N cities

Just putting this out there in case anyone wants to try/help. Thanks.

[John D'Errico]

But please don't post 5 different questions on the subject of every individual homework assignment you get. Just update this one if you feel the need.

Answer 1

[Jacob Savona]

I almost have the first question.

function [D_min,route_min,Dist] = TSP_JAS(coord)
%%Question 1
[m n]=size(coord);
n=m;
Dist = zeros(m,n);
for j = 1:m
    for k = 1:n
        Dist(j,k) = sqrt((coord(j,1)+coord(i,1))^2 + (coord(j,2)+coord(i,2))^2);
    end
end
Dist

%The Dist(j,k) = sqrt((coord(j,1)+coord(i,1))^2 + (coord(j,2)+coord(i,2))^2); has an error message: Subscript indices must either be real positive integers or logicals.

[Jacob Savona]

Here is my code so far:

function [D_min,route_min,Dist] = TSP_JAS(coordz)
N = 5;
coordx = round(1000*rand(N,1))-500; % x coordinate of cities
coordy = round(1000*rand(N,1))-500; % y coordinates of cities
coord = [coordx coordy]; % x-y coordinates of N cities

%%Question 1
[m n]=size(coord);
n=m;
Dist = zeros(m,n);
for j = 1:m
    for k = 1:n
        Dist(j,k) = sqrt((coord(j,1)-coord(k,1))^2 + (coord(j,2)-coord(k,2))^2);
    end
end
Dist
%%Question 2
N=5;
P = perms(1:N);
r=factorial(N);
g=1;
while g<2
    city1 = P(g,1);
    if city1~=1
    P(g,:)=[];
    g=0;
    end 
    g=g+1;
end
P(:,N)=1

And it works from there, just a little stumped on question 3. Will post soon...

[Jacob Savona]

Here's code for Question 3:

%%Question 3
s=factorial((N-1));
b=zeros(s,1);
for h=1:s
    for q=1:N-1
        kk=[h,N-(N-q)];
        q=q+1;
        ww=[h,N-(N-q)];
        u=Dist(kk,ww);
        b(h,1)=u;
    end
end
b

Comes up with Error message: Subscripted assignment dimension mismatch b(h,1)=u;

[Jacob Savona]

Fixed Question 3:

%%Question 3
s=factorial((N-1));
Dist=zeros(s,1);
for h=1:s
    for q=1:N-1
        kk=R(h,N-(N-q));
        q=q+1;
        ww=R(h,N-(N-q));
        u=D(kk,ww);

      end
      Dist(h)=u;
  end
  Dist

[Jacob Savona]

I have a code for question 4:

%%Question 4
D_min= min(Dist);
route_min=zeros(1,N);
for f=1:s
    o=find(Dist(f)== D_min);
end
route_min(1,:)=R(o,:);

But there is an error: Improper assignment with rectangular empty matrix: route_min(1,:)=R(o,:);

[Jacob Savona]

In my new code I did define R. Here is my new code up though Question 4:

function [D_min,route_min,Dist] = TSP_JAS(coordz)
N = 5;
coordx = round(1000*rand(N,1))-500; % x coordinate of cities
coordy = round(1000*rand(N,1))-500; % y coordinates of cities
coord = [coordx coordy]; % x-y coordinates of N cities

%%Question 1
[m n]=size(coord);
n=m;
D = zeros(m,n);
for j = 1:m
    for k = 1:n
        D(j,k) = sqrt((coord(j,1)-coord(k,1))^2 + (coord(j,2)-coord(k,2))^2);
    end
end
D
%%Question 2
N=5;
R = perms(1:N);
r=factorial(N);
g=1;
while g<2
    city1 = R(g,1);
    if city1~=1
    R(g,:)=[];
    g=0;
    end 
    g=g+1;
end
R(:,N)=1
%%Question 3
s=factorial((N-1));
Dist=zeros(s,1);
for h=1:s
    for q=1:N-1
        kk=R(h,N-(N-q));
        q=q+1;
        ww=R(h,N-(N-q));
        u=D(kk,ww);

      end
      Dist(h)=u;
  end
  Dist
  %%Question 4
  D_min= min(Dist)
  route_min=zeros(1,N);
  for f=1:s
      o=find(Dist==D_min);
      y=min(o);
  end
  route_min(1,:)=R(y,:)

The part of question 5 I don't understand is how to connect the coordinates as the shortest route.

[Jacob Savona]

I understand how to connect them, but could you give an example of how to connect them in a certain order? The order of the shortest route changes each time, which is what gets me.

[Jacob Savona]

I'm sorry. I still don't follow what you are doing...

[Jacob Savona]

For the first plot just the standard

figure
plot(coordx,coordy,'k-*')

because I don't know how to approach it.

For the second(plot number route(route 1, route 2, etc..) vs. its distance.

%%Question 6
s=factorial((N-1));
figure
for hh=1:s 
    ll=Dist(hh,1);
    plot(hh,ll,'ro');
end

but that isn't plotting correctly