Sapere Scienza

Sapere Scienza

Cammini minimi, ovvero come usare la matematica e vivere felici

di 

Siamo ormai letteralmente circondati dai navigatori per orientarci negli spostamenti: basati su ricevitori di segnali GPS (acronimo di Global Positioning System), questi strumenti ci consentono di individuare il percorso migliore per raggiungere la destinazione desiderata, sia essa la casa di un amico, un hotel, una pizzeria o un museo. Non tutti sanno però che l'ingrediente nascosto, ma fondamentale, dei navigatori è la matematica

 

I grafi e i cammini minimi

Il problema viene modellizzato matematicamente introducendo i grafi, ossia strutture matematiche costituite da nodi, per esempio gli incroci di una rete di trasporto, e dagli archi che li connettono, per esempio le strade. Trovare la strada più breve si traduce quindi nel problema di trovare un “cammino minimo” sul grafo, ossia la successione degli archi da seguire per raggiungere il nodo di arrivo coprendo la distanza più corta. Questo problema dei cammini minimi diventa allora un problema di ottimizzazione matematica e può essere risolto con particolari algoritmi di calcolo. Ed è un problema matematico che si applica a reti di dimensioni a volte molto grandi, in cui, per ogni coppia di punti di origine e destinazione, c'è un numero enorme di possibili percorsi da valutare per trovare il più corto, e senza algoritmi avanzati anche un computer superpotente non saprebbe calcolare la soluzione in un tempo accettabile.

 

Trovare la strada col crowd-sourcing

Il problema può poi complicarsi in vari modi. Nel campo della navigazione stradale, per esempio, non cerchiamo solo il percorso più breve: spesso ci interessa conoscere il percorso, magari più lungo, ma che ci consenta di raggiungere prima possibile la nostra destinazione. È questo il caso delle applicazioni per la navigazione basate sul crowd-sourcing, che consentono cioè di supportare la navigazione con i dati forniti in tempo reale dai dispositivi degli utenti stessi circa le condizioni del traffico, gli errori nelle mappe, la presenza di incidenti stradali o la chiusura di alcune strade.

 

I grafi aiutano a... diventare amici delle star

Ma non finisce qui: attraverso i grafi è possibile rappresentare efficacemente non solo le reti di trasporto, ma anche le reti telefoniche, la rete internet, e persino i social network come Facebook o Linkedin. In questo modo, attraverso l'uso degli algoritmi matematici, è possibile individuare il “percorso sociale” più agevole per diventare amici di attori famosi, incontrare l'anima gemella o trovare il lavoro dei propri sogni. Forse allora la ricerca del percorso minimo verso la felicità è proprio un problema matematico?

Roberto Natalini e Antonino Sgalambro

Roberto Natalini è un matematico, direttore dell'Istituto per le Applicazioni del Calcolo del Consiglio Nazionale delle Ricerche e responsabile dello Sportello Matematico per l'Industria Italiana (Smii).

Antonino Sgalambro è un matematico dell'Istituto per le Applicazioni del Calcolo "M. Picone" (Iac) del Cnr di Roma. Coordina il team dello Smii, portale di incontro e consulenza tra la comunità matematica e il mondo industriale messo a punto dall'Iac.

copertina   luglio-agosto 2019

  COMPRA IL NUMERO

 
  ABBONATI

 
  SOMMARIO

 
  EDITORIALE

bannerCnrXSapere 0

iscriviti copia

clark

Questo sito utilizza cookie, anche di terze parti, per migliorare la tua esperienza di navigazione. Se vuoi saperne di più consulta l'informativa estesa. Cliccando su ok acconsenti all'uso dei cookie.