L’algoritmo che si corregge da solo

(Sapienza Università di Roma) – La risoluzione di problemi matematici complessi rappresenta da sempre uno degli obiettivi principali della scienza. Un recente articolo apparso sulla prestigiosa rivista Nature Communications a firma di Raffaele Marino, Giorgio Parisi e Federico Ricci-Tersenghi, gli ultimi due professori del dipartimento di Fisica della Sapienza, presenta un nuovo algoritmo numerico per la risoluzione di difficili problemi in cui si tenti di trovare la combinazione ottimale di un grande numero di variabili che soddisfino contemporaneamente un numero enorme di vincoli. Questi problemi compaiono in molte discipline scientifiche e campi di applicazione pratica, come la moderna crittografia e il design e la verifica dei circuiti integrati nei microchip. In questi casi, essendo il numero dei vincoli per variabile molto grande tanto da rendere quasi impossibile venire a capo del problema, la ricerca delle poche soluzioni valide diventa un compito estremamente complesso.

Tanto per dare un idea della difficoltà alla base di questi problemi, si consideri che il numero di possibili combinazioni da esplorare è talmente grande che solo per essere scritto richiederebbe quasi un milione di cifre! Al confronto, il numero di atomi in tutto l’universo è minuscolo, visto che si può scrivere con meno di 100 cifre.

L’algoritmo proposto in questo lavoro (battezzato “backtracking survey propagation”) assegna le variabili del problema un po’ alla volta sulla base delle informazioni raccolte in una procedura dinamica detta di message passing. Ogni variabile fa una stima del valore che dovrebbe assumere per risolvere il problema e “passa” questa informazione alle variabili accanto. Alla fine di questo processo è molto probabile che alcune variabili abbiano capito (con un buon livello di confidenza) quale sia il giusto valore da assumere per risolvere il problema in questione: allora queste variabili vengono assegnate a tale valore dall’algoritmo.

In aggiunta, il nuovo algoritmo permette anche di tornare indietro, nel caso in cui sia stato commesso un errore, liberando alcune variabili già assegnate. Questa fase di backtracking è estremamente utile al fine di aggiustare errori commessi nella prima parte dell’assegnazione, permettendo così 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 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 Ricci Tersenghi.

Riferimenti: “The backtracking survey propagation algorithm for solving random K-SAT problems”, Raffaele Marino, Giorgio Parisi e Federico Ricci-Tersenghi, Nat. Commun. 7, 12996 (2016) doi: 10.1038/ncomms12996