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.

3 次查看（过去 30 天）
Jacob Savona
Jacob Savona 2015-3-2
编辑： Jacob Savona 2015-3-3
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.

请先登录，再回答此问题。

回答（1 个）

Jacob Savona
Jacob Savona 2015-3-2
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.
  8 个评论
显示 6更早的评论
Jacob Savona
Jacob Savona 2015-3-3
编辑：Jacob Savona 2015-3-3
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

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Traveling Salesman (TSP) 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by