El problema del viatjant de comerç (traveling salesman problem) és un problema clàssic de l’algorísmica: es tracta de passar per una sèrie de punts, sense repetir-ne cap, i minimitzant la distància recorreguda. Fa unes poques setmanes vaig importar els arbres singulars de Barcelona a OpenStreetMaps, i crec que és una bona activitat didàctica per conèixer els arbres de la ciutat fer una ruta per uns quants d’aquests arbres.
Per fer-ho més interessant, podem plantejar-nos el problema de fer un recorregut que minimitzi la distància, passant per tots els arbres, i que retorni al punt de partida. Vaig estar cercant diferents implementacions amb Python que resolguin el problema, fins que en vaig trobar una que satisfeia la meva restricció de tornar al punt de partida.
Sobre aquesta solució he fet alguna modificació per tal de generar un fitxer JSON amb la solució. Finalment, hem de pintar sobre un mapa OSM els nostres punts (nodes); traçar una línia recta entre els punts; i afegir un label-text informatiu sobre aquests punts. El resultat es pot veure en la imatge.
Evidentment hem fet unes simplificacions: la distància mínima entre dos punts és la línia recta, però per la ciutat no podem anar en línia recta, i a més poden haver-hi pujades i baixades. Però com a exercici didàctic crec que és interessant.
Aquí Catalunya són populars les Curses d’Orientació. Crec que es podria aprofitar aquestes activitats en el lleure i afegir-hi una capa de coneixement, com ara conèixer els arbres, conèixer monuments, etc. Crec que per als joves i infants pot ser una activitat engrescadora.
Referències: