Salve a tutti, siete all'ascolto di INSiDER - Dentro la Tecnologia, un podcast di Digital People e io sono il vostro host Davide Fasoli.

Oggi spiegheremo come fanno i navigatori, come Google Maps, a calcolare così velocemente il percorso migliore grazie a un algoritmo inventato quasi 70 anni fa.

Prima di passare alle notizie che più ci hanno colpito questa settimana, vi ricordo che potete seguirci su Instagram a @dentrolatecnologia, iscrivervi alla newsletter e ascoltare un nuovo episodio ogni sabato mattina, su Spotify, Apple Podcast, Google Podcast oppure direttamente sul nostro sito.

Dopo molti anni Rockstar Games ha pubblicato il trailer di Grand Theft Auto 6, il prossimo capitolo della celebre saga di videogiochi. Il trailer ha raggiunto un'incredibile cifra di oltre 100 milioni di visualizzazioni su YouTube, quasi in sole 24 ore. Grand Theft Auto 6 sarà ambientato nella mitica Vice City, una parodia di Miami e Miami Beach,

ma la mappa sarà probabilmente molto più estesa. Il gioco è programmato per il 2025 e sarà disponibile inizialmente solo su PlayStation 5 e Xbox Series X e S. Il filmato offre uno sguardo incredibile sulla rinnovata città, già protagonista in passato di un titolo della saga, che si presenta in tutta la sua magnificenza, sottolineata da una straordinaria

qualità grafica, che sembra sfruttare a pieno la potenza delle console next-gen. Infine, quello che ha colpito, oltre ai dettagli che sembrerebbero rendere il gioco molto realistico e immersivo, è la presenza dei social network all'interno del gioco, a sottolineare quindi l'estrema attualità del titolo, che ha sempre avuto come principale obiettivo parodizzare

la società contemporanea, statunitense in particolare.

Lo scorso 6 dicembre Sony ha rilasciato sul mercato il nuovo controller Access, pensato per abbattere le barriere fisiche del gaming e permettere alle persone con disabilità di poter giocare ai titoli PS5 più agevolmente e più a lungo.

Il vantaggio sostanziale di questo nuovo dispositivo è la sua elevata configurabilità, infatti è possibile impostare fino a 30 configurazioni diverse, personalizzando a proprio piacimento la posizione dei tasti e della leva di controllo.

Grazie alla sua forma ergonomica, studiata appositamente per soddisfare le esigenze dei giocatori, Access può essere posizionato con diversi orientamenti e su qualsiasi superficie piatta.

In ogni caso, Sony ha comunque progettato il controller per poter essere agganciato anche a un supporto AMPS.

Per quanto riguarda l'imballaggio, anch'esso è stato progettato per essere aperto con una sola mano e con il minimo sforzo, grazie a comodi anelli che possono essere tirati dal lato destro a sinistro, in modo da far scivolare facilmente il controller e i vari compartimenti del kit.

L'aveva annunciata a maggio e finalmente è stata presentata Gemini, la vera risposta di Google al modello GPT-4 di OpenAI.

Secondo i test effettuati, infatti, Google Gemini riesce a performare meglio rispetto a tutte le altre IA presenti sul mercato.

Ma non solo.

Questa nuova IA, infatti, è riuscita a superare anche l'essere umano nel test MMLU, ossia in breve riesce a creare riassunti, rispondere alle domande e tradurre meglio di noi.

Sia chiaro, questo è un test che prende in considerazione solo alcuni aspetti.

Su tanti altri, anche Gemini non riesce ancora a competere con l'uomo.

Inoltre, l'intelligenza artificiale di Google è la prima IA multimodale al mondo.

Ciò significa che riesce nativamente a comprendere testo, codice, immagini, video e audio.

GPT-4, al contrario, riesce a comprendere solo il testo e si affida ad altre intelligenze artificiali per comprendere i diversi tipi di input.

Google poi ci tiene a sottolineare che la sua nuova IA è stata addestrata secondo i principi di IA responsabile di Google ed è la più sicura mai creata, soprattutto in termini di pregiudizi e tossicità.

Infine, Gemini si presenta in tre versioni, Ultra, la più potente, Pro, che verrà integrata in Google Bard, e Nano, che invece è pensata per lavorare offline sui nuovi Google Pixel.

Le mappe stradali hanno da sempre avuto un ruolo fondamentale per semplificare e garantire gli spostamenti di qualsiasi tipo e con qualsiasi mezzo. E fino a qualche decennio fa era consuetudine arrivati magari da turisti in una nuova città o paese, acquistare le mappe da consultare e trovare così percorsi migliori per spostarsi da un posto all'altro. E non era nemmeno così

raro ritrovarsi imbottigliati nel traffico, capitare in una strada chiusa o trovarsi di fronte a percorsi diversi perché le mappe acquistate non erano aggiornate. Fortunatamente tutti questi problemi sono totalmente o quasi scomparsi con l'avvento dei navigatori e ancor di più con app come Google Maps o Apple Maps, che riescono ad essere sempre aggiornate

in tempo pressoché reale. Ma come fanno i navigatori a calcolare i percorsi migliori così velocemente? Utilizzando per giunta la potenza di calcolo di uno smartphone nel caso dell'utilizzo offline o di un computer di bordo, che è risaputo non essere tra i dispositivi più performanti con cui abbiamo quotidianamente a che fare, ancor di più

se l'auto ha una decina di anni alle spalle. La risposta sta principalmente negli algoritmi che vengono utilizzati, ideati all'incirca negli anni 60, che sono estremamente semplici ed efficienti nel cercare, velocemente senza sprecare troppe risorse, il percorso migliore che non è necessariamente il più breve tra due punti.

Prima di capire come funziona l'algoritmo dietro Google Maps, però, bisogna capire cos'è un grafo da un punto di vista matematico. Prendendo la sua definizione più semplice e comprensibile, un grafo, da non confondersi con un grafico, non è altro che un insieme di nodi o vertici connessi tra loro attraverso degli archi. Possiamo immaginarlo come una

rete di punti tra loro interconnessi, dove gli archi possono anche assumere un certo peso che può ad esempio indicarne la lunghezza. Se ci pensiamo, con questa definizione possiamo accorgerci di come siamo circondati da strutture che possono essere rappresentate da grafi.

Alcuni esempi sono la rete internet, gli alberi genealogici, gli alberi decisionali, la rete di amici di un social network e, come si può intuire, la rete stradale.

Di esempi, dunque, possono essercene tantissimi, ed è proprio per questo motivo che la teoria dei grafi, ossia quella disciplina che si occupa proprio di studiare questi oggetti, è di notevole interesse per la comunità scientifica. Per citare un ultimo esempio, le stesse reti neurali, che sono alla base dei moderni modelli di intelligenza artificiale,

fanno uso di grafi per funzionare e rispondere alle nostre domande.

Ora che sappiamo che cos'è un grafo, l'intera rete stradale può essere rappresentata come un insieme di nodi ed archi. I nodi possono essere incroci, rotonde, punti d'interesse o anche singole abitazioni. Gli archi che connettono questi nodi sono invece le varie strade, di diversa lunghezza o differenti caratteristiche. A questo punto serve quindi

solo un algoritmo che trovi il percorso più breve tra due nodi, quello che rappresenta la nostra posizione e quello che rappresenta invece la destinazione da raggiungere.

Una possibile soluzione può essere quella di andare a tentativi, quindi simulare tutti i possibili percorsi, e scegliere infine quello migliore. Soluzione che può certamente funzionare per un grafo composto da una decina di nodi, ma per la rete stradale mondiale che è un grafo complessissimo composto da miliardi di archi e nodi, il discorso è totalmente diverso.

Siamo nel 1956 e al National Research Institute for Mathematics and Computer Science di Amsterdam si sta sviluppando un nuovo tipo di computer, l'Arcam, che integrava un sistema per il calcolo parallelo. Serviva quindi un programma per dimostrare la capacità di questo nuovo computer, ed è qui che interviene l'informatico e ingegnere tedesco Dijkstra.

Dijkstra voleva trovare un problema, e di conseguenza una soluzione, che fosse semplice e facilmente comprensibile a tutti, anche ai non programmatori. Fu così che in circa venti minuti ideò l'algoritmo che lo rese famoso in tutto il mondo e che ancora oggi porta il suo nome, ossia quello per trovare il percorso più breve tra due nodi di uno stesso grafo.

Quello che fece poi Dijkstra per dimostrare il funzionamento di Arcam e del suo programma fu quindi prendere una mappa semplificata che collegava 64 città olandesi, creare un grafo e applicare il suo algoritmo per trovare il percorso più breve tra Rotterdam e Groningen.

Insomma, una primordiale forma estremamente semplificata di navigatore, che però funzionava egregiamente bene. Proprio per questo lo stesso codice di base, o meglio una sua versione leggermente modificata, viene utilizzata anche oggi per applicazioni di questo tipo.

Ma come funziona in sostanza questo algoritmo? Questo è uno di quei casi in cui delle immagini o un video sarebbero di grande aiuto, ma faremo il possibile per renderlo facile da immaginare e semplice da spiegare anche sulla voce. In ogni caso un breve riassunto con anche le immagini potrete trovarlo nel post che uscirà il prossimo mercoledì sulla

nostra pagina Instagram, @dentrolatecnologia.

Immaginiamo un grafo molto semplice, formato da 4 nodi A, B, C e D. L'obiettivo è di andare da A a D nel minor tempo possibile. Sappiamo inoltre che per andare da A a B ci vogliono 3 minuti, per andare da A a C ce ne vogliono 5, per andare da C a D ci vogliono 6 minuti, per andare da B a D ci vogliono 10 minuti, e infine c'è un collegamento diretto tra

A e D che però dura 12 minuti. Quello che fa l'algoritmo Dijkstra è calcolare quanto tempo ci si impiega per arrivare da A a qualsiasi nodo del grafo. All'inizio tutti i nodi sono senza valore, o in alcuni casi hanno un valore infinito. Noi ci troviamo ad A, che avrà valore 0 in quanto ci mettiamo 0 minuti per arrivarci. Da A possiamo arrivare

a B, C e D, che quindi assumeranno valore relativamente di 3, 5 e 12.

A questo punto in ordine si ripete il procedimento partendo dal nodo con valore più piccolo, in questo caso B. Da B possiamo arrivare solo a D, impiegando in totale 13 minuti, ossia i 3 minuti per raggiungere B da A e i 10 minuti per raggiungere D da B. Tuttavia il nodo D lo possiamo raggiungere tranquillamente in 12 minuti partendo direttamente da A, quindi

questa soluzione non è la migliore e va scartata. Passiamo quindi ad analizzare il secondo nodo, C. In questo caso da C possiamo raggiungere D in 6 minuti, per un tempo totale di percorrenza di 12 minuti, ossia un minuto in meno rispetto al percorso diretto a D. Non essendoci altri nodi da analizzare abbiamo quindi trovato il percorso più veloce per raggiungere D

da A, ossia quello che passa da C. Un algoritmo, quello di Dijkstra, semplice e considerato elegante, perché con poche righe di codice riesce a risolvere in tempi brevi un problema molto complesso. Nell'esempio appena fatto, che è chiaramente molto semplificato rispetto ad una mappa stradale, abbiamo utilizzato come unità di misura i minuti,

per dare un peso ai collegamenti tra i vari nodi. Tuttavia nulla vieta di utilizzare altri criteri.

Possiamo infatti cercare il percorso più breve utilizzando la lunghezza delle strade, il percorso più breve utilizzando come nell'esempio i minuti o comunque i limiti di velocità posti per strada. Oppure si può utilizzare un criterio che tiene conto del consumo dell'anidride carbonica, come ha fatto Google introducendo recentemente in Maps l'opzione

per il percorso ecosostenibile. Contemporaneamente Google o Apple utilizzano i dati aggregati dei dispositivi Android o iOS per raccogliere le informazioni sullo stato del traffico e aggiornare in tempo reale il peso di ogni strada e a sua volta aggiornare il percorso di conseguenza. O ancora utilizzando l'intelligenza artificiale si può

addirittura predire il traffico che ci sarà in un determinato percorso. Insomma, l'algoritmo di base è semplice, ma ciò che rende le app di navigazione un passo avanti rispetto ai navigatori più classici è proprio la capacità di dare alle strade il giusto peso, utilizzando complessi sistemi di analisi dei dati e sempre più l'intelligenza artificiale. Ad essere sinceri

infine anche l'algoritmo che viene utilizzato, come dicevamo poco fa, non è esattamente quello ideato da Dijkstra, bensì una sua versione modificata e migliorata che prende il nome di algoritmo A*. L'A* è stato descritto per la prima volta nel 1968 da Peter Hart, Nils Nilsson e Bertram Raphael che hanno introdotto il concetto di stima euristica. In pratica invece

di controllare tutti o quasi i nodi come fa l'algoritmo Dijkstra, si dà priorità a quelli che in qualche modo si avvicinano più alla destinazione. Per fare un esempio, per andare da Monaco a Roma è più probabile che il percorso corretto vada verso sud piuttosto che verso nord, e quindi la ricerca del percorso migliore si concentrerà maggiormente su quelle

strade che vanno effettivamente verso Roma. In questo caso la stima euristica introdotta potrebbe essere proprio la distanza in linea d'aria della destinazione dei vari punti della mappa. Ed è stato dimostrato come questo algoritmo, pur non tentando tutte le possibili alternative, riesca a trovare, in modo ancora più ottimizzato e veloce rispetto alla versione

ideata da Dijkstra, il miglior percorso che collega a due punti di un grafo, o nel caso dei navigatori, due punti della mappa. Quindi, per concludere, cosa c'è dietro a Google Maps e simili? Oltre a una buona dose di raccolta e analisi dei dati dei propri utenti, ciò che rende queste app così funzionali sono una manciata di righe di codice, di un algoritmo tutto sommato

semplice scritto 67 anni fa. E se ci pensiamo, il problema alla base era complessissimo, data la quantità di nodi, o in questo caso di strade, da percorrere per trovare quella migliore. Talmente complesso che senza l'intuizione di Dijkstra probabilmente le app di navigazione ad oggi nemmeno esisterebbero. E la prossima volta che utilizzeremo Google Maps, magari per raggiungere

la destinazione delle prossime vacanze natalizie, potrete dire di conoscere ciò che la rende così speciale.

E così si conclude questa puntata di INSiDER - Dentro la Tecnologia, io ringrazio come sempre la redazione e in special modo Matteo Gallo e Luca Martinelli che ogni sabato mattina ci permettono di pubblicare un nuovo episodio.

Per qualsiasi tipo di domanda o suggerimento scriveteci a redazione@dentrolatecnologia.it seguiteci su Instagram a @dentrolatecnologia dove durante la settimana pubblichiamo notizie e approfondimenti.

In qualsiasi caso nella descrizione della puntata troverete tutti i nostri social.

Se trovate interessante il podcast condividetelo che per noi è un ottimo modo per crescere e non dimenticate di farci pubblicità.

Noi ci sentiamo la settimana prossima.