Trouble finding shortest possible distance between all points
10 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Hi,
I'm trying to find the shortest possible distance between these points, with the red dot being the start and finishing point.
I have two 14x1 arrays with each point's x and y position, and I already have a function to tell me how long a path of the points ordered in a certain way is, but I'm wondering if there's any way to automatically find the shortest possible distance?
Here's my code for context:
[location_data, location_names] = xlsread('exposure_sites.xlsx') ;
latitude_dms = location_data(:, 1:3);
longitude_dms = location_data(:, 4:6);
latitude_degrees = dms2degrees(latitude_dms) ;
longitude_degrees = dms2degrees(longitude_dms) ;
exposure_origin = [mean(latitude_degrees), mean(longitude_degrees)] ;
origin_x = exposure_origin(1,2) ;
origin_y = exposure_origin(1,1) ;
km_per_degree_latitude = 2 .* pi .* 6373.6 / 360 ;
km_per_degree_longitude = km_per_degree_latitude * cos((-27.4743) .* (pi/180)) ;
exposure_x = longitude_degrees * km_per_degree_longitude ;
exposure_y = latitude_degrees * km_per_degree_latitude ;
figure
plot(exposure_x, exposure_y, '.', MarkerSize = 15)
grid on
axis equal
xlabel('x-coordinates'), ylabel('y-coordinates'), title('Coronavirus Variant Exposure Sites')
text(exposure_x, exposure_y, location_names, 'VerticalAlignment', 'bottom')
box off
c = convhull(exposure_x, exposure_y)' ;
first_trip = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 1] ;
computeTripDistance([exposure_x exposure_y], first_trip) ;
axis([1.5095*10^4, 1.512*10^4, -3066, -3045])
trip_3 = ([1 4 8 10 5 3 7 2 13 11 9 14 12 6 1]) ;
computeTripDistance([exposure_x exposure_y], trip_3) ;
axis([1.5095*10^4, 1.512*10^4, -3066, -3045])
As you can see, I've gotten one that works pretty well but I'm wondering if anyone can get it lower? Sorry if this turned out to be more of a maths thing than a coding thing, I just wanted to give as much context as possible.
2 comentarios
jessupj
el 9 de Jun. de 2022
"I'm wondering if there's any way to automatically find the shortest possible distance."
This is a well known problem that's worth reading up on. https://en.wikipedia.org/wiki/Travelling_salesman_problem
Mathieu NOE
el 9 de Jun. de 2022
Editada: Mathieu NOE
el 9 de Jun. de 2022
yeap
there is already matlab ressources for the Travelling Salesman Problem (TSP)
and probably many more if you spend some time on the FileExchange section
Respuestas (0)
Ver también
Categorías
Más información sobre Traveling Salesman (TSP) en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!