Scienza: individuato l’algoritmo matematico che si autocorregge

MeteoWeb

La risoluzione di problemi matematici complessi è da sempre uno degli obiettivi principali della scienza. Lo sanno bene anche i ricercato della Sapienza che, attraverso uno studio pubblicato su Nature Communications, hanno individuato un algoritmo matematico in grado di autocorreggersi in caso di errore. L’articolo, firmato da Raffaele Marino, Giorgio Parisi e Federico Ricci-Tersenghi, presenta un nuovo algoritmo numerico che permetterà di risolvere difficili problemi, nei quali si tenta di trovare la combinazione ottimale di un grande numero di variabili che soddisfino contemporaneamente un numero enorme di vincoli.

Si tratta di problemi molto frequenti nelle diverse discipline scientifiche e con campi di applicazione pratici. Permetterà infatti la risoluzione di problemi complessi anche alla base di crittografia moderna e design e la verifica di circuiti integrati nei microchip. Nei casi pratici, poiché il numero dei vincoli per variabile  è molto grande, tanto da render la soluzione quasi impossibile, riuscire a discernere le poche soluzioni valide diventa un compito estremamente complesso. Per far comprendere meglio la portata della difficoltà, basti pensare che il numero di possibili combinazioni da esplorare è così grande che per essere scritto sarebbero necessarie quasi un milione di cifre! Un numero maggiore persino al numero di atomi in tutto l’universo, che può essere scritto con meno di 100 cifre.

Nel lavoro proposto, l’algoritmo (battezzato “backtracking survey propagation”) assegna un po’ per volta le variabili sulla base delle informazioni raccolte attraverso una procedura dinamica definita di message passing. Ogni variabile fa dunque una stima del valore che dovrebbe assumere per risolvere il problema e trasferisce questa informazione alle variabili successive. A fine processo è molto probabile che alcune variabili abbiano trovato il giusto valore da assumere per risolvere il problema in questione: queste variabili vengono dunque assegnate a tale valore dall’algoritmo.

Oltretutto, il nuovo algoritmo permette anche di tornare indietro, in caso di errori, in modo da liberare alcune variabili già assegnate. Questa fase di backtracking è estremamente utile al fine di ottenere dei risultati più precisi, permettendo al nuovo algoritmo di risolvere problemi di ottimizzazione con decine di milioni di vincoli, molto vicino alla soglia critica. “Gli algoritmi basati sul message passing sono al momento di gran lunga i più efficienti per risolvere questi problemi, ma hanno il difetto che spesso ci si rende conto solo verso la fine di aver fatto degli errori nelle assegnazioni iniziali.” spiega il professor Parisi. “Il nostro nuovo algoritmo riesce a capire quali siano le variabili che conviene sbloccare per migliorare le scelte iniziali sbagliate. Con questo nuovo algoritmo riusciamo a risolvere problemi che prima risultavano intrattabili” aggiunge il professor Ricci Tersenghi.