Vai al contenuto

Calcoli scientifici con Julia/Commesso viaggiatore

Wikibooks, manuali e libri di testo liberi.
Indice del libro

Nel problema del commesso viaggiatore dato un insieme di città, e note le distanze tra ciascuna coppia di esse, bisogna trovare il tragitto di minima percorrenza che il commesso deve seguire per visitare tutte le città una ed una sola volta e ritornare alla città di partenza. Per risolvere il problema con Julia innanzitutto occorre scaricare le coordinate geografiche (latitudine, longitudine) delle città che si vogliono visitare.
In Google Maps cercare la città o il luogo da visitare. Cliccare su di essa col tasto destro del mouse e poi sulle coordinate geografiche che verrano copiate negli appunti in modo da incollarle nel codice:

city_coordinates = [
    [38.12044401205735, 13.344912286949409], # Palermo
    [37.50787101641852, 15.080264582092187],# Catania
    [37.07558088824639, 15.286173206794285], # Siracusa
    [37.3084415245004, 13.585830724530107],  # Agrigento
    [38.016020896565806, 12.535508424272644], # Trapani
    [38.19149527666429, 15.558410966147036], # Messina
    ]

Creare una funzione per convertire le coordinate geografiche in cartesiane secondo una formula approssimativa trovata in rete :

function to_euclidean_coordinates(lat, lon)
    R = 6371000
    x = R * cos(lat) * cos(lon)
    y= R * cos(lat) * sin(lon)
    return [x, y]
end

Convertire le coordinate geografiche in cartesiane :

cities =[]

for coord in city_coordinates
    push!(cities,to_euclidean_coordinates(coord[1],coord[2]))
end

println(cities)
Any[[4.1390843138109976e6, 4.082710768009927e6], [-5.062558793864646e6, 3.673371982848222e6], [-4.7188196445483435e6, 2.117434951611853e6], [3.08584312433141e6, 5.018078076055259e6], [6.050861735871778e6, -186802.1569603486], [-5.551514153391771e6, 836487.2998629898]]

Installare le librerie TravelingSalesmanExact e GLPK di Julia e calcolare il giro ottimale del commesso viaggiatore:

using TravelingSalesmanExact, GLPK
set_default_optimizer!(GLPK.Optimizer)
tour, cost = get_optimal_tour(cities, distance=TravelingSalesmanExact.euclidean_distance)
plot_cities(cities[tour])

Visualizzare il giro ottimale :

citta = ["Palermo","Catania","Siracusa","Agrigento","Trapani","Messina"]

for c in tour
   println(citta[c]) 
end
Trapani
Palermo
Agrigento
Catania
Siracusa
Messina