WEBVTT 00:00:01.199 --> 00:00:03.279 Salve a tutti, siete all'ascolto di 00:00:03.279 --> 00:00:05.599 INSiDER - Dentro la Tecnologia, 00:00:05.599 --> 00:00:07.839 un podcast di Digital People e 00:00:07.839 --> 00:00:09.039 io sono il vostro host, 00:00:09.039 --> 00:00:10.080 Davide Fasoli. 00:00:16.864 --> 00:00:18.945 Oggi spiegheremo come fanno i navigatori, 00:00:18.945 --> 00:00:21.425 come Google Maps, a calcolare così 00:00:21.425 --> 00:00:23.585 velocemente il percorso migliore grazie a 00:00:23.585 --> 00:00:25.904 un algoritmo inventato quasi 70 anni fa. 00:00:26.059 --> 00:00:27.500 Prima di passare alle notizie che 00:00:27.500 --> 00:00:29.339 più ci hanno colpito questa settimana, 00:00:29.339 --> 00:00:31.179 vi ricordo che potete seguirci su 00:00:31.179 --> 00:00:35.020 Instagram a @dentrolatecnologia, iscrivervi alla newsletter 00:00:35.020 --> 00:00:36.859 e ascoltare un nuovo episodio ogni 00:00:36.859 --> 00:00:38.774 sabato mattina, su Spotify, 00:00:38.774 --> 00:00:41.814 Apple Podcast, Google Podcast oppure direttamente 00:00:41.814 --> 00:00:42.935 sul nostro sito. 00:00:55.770 --> 00:00:58.250 Dopo molti anni Rockstar Games ha 00:00:58.250 --> 00:01:00.170 pubblicato il trailer di Grand Theft 00:01:00.170 --> 00:01:02.490 Auto 6, il prossimo capitolo della 00:01:02.490 --> 00:01:04.250 celebre saga di videogiochi. 00:01:04.250 --> 00:01:06.409 Il trailer ha raggiunto un'incredibile cifra 00:01:06.409 --> 00:01:08.409 di oltre 100 milioni di visualizzazioni 00:01:08.584 --> 00:01:11.224 su YouTube, quasi in sole 24 ore. 00:01:11.224 --> 00:01:12.905 Grand Theft Auto 6 sarà ambientato 00:01:12.905 --> 00:01:14.825 nella mitica Vice City, 00:01:14.825 --> 00:01:17.144 una parodia di Miami e Miami Beach, 00:01:17.144 --> 00:01:18.825 ma la mappa sarà probabilmente molto 00:01:18.825 --> 00:01:19.625 più estesa. 00:01:19.625 --> 00:01:21.305 Il gioco è programmato per il 00:01:21.305 --> 00:01:24.479 2025 e sarà disponibile inizialmente solo 00:01:24.479 --> 00:01:26.939 su PlayStation 5 e Xbox Series 00:01:26.939 --> 00:01:28.079 X e S. 00:01:28.079 --> 00:01:30.239 Il filmato offre uno sguardo incredibile 00:01:30.239 --> 00:01:32.959 sulla rinnovata città, già protagonista in 00:01:32.959 --> 00:01:34.799 passato di un titolo della saga, 00:01:34.799 --> 00:01:36.159 che si presenta in tutta la 00:01:36.159 --> 00:01:39.084 sua magnificenza, sottolineata da una straordinaria 00:01:39.084 --> 00:01:41.284 qualità grafica, che sembra sfruttare a 00:01:41.284 --> 00:01:44.125 pieno la potenza delle console next-gen. 00:01:44.204 --> 00:01:45.725 Infine, quello che ha colpito, 00:01:45.725 --> 00:01:47.645 oltre ai dettagli che sembrerebbero rendere 00:01:47.645 --> 00:01:49.468 il gioco molto realistico e immersivo, 00:01:49.740 --> 00:01:51.659 è la presenza dei social network 00:01:51.659 --> 00:01:54.060 all'interno del gioco, a sottolineare quindi 00:01:54.060 --> 00:01:55.659 l'estrema attualità del titolo, 00:01:55.659 --> 00:01:57.420 che ha sempre avuto come principale 00:01:57.420 --> 00:02:00.540 obiettivo parodizzare la società contemporanea, 00:02:00.540 --> 00:02:02.060 statunitense in particolare. 00:02:04.915 --> 00:02:06.676 Lo scorso 6 dicembre Sony ha 00:02:06.676 --> 00:02:09.875 rilasciato sul mercato il nuovo controller Access, 00:02:09.875 --> 00:02:11.875 pensato per abbattere le barriere fisiche 00:02:11.875 --> 00:02:13.955 del gaming e permettere alle persone 00:02:13.955 --> 00:02:15.930 con disabilità di poter giocare ai 00:02:15.930 --> 00:02:18.409 titoli PS5 più agevolmente e più 00:02:18.409 --> 00:02:19.050 a lungo. 00:02:19.050 --> 00:02:21.050 Il vantaggio sostanziale di questo nuovo 00:02:21.050 --> 00:02:24.090 dispositivo è la sua elevata configurabilità, 00:02:24.090 --> 00:02:25.849 infatti è possibile impostare fino a 00:02:25.849 --> 00:02:28.810 30 configurazioni diverse, personalizzando a proprio 00:02:28.810 --> 00:02:31.155 piacimento la posizione dei tasti e 00:02:31.155 --> 00:02:32.594 della leva di controllo. 00:02:32.754 --> 00:02:34.514 Grazie alla sua forma ergonomica, 00:02:34.514 --> 00:02:37.155 studiata appositamente per soddisfare le esigenze 00:02:37.155 --> 00:02:39.875 dei giocatori, Access può essere posizionato 00:02:39.875 --> 00:02:42.354 con diversi orientamenti e su qualsiasi 00:02:42.354 --> 00:02:43.314 superficie piatta. 00:02:43.610 --> 00:02:45.129 In ogni caso, Sony ha comunque 00:02:45.129 --> 00:02:47.289 progettato il controller per poter essere 00:02:47.289 --> 00:02:50.810 agganciato anche a un supporto AMPS. 00:02:50.810 --> 00:02:52.169 Per quanto riguarda l'imballaggio, 00:02:52.169 --> 00:02:54.330 anch'esso è stato progettato per essere 00:02:54.330 --> 00:02:55.849 aperto con una sola mano e 00:02:55.849 --> 00:02:57.210 con il minimo sforzo, 00:02:57.289 --> 00:02:58.889 grazie a comodi anelli che possono 00:02:58.889 --> 00:03:00.965 essere tirati dal lato destro a sinistro, 00:03:00.965 --> 00:03:02.965 in modo da far scivolare facilmente 00:03:02.965 --> 00:03:05.205 il controller e i vari compartimenti 00:03:05.205 --> 00:03:06.245 del kit. 00:03:08.724 --> 00:03:10.805 L'aveva annunciata a maggio e finalmente 00:03:10.805 --> 00:03:12.645 è stata presentata Gemini, 00:03:12.645 --> 00:03:14.340 la vera risposta di Google al 00:03:14.340 --> 00:03:16.740 modello GPT-4 di OpenAI. 00:03:16.740 --> 00:03:18.020 Secondo i test effettuati, 00:03:18.020 --> 00:03:20.419 infatti, Google Gemini riesce a performare 00:03:20.419 --> 00:03:21.939 meglio rispetto a tutte le altre 00:03:21.939 --> 00:03:23.780 IA presenti sul mercato. 00:03:23.780 --> 00:03:24.419 Ma non solo. 00:03:24.754 --> 00:03:26.594 Questa nuova IA, infatti, 00:03:26.594 --> 00:03:28.435 è riuscita a superare anche l'essere 00:03:28.435 --> 00:03:30.675 umano nel test MMLU, 00:03:30.675 --> 00:03:32.915 ossia in breve riesce a creare riassunti, 00:03:32.915 --> 00:03:35.395 rispondere alle domande e tradurre meglio 00:03:35.395 --> 00:03:36.034 di noi. 00:03:36.034 --> 00:03:37.569 Sia chiaro, questo è un test 00:03:37.569 --> 00:03:40.129 che prende in considerazione solo alcuni aspetti. 00:03:40.210 --> 00:03:41.889 Su tanti altri, anche Gemini non 00:03:41.889 --> 00:03:43.890 riesce ancora a competere con l'uomo. 00:03:43.969 --> 00:03:46.849 Inoltre, l'intelligenza artificiale di Google è 00:03:46.849 --> 00:03:48.930 la prima IA multimodale al mondo. 00:03:49.185 --> 00:03:51.344 Ciò significa che riesce nativamente a 00:03:51.344 --> 00:03:54.064 comprendere testo, codice, immagini, 00:03:54.064 --> 00:03:55.185 video e audio. 00:03:55.185 --> 00:03:57.504 GPT-4, al contrario, riesce a comprendere 00:03:57.504 --> 00:03:59.025 solo il testo e si affida 00:03:59.025 --> 00:04:01.344 ad altre intelligenze artificiali per comprendere 00:04:01.344 --> 00:04:03.025 i diversi tipi di input. 00:04:03.025 --> 00:04:04.784 Google poi ci tiene a sottolineare 00:04:04.784 --> 00:04:06.360 che la sua nuova IA è 00:04:06.360 --> 00:04:08.360 stata addestrata secondo i principi di 00:04:08.360 --> 00:04:10.840 IA responsabile di Google ed è 00:04:10.840 --> 00:04:12.360 la più sicura mai creata, 00:04:12.360 --> 00:04:15.159 soprattutto in termini di pregiudizi e tossicità. 00:04:15.159 --> 00:04:17.639 Infine, Gemini si presenta in tre versioni, 00:04:17.720 --> 00:04:18.759 Ultra, la più potente, 00:04:18.975 --> 00:04:21.375 Pro, che verrà integrata in Google Bard, 00:04:21.375 --> 00:04:23.295 e Nano, che invece è pensata 00:04:23.295 --> 00:04:26.415 per lavorare offline sui nuovi Google Pixel. 00:04:39.470 --> 00:04:41.310 Le mappe stradali hanno da sempre 00:04:41.310 --> 00:04:43.789 avuto un ruolo fondamentale per semplificare 00:04:43.789 --> 00:04:45.870 e garantire gli spostamenti di qualsiasi 00:04:45.870 --> 00:04:47.644 tipo e con qualsiasi mezzo. 00:04:47.644 --> 00:04:49.004 E fino a qualche decennio fa 00:04:49.004 --> 00:04:51.564 era consuetudine arrivati magari da turisti 00:04:51.564 --> 00:04:53.245 in una nuova città o paese, 00:04:53.245 --> 00:04:55.084 acquistare le mappe da consultare e 00:04:55.084 --> 00:04:57.725 trovare così percorsi migliori per spostarsi 00:04:57.725 --> 00:04:58.685 da un posto all'altro. 00:04:58.939 --> 00:05:00.379 E non era nemmeno così raro 00:05:00.379 --> 00:05:02.539 ritrovarsi imbottigliati nel traffico, 00:05:02.539 --> 00:05:04.539 capitare in una strada chiusa o 00:05:04.539 --> 00:05:06.459 trovarsi di fronte a percorsi diversi 00:05:06.459 --> 00:05:09.100 perché le mappe acquistate non erano aggiornate. 00:05:09.180 --> 00:05:12.060 Fortunatamente tutti questi problemi sono totalmente 00:05:12.060 --> 00:05:14.459 o quasi scomparsi con l'avvento dei 00:05:14.459 --> 00:05:16.274 navigatori e ancor di più con 00:05:16.274 --> 00:05:18.514 app come Google Maps o Apple Maps, 00:05:18.514 --> 00:05:20.595 che riescono ad essere sempre aggiornate 00:05:20.595 --> 00:05:22.115 in tempo pressoché reale. 00:05:22.115 --> 00:05:23.555 Ma come fanno i navigatori a 00:05:23.555 --> 00:05:26.274 calcolare i percorsi migliori così velocemente? 00:05:26.435 --> 00:05:28.194 Utilizzando per giunta la potenza di 00:05:28.194 --> 00:05:29.875 calcolo di uno smartphone nel caso 00:05:29.875 --> 00:05:32.040 dell'utilizzo offline o di un computer 00:05:32.040 --> 00:05:33.720 di bordo, che è risaputo non 00:05:33.720 --> 00:05:36.439 essere tra i dispositivi più performanti 00:05:36.439 --> 00:05:38.759 con cui abbiamo quotidianamente a che fare, 00:05:38.759 --> 00:05:39.880 ancor di più se l'auto ha 00:05:39.880 --> 00:05:41.800 una decina di anni alle spalle. 00:05:41.800 --> 00:05:44.279 La risposta sta principalmente negli algoritmi 00:05:44.279 --> 00:05:46.974 che vengono utilizzati, ideati all'incirca negli 00:05:46.974 --> 00:05:49.294 anni 60, che sono estremamente semplici 00:05:49.294 --> 00:05:51.294 ed efficienti nel cercare, 00:05:51.375 --> 00:05:53.694 velocemente senza sprecare troppe risorse, 00:05:53.694 --> 00:05:55.615 il percorso migliore che non è 00:05:55.615 --> 00:05:57.694 necessariamente il più breve tra due punti. 00:05:58.060 --> 00:06:00.139 Prima di capire come funziona l'algoritmo 00:06:00.139 --> 00:06:01.660 dietro Google Maps, però, 00:06:01.740 --> 00:06:03.660 bisogna capire cos'è un grafo da 00:06:03.660 --> 00:06:05.180 un punto di vista matematico. 00:06:05.259 --> 00:06:07.259 Prendendo la sua definizione più semplice 00:06:07.259 --> 00:06:08.860 e comprensibile, un grafo, 00:06:08.860 --> 00:06:10.814 da non confondersi con un grafico, 00:06:10.814 --> 00:06:12.095 non è altro che un insieme 00:06:12.095 --> 00:06:14.254 di nodi o vertici connessi tra 00:06:14.254 --> 00:06:15.775 loro attraverso degli archi. 00:06:15.775 --> 00:06:17.855 Possiamo immaginarlo come una rete di 00:06:17.855 --> 00:06:19.855 punti tra loro interconnessi, 00:06:19.855 --> 00:06:21.535 dove gli archi possono anche assumere 00:06:21.535 --> 00:06:23.134 un certo peso che può ad 00:06:23.134 --> 00:06:24.574 esempio indicarne la lunghezza. 00:06:24.889 --> 00:06:26.889 Se ci pensiamo, con questa definizione 00:06:26.889 --> 00:06:29.449 possiamo accorgerci di come siamo circondati 00:06:29.449 --> 00:06:31.610 da strutture che possono essere rappresentate 00:06:31.610 --> 00:06:32.569 da grafi. 00:06:32.569 --> 00:06:34.649 Alcuni esempi sono la rete internet, 00:06:34.649 --> 00:06:37.610 gli alberi genealogici, gli alberi decisionali, 00:06:37.610 --> 00:06:38.889 la rete di amici di un 00:06:38.889 --> 00:06:41.264 social network e, come si può intuire, 00:06:41.264 --> 00:06:42.465 la rete stradale. 00:06:42.465 --> 00:06:45.264 Di esempi, dunque, possono essercene tantissimi, 00:06:45.264 --> 00:06:46.625 ed è proprio per questo motivo 00:06:46.625 --> 00:06:48.064 che la teoria dei grafi, 00:06:48.064 --> 00:06:49.824 ossia quella disciplina che si occupa 00:06:49.824 --> 00:06:51.504 proprio di studiare questi oggetti, 00:06:51.504 --> 00:06:53.185 è di notevole interesse per la 00:06:53.185 --> 00:06:54.145 comunità scientifica. 00:06:54.500 --> 00:06:56.100 Per citare un ultimo esempio, 00:06:56.100 --> 00:06:57.300 le stesse reti neurali, 00:06:57.300 --> 00:06:58.740 che sono alla base dei moderni 00:06:58.740 --> 00:07:00.660 modelli di intelligenza artificiale, 00:07:00.660 --> 00:07:02.500 fanno uso di grafi per funzionare 00:07:02.500 --> 00:07:04.660 e rispondere alle nostre domande. 00:07:04.660 --> 00:07:06.660 Ora che sappiamo che cos'è un grafo, 00:07:06.824 --> 00:07:09.305 l'intera rete stradale può essere rappresentata 00:07:09.305 --> 00:07:11.625 come un insieme di nodi ed archi. 00:07:11.625 --> 00:07:13.465 I nodi possono essere incroci, 00:07:13.465 --> 00:07:17.064 rotonde, punti d'interesse o anche singole abitazioni. 00:07:17.064 --> 00:07:18.745 Gli archi che connettono questi nodi 00:07:18.745 --> 00:07:20.425 sono invece le varie strade, 00:07:20.425 --> 00:07:22.745 di diversa lunghezza o differenti caratteristiche. 00:07:23.120 --> 00:07:24.879 A questo punto serve quindi solo 00:07:24.879 --> 00:07:26.800 un algoritmo che trovi il percorso 00:07:26.800 --> 00:07:28.240 più breve tra due nodi, 00:07:28.240 --> 00:07:30.160 quello che rappresenta la nostra posizione 00:07:30.160 --> 00:07:31.839 e quello che rappresenta invece la 00:07:31.839 --> 00:07:33.439 destinazione da raggiungere. 00:07:33.439 --> 00:07:35.199 Una possibile soluzione può essere quella 00:07:35.199 --> 00:07:36.639 di andare a tentativi, 00:07:36.639 --> 00:07:38.805 quindi simulare tutti i possibili percorsi, 00:07:38.805 --> 00:07:40.725 e scegliere infine quello migliore. 00:07:40.725 --> 00:07:42.805 Soluzione che può certamente funzionare per 00:07:42.805 --> 00:07:44.725 un grafo composto da una decina 00:07:44.725 --> 00:07:46.165 di nodi, ma per la rete 00:07:46.165 --> 00:07:47.685 stradale mondiale che è un grafo 00:07:47.685 --> 00:07:50.004 complessissimo composto da miliardi di archi 00:07:50.004 --> 00:07:52.245 e nodi, il discorso è totalmente diverso. 00:07:52.699 --> 00:07:55.740 Siamo nel 1956 e al National 00:07:55.740 --> 00:07:58.939 Research Institute for Mathematics and Computer 00:07:58.939 --> 00:08:01.339 Science di Amsterdam si sta sviluppando 00:08:01.339 --> 00:08:03.019 un nuovo tipo di computer, 00:08:03.019 --> 00:08:05.180 l'Arcam, che integrava un sistema per 00:08:05.180 --> 00:08:06.139 il calcolo parallelo. 00:08:06.454 --> 00:08:08.535 Serviva quindi un programma per dimostrare 00:08:08.535 --> 00:08:10.535 la capacità di questo nuovo computer, 00:08:10.535 --> 00:08:12.615 ed è qui che interviene l'informatico 00:08:12.615 --> 00:08:14.574 e ingegnere tedesco Dijkstra. 00:08:14.574 --> 00:08:16.774 Dijkstra voleva trovare un problema, 00:08:16.774 --> 00:08:18.214 e di conseguenza una soluzione, 00:08:18.420 --> 00:08:20.900 che fosse semplice e facilmente comprensibile 00:08:20.900 --> 00:08:23.220 a tutti, anche ai non programmatori. 00:08:23.220 --> 00:08:24.579 Fu così che in circa venti 00:08:24.580 --> 00:08:26.740 minuti ideò l'algoritmo che lo rese 00:08:26.740 --> 00:08:28.420 famoso in tutto il mondo e 00:08:28.420 --> 00:08:30.340 che ancora oggi porta il suo nome, 00:08:30.595 --> 00:08:32.274 ossia quello per trovare il percorso 00:08:32.274 --> 00:08:33.875 più breve tra due nodi di 00:08:33.875 --> 00:08:34.835 uno stesso grafo. 00:08:34.835 --> 00:08:36.595 Quello che fece poi Dijkstra per 00:08:36.595 --> 00:08:38.835 dimostrare il funzionamento di Arcam e 00:08:38.835 --> 00:08:40.914 del suo programma fu quindi prendere 00:08:40.914 --> 00:08:43.715 una mappa semplificata che collegava 64 00:08:43.715 --> 00:08:45.799 città olandesi, creare un grafo e 00:08:45.799 --> 00:08:47.559 applicare il suo algoritmo per trovare 00:08:47.559 --> 00:08:49.879 il percorso più breve tra Rotterdam 00:08:49.879 --> 00:08:51.160 e Groningen. 00:08:51.240 --> 00:08:54.040 Insomma, una primordiale forma estremamente semplificata 00:08:54.040 --> 00:08:57.080 di navigatore, che però funzionava egregiamente bene. 00:08:57.365 --> 00:08:59.044 Proprio per questo lo stesso codice 00:08:59.044 --> 00:09:00.485 di base, o meglio una sua 00:09:00.485 --> 00:09:03.284 versione leggermente modificata, viene utilizzata anche 00:09:03.284 --> 00:09:05.125 oggi per applicazioni di questo tipo. 00:09:05.125 --> 00:09:07.605 Ma come funziona in sostanza questo algoritmo? 00:09:07.684 --> 00:09:08.804 Questo è uno di quei casi 00:09:08.804 --> 00:09:10.324 in cui delle immagini o un 00:09:10.324 --> 00:09:12.240 video sarebbero di grande aiuto, 00:09:12.320 --> 00:09:14.000 ma faremo il possibile per renderlo 00:09:14.000 --> 00:09:16.000 facile da immaginare e semplice da 00:09:16.000 --> 00:09:17.440 spiegare anche sulla voce. 00:09:17.440 --> 00:09:19.040 In ogni caso un breve riassunto 00:09:19.040 --> 00:09:21.040 con anche le immagini potrete trovarlo 00:09:21.040 --> 00:09:22.800 nel post che uscirà il prossimo 00:09:22.800 --> 00:09:24.960 mercoledì sulla nostra pagina Instagram, 00:09:24.960 --> 00:09:26.480 @dentrolatecnologia. 00:09:26.955 --> 00:09:28.955 Immaginiamo un grafo molto semplice, 00:09:28.955 --> 00:09:30.619 formato da 4 nodi A, 00:09:30.619 --> 00:09:31.835 B, C e D. 00:09:31.835 --> 00:09:33.461 L'obiettivo è di andare da A 00:09:33.461 --> 00:09:35.435 a D nel minor tempo possibile. 00:09:35.514 --> 00:09:37.595 Sappiamo inoltre che per andare da 00:09:37.595 --> 00:09:39.355 A a B ci vogliono 3 minuti, 00:09:39.355 --> 00:09:40.710 per andare da A a C 00:09:40.709 --> 00:09:41.909 ce ne vogliono 5, 00:09:41.909 --> 00:09:43.110 per andare da C a D 00:09:43.110 --> 00:09:44.389 ci vogliono 6 minuti, 00:09:44.389 --> 00:09:45.830 per andare da B a D 00:09:45.829 --> 00:09:47.110 ci vogliono 10 minuti, 00:09:47.110 --> 00:09:49.110 e infine c'è un collegamento diretto 00:09:49.110 --> 00:09:50.549 tra A e D che però 00:09:50.549 --> 00:09:51.750 dura 12 minuti. 00:09:51.750 --> 00:09:53.590 Quello che fa l'algoritmo Dijkstra è 00:09:53.735 --> 00:09:55.654 calcolare quanto tempo ci si impiega 00:09:55.654 --> 00:09:57.654 per arrivare da A a qualsiasi 00:09:57.654 --> 00:09:58.855 nodo del grafo. 00:09:58.855 --> 00:10:01.495 All'inizio tutti i nodi sono senza valore, 00:10:01.495 --> 00:10:02.774 o in alcuni casi hanno un 00:10:02.774 --> 00:10:03.815 valore infinito. 00:10:03.815 --> 00:10:05.014 Noi ci troviamo ad A, 00:10:05.014 --> 00:10:06.455 che avrà valore 0 in quanto 00:10:06.455 --> 00:10:08.535 ci mettiamo 0 minuti per arrivarci. 00:10:08.919 --> 00:10:10.919 Da A possiamo arrivare a B, 00:10:10.919 --> 00:10:12.840 C e D, che quindi assumeranno 00:10:12.840 --> 00:10:14.759 valore relativamente di 3, 00:10:14.759 --> 00:10:15.879 5 e 12. 00:10:16.040 --> 00:10:17.559 A questo punto in ordine si 00:10:17.559 --> 00:10:19.799 ripete il procedimento partendo dal nodo 00:10:19.799 --> 00:10:21.160 con valore più piccolo, 00:10:21.160 --> 00:10:22.120 in questo caso B. 00:10:22.274 --> 00:10:24.355 Da B possiamo arrivare solo a D, 00:10:24.355 --> 00:10:26.434 impiegando in totale 13 minuti, 00:10:26.434 --> 00:10:28.115 ossia i 3 minuti per raggiungere 00:10:28.115 --> 00:10:29.555 B da A e i 10 00:10:29.555 --> 00:10:31.394 minuti per raggiungere D da B. 00:10:31.394 --> 00:10:32.754 Tuttavia il nodo D lo possiamo 00:10:32.754 --> 00:10:35.394 raggiungere tranquillamente in 12 minuti partendo 00:10:35.394 --> 00:10:37.730 direttamente da A, quindi questa soluzione 00:10:37.730 --> 00:10:39.809 non è la migliore e va scartata. 00:10:39.809 --> 00:10:42.289 Passiamo quindi ad analizzare il secondo nodo, 00:10:42.289 --> 00:10:42.769 C. 00:10:42.769 --> 00:10:44.449 In questo caso da C possiamo 00:10:44.449 --> 00:10:46.289 raggiungere D in 6 minuti, 00:10:46.289 --> 00:10:47.970 per un tempo totale di percorrenza 00:10:47.970 --> 00:10:49.649 di 12 minuti, ossia un minuto 00:10:49.649 --> 00:10:51.855 in meno rispetto al percorso diretto 00:10:51.855 --> 00:10:52.414 a D. 00:10:52.414 --> 00:10:54.574 Non essendoci altri nodi da analizzare 00:10:54.574 --> 00:10:56.095 abbiamo quindi trovato il percorso più 00:10:56.095 --> 00:10:58.174 veloce per raggiungere D da A, 00:10:58.174 --> 00:10:59.695 ossia quello che passa da C. 00:10:59.695 --> 00:11:01.695 Un algoritmo, quello di Dijkstra, 00:11:01.695 --> 00:11:03.695 semplice e considerato elegante, 00:11:03.774 --> 00:11:05.214 perché con poche righe di codice 00:11:05.214 --> 00:11:06.960 riesce a risolvere in tempi brevi 00:11:06.960 --> 00:11:08.639 un problema molto complesso. 00:11:08.800 --> 00:11:10.480 Nell'esempio appena fatto, che è chiaramente 00:11:10.480 --> 00:11:13.360 molto semplificato rispetto ad una mappa stradale, 00:11:13.360 --> 00:11:15.279 abbiamo utilizzato come unità di misura 00:11:15.279 --> 00:11:16.720 i minuti, per dare un peso 00:11:16.720 --> 00:11:18.559 ai collegamenti tra i vari nodi. 00:11:18.559 --> 00:11:21.440 Tuttavia nulla vieta di utilizzare altri criteri. 00:11:21.440 --> 00:11:23.434 Possiamo infatti cercare il percorso più 00:11:23.434 --> 00:11:25.835 breve utilizzando la lunghezza delle strade, 00:11:25.835 --> 00:11:27.754 il percorso più breve utilizzando come 00:11:27.754 --> 00:11:29.754 nell'esempio i minuti o comunque i 00:11:29.754 --> 00:11:31.914 limiti di velocità posti per strada. 00:11:31.995 --> 00:11:33.754 Oppure si può utilizzare un criterio 00:11:33.754 --> 00:11:36.715 che tiene conto del consumo dell'anidride carbonica, 00:11:37.019 --> 00:11:39.340 come ha fatto Google introducendo recentemente 00:11:39.340 --> 00:11:42.779 in Maps l'opzione per il percorso ecosostenibile. 00:11:42.940 --> 00:11:45.580 Contemporaneamente Google o Apple utilizzano i 00:11:45.580 --> 00:11:48.059 dati aggregati dei dispositivi Android o 00:11:48.059 --> 00:11:50.540 iOS per raccogliere le informazioni sullo 00:11:50.540 --> 00:11:52.524 stato del traffico e aggiornare in 00:11:52.524 --> 00:11:54.125 tempo reale il peso di ogni 00:11:54.125 --> 00:11:55.804 strada e a sua volta aggiornare 00:11:55.804 --> 00:11:57.485 il percorso di conseguenza. 00:11:57.565 --> 00:12:00.445 O ancora utilizzando l'intelligenza artificiale si 00:12:00.445 --> 00:12:02.445 può addirittura predire il traffico che 00:12:02.445 --> 00:12:04.700 ci sarà in un determinato percorso. 00:12:04.940 --> 00:12:07.419 Insomma, l'algoritmo di base è semplice, 00:12:07.419 --> 00:12:08.539 ma ciò che rende le app 00:12:08.539 --> 00:12:10.539 di navigazione un passo avanti rispetto 00:12:10.539 --> 00:12:12.620 ai navigatori più classici è proprio 00:12:12.620 --> 00:12:14.299 la capacità di dare alle strade 00:12:14.299 --> 00:12:17.205 il giusto peso, utilizzando complessi sistemi 00:12:17.205 --> 00:12:19.045 di analisi dei dati e sempre 00:12:19.045 --> 00:12:20.805 più l'intelligenza artificiale. 00:12:20.884 --> 00:12:22.965 Ad essere sinceri infine anche l'algoritmo 00:12:22.965 --> 00:12:25.764 che viene utilizzato, come dicevamo poco fa, 00:12:25.764 --> 00:12:27.924 non è esattamente quello ideato da Dijkstra, 00:12:28.049 --> 00:12:30.049 bensì una sua versione modificata e 00:12:30.049 --> 00:12:31.730 migliorata che prende il nome di 00:12:31.730 --> 00:12:33.450 algoritmo A*. 00:12:33.450 --> 00:12:35.970 L'A* è stato descritto per la 00:12:35.970 --> 00:12:39.649 prima volta nel 1968 da Peter Hart, 00:12:39.649 --> 00:12:42.424 Nils Nilsson e Bertram Raphael che 00:12:42.424 --> 00:12:44.985 hanno introdotto il concetto di stima euristica. 00:12:45.064 --> 00:12:47.144 In pratica invece di controllare tutti 00:12:47.144 --> 00:12:48.664 o quasi i nodi come fa 00:12:48.664 --> 00:12:50.904 l'algoritmo Dijkstra, si dà priorità a 00:12:50.904 --> 00:12:52.184 quelli che in qualche modo si 00:12:52.184 --> 00:12:54.024 avvicinano più alla destinazione. 00:12:54.419 --> 00:12:55.459 Per fare un esempio, 00:12:55.459 --> 00:12:56.740 per andare da Monaco a Roma 00:12:56.740 --> 00:12:58.339 è più probabile che il percorso 00:12:58.339 --> 00:13:00.500 corretto vada verso sud piuttosto che 00:13:00.500 --> 00:13:02.500 verso nord, e quindi la ricerca 00:13:02.500 --> 00:13:04.980 del percorso migliore si concentrerà maggiormente 00:13:04.980 --> 00:13:07.059 su quelle strade che vanno effettivamente 00:13:07.059 --> 00:13:07.620 verso Roma. 00:13:07.845 --> 00:13:09.605 In questo caso la stima euristica 00:13:09.605 --> 00:13:12.245 introdotta potrebbe essere proprio la distanza 00:13:12.245 --> 00:13:14.564 in linea d'aria della destinazione dei 00:13:14.564 --> 00:13:16.084 vari punti della mappa. 00:13:16.084 --> 00:13:18.644 Ed è stato dimostrato come questo algoritmo, 00:13:18.644 --> 00:13:20.884 pur non tentando tutte le possibili alternative, 00:13:21.110 --> 00:13:22.870 riesca a trovare, in modo ancora 00:13:22.870 --> 00:13:24.790 più ottimizzato e veloce rispetto alla 00:13:24.790 --> 00:13:26.389 versione ideata da Dijkstra, 00:13:26.389 --> 00:13:28.230 il miglior percorso che collega a 00:13:28.230 --> 00:13:29.350 due punti di un grafo, 00:13:29.350 --> 00:13:30.870 o nel caso dei navigatori, 00:13:30.950 --> 00:13:32.149 due punti della mappa. 00:13:32.230 --> 00:13:34.230 Quindi, per concludere, cosa c'è dietro 00:13:34.230 --> 00:13:36.014 a Google Maps e simili? 00:13:36.014 --> 00:13:37.294 Oltre a una buona dose di 00:13:37.294 --> 00:13:39.294 raccolta e analisi dei dati dei 00:13:39.294 --> 00:13:40.975 propri utenti, ciò che rende queste 00:13:40.975 --> 00:13:43.855 app così funzionali sono una manciata 00:13:43.855 --> 00:13:45.134 di righe di codice, 00:13:45.134 --> 00:13:47.214