Oggi proseguiamo il discorso sul Problema del Commesso Viaggiatore approfondendo il concetto di Ottimizzazione e correggendo alcune imprecisioni dello scorso episodio. Pensieri in codice Autori dell’episodio: Elia Migliore, Valerio Galano Entra a far parte della community Canale Telegram Gruppo Telegram Sostieni il progetto Sostieni tramite Satispay Sostieni tramite Revolut Sostieni tramite PayPal (applica commissioni) Sostieni utilizzando i link affiliati di Pensieri in codice: Amazon, Todoist, Readwise Reader, Satispay Sostenitori di oggi: Edoardo Secco, Carlo Tomas Partner Runtime Radio GrUSP - Codice sconto per tutti gli eventi: community_PIC Schrödinger Hat Fonti dell'episodio https://it.m.wikipedia.org/wiki/Ricerca_operativa https://it.m.wikipedia.org/wiki/Ottimizzazione_(matematica) https://it.m.wikipedia.org/wiki/Programmazione_lineare https://it.m.wikipedia.org/wiki/Euristica Attrezzatura Shure Microfono Podcast USB MV7 Neewer NW-5 Pannello fonoassorbente Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast. Crediti Sound design - Alex Raccuglia Voce intro - Maria Chiara Virgili Voce intro - Spad Musiche - Kubbi - Up In My Jam, Light-foot - Moldy Lotion, Creativity, Old time memories Suoni - Zapsplat.com Cover e trascrizione - Francesco Zubani
Audio and video play straight from the show's own hosting. PodSubs stores and serves no media.
Transcript
From the show. Tap a time to play from there.
Dopo l'ultimo episodio di Snippet, quello sul problema del commesso viaggiatore, sono stato contattato da un ascoltatore del podcast, Elia, che mi ha fatto notare che ho dato un paio di informazioni sbagliate o incomplete. La mia conoscenza del problema infatti era un po' datata e le mie ricerche per scrivere l'episodio non hanno aiutato a colmare queste lacune. Elia invece ha scritto un paper su una variante molto più complessa del TSP ed ha anche ideato una euristica, cioè una procedura che esplora un numero limitato di possibili soluzioni
per trovarne una il più possibile vicino a quella ottima in modo molto rapido. In poche parole Elia è molto più ferrato di me sull'argomento e per questo motivo l'ho incastrato e gli ho chiesto di scrivere il testo per questo episodio in modo da approfondire il concetto di ottimizzazione e chiarire e correggere un po' di cose dette l'ultima volta. Lui molto gentilmente ha accettato ed il risultato di questa collaborazione è lo snippet che stai per ascoltare.
Un problema di ottimizzazione è un tipo di problema matematico in cui si cerca di trovare il valore migliore, detto anche ottimo, di una funzione denominata obiettivo. Problemi di ottimizzazione sono ad esempio scegliere i prodotti con cui fare la spesa per la settimana, andando a riempire il nostro carrello spendendo il meno possibile, cercare di montare i pezzi di un macchinario industriale parallelizzando il più possibile i vari step di montaggio, cercare la più corta sequenza di istruzioni per scrivere un programma
che effettui un calcolo ed anche trovare il percorso più breve per attraversare un certo numero di città. Ebbene sì, il problema del commesso viaggiatore di cui abbiamo parlato nell'episodio precedente è proprio un problema di ottimizzazione. La branca dell'informatica che si occupa di calcolare e affrontare sistematicamente questo tipo di problemi è nota con il nome di ricerca operativa. Tale nome ha origine nel contesto delle operazioni militari durante la seconda guerra mondiale.
In quel periodo infatti, matematici e ingegneri furono incaricati di sviluppare modelli matematici e metodi per aiutare a prendere decisioni operative complesse e migliorare così l'efficienza delle azioni militari. Dopo la guerra, poi, questi strumenti matematici e modelli di calcolo furono applicati con successo a molte altre aree dello sviluppo civile, come la produzione industriale, la logistica, la pianificazione di trasporti, la gestione delle risorse, la finanza, eccetera. I primi passi per descrivere correttamente un problema di ottimizzazione consistono
nello scrivere una formula per decidere quanto buona o cattiva sia una possibile soluzione. Questa formula è chiamata funzione obiettivo. Nell'esempio del commesso viaggiatore, la funzione obiettivo quantifica, data una particolare soluzione, la distanza totale percorsa per visitare una lista ordinata di città. Tale funzione è quindi una sorta di bussola che permette a chi calcola le varie ottimizzazioni di capire se sta migliorando o peggiorando la soluzione individuata, in quanto lo scopo
dell'ottimizzazione è proprio quello di massimizzare o minimizzare la funzione obiettivo. In riferimento al TSPI, tanto per rimanere sempre sull'esempio del commesso viaggiatore, lo scopo è infatti quello di minimizzare la distanza per attraversare le varie città, mentre ad esempio nel caso del montaggio del macchinario l'obiettivo sarebbe quello di massimizzare il numero di linee produttive che possono lavorare in parallelo. In tutto questo discorso sono poi presenti anche degli elementi chiamati vincoli, cioè
delle regole che descrivono determinate condizioni da rispettare per considerare valida una soluzione. Tornando ancora una volta al TSPI, una soluzione è valida solo se visita tutte le città nella lista, oppure nell'esempio del carrello della spesa da riempire, un vincolo potrebbe essere quello di totalizzare almeno un certo quantitativo di calorie da consumare in un giorno. Insomma, i vincoli sono delle direttive da rispettare per non imbrogliare nell'elaborazione e soprattutto per trovare una soluzione che sia sensata e utile allo scopo reale prefissato.
Infine, l'ultimo elemento del problema è rappresentato dalle variabili, ovvero le varie scelte che si possono compiere per trovare una soluzione. Nel TSPI le variabili potrebbero ad esempio essere un numero per ogni città che rappresenta l'ordine di visita. Tutti questi che abbiamo descritto sono i vari elementi di base per la modellazione che permettono a matematici e informatici di rappresentare in maniera precisa e sintetica un problema di ottimizzazione. E partendo da tale modellazione si può notare un fatto molto
interessante e probabilmente controintuitivo. Cioè esistono problemi per i quali è molto complesso trovare una soluzione ma è paradossalmente molto semplice verificare se una data soluzione è corretta. Prendiamo ad esempio un insieme di numeri. Occorrono molti tentativi per trovarne tre che sommati diano come risultato un certo valore k, però una volta ottenuta una tripletta è invece molto semplice verificare se essa rappresenta una soluzione corretta o
meno. Questo tipo di asimmetria tra semplicità di verifica di una soluzione e complessità nel calcolarla tra le altre cose è un elemento fondante di quella disciplina alla base della sicurezza informatica nota come criptografia. Ma tornando al nostro TSP, nello scorso episodio ho erroneamente detto che non saremo in grado di verificare la soluzione adottata dalle api per spostarsi di fiore in fiore perché per noi è impossibile calcolare l'ottimo quando il numero di nodi è troppo elevato. Beh in realtà questo non è vero. Tramite infatti un complesso e geniale
metodo matematico chiamato algoritmo del simplesso è possibile trasformare il TSP in uno dei problemi appena descritti per i quali verificare se sia ottenuta la risposta corretta è un'operazione attuabile anche in un tempo relativamente contenuto. In secondo luogo poi sempre nello scorso episodio avevo detto che per trovare la soluzione del TSP è necessario elencare tutti i possibili cammini. Ma anche questa affermazione si è poi rivelata imprecisa. Infatti la realtà è
che alcuni cammini possono essere scartati grazie a dei ragionamenti per assurdo e ciò vuol dire che non è necessario esplorare ogni volta tutte le possibilità. Il nocciolo del ragionamento è essenzialmente nella definizione un cammino ottimo è composto da sottocammini ottimi. Il che nel concreto vuol dire che se sappiamo ad esempio che il cammino migliore per andare da Torino a Bari e partire dal Piemonte e attraversare le Milano Magna, le Marche, l'Abruzzo, il Molise e poi
raggiungere la Puglia. Se volessimo aggiungere una tappa che attraversa ad esempio l'Umbria non dovremmo provare ogni combinazione possibile dei percorsi perché sapremmo che ad esempio il sottopercorso migliore per andare dalle Marche alla Puglia rimarrebbe sempre attraversare l'Abruzzo e il Molise. Questa tecnica prende il nome di programmazione dinamica e consiste sostanzialmente nel riutilizzare i sottopercorsi ottimi di una soluzione che già avevamo calcolato
in precedenza. Grazie per aver ascoltato Snippet, una rubrica di Pensieri in Codice. Scopri tanti altri contenuti sul sito pensieriincodice.it
Quanto inquina una domanda fatta a un chatbot? In rete le risposte non mancano, ma quanto sono affidabili? In questo episodio della Community Edition Paola Zubani, consulente in ambito sostenibilità, ci accompagna tra...
Da quando lavoro con gli agenti di Intelligenza Artificiale, il mio Second Brain ha rischiato di morire: a cosa serve prendere appunti, se tanto la macchina sa già tutto? In questo episodio ti racconto perché invece è...
Per festeggiare i 150 episodi, stavolta al microfono non ci sono solo io: Nox, speaker artificiale di Runtime by Night, mi intervista per provare a raccontarti la vera anima di Pensieri in codice, tra idee da smontare,...
Oggi parliamo del legame tra tecnologia e memoria: come gli strumenti digitali cambiano il nostro modo di ricordare, come funziona la memoria umana e in cosa differisce da quella digitale. E sul finale una bella...
Oggi ti racconto la storia dell’Elea 9003, il primo calcolatore elettronico commerciale italiano: un’avventura tra Olivetti, ricerca, transistor e design che ha provato a portare l’Italia nel futuro dell’elettronica....