Il computer, il genio e la forza bruta

Un problema banale, che nemmeno i calcolatori più potenti riescono a risolvere in un tempo ragionevole. La matematica combinatoria, severa, fissa i limiti della tecnologia attuale e futura. E ci insegna ad usare il cervello al posto della forza bruta.



[ZEUS News - www.zeusnews.it - 22-07-2003]

Karim lavora per un corriere espresso: con il suo furgone consegna pacchi e buste per conto di un'organizzazione avanzatissima dal punto di vista telematico ed informatico. Ogni giorno deve consegnare un certo numero, facciamo 20 oggetti in 20 indirizzi diversi, per cui avrà da percorrere un circuito, con partenza ed arrivo nel magazzino, formato da 20+1 tappe. Karim è un tipo pignolo: gli è saltato il ticchio di chiedere la sequenza ottimale, quella che può fargli risparmiare tempo, benzina, gomme, etc. Ma quell'antipatico del ragioniere gli ha risposto picche. Perchè?

Quello di Karim è un esempio del Traveller Salesman Problem, o TSP, un problema che è considerato difficile, perchè ad oggi non si conosce un algoritmo polinomiale (collegato polinomialmente alla dimensione n del problema, e quindi veloce) che possa risolverlo. Se volesse risolvere il problema, la ditta dovrebbe per prima cosa, e già qui non sarebbe facile, munirsi di una tabella enorme riportante le distanze tra ogni via della città e tutte le altre. Se rappresentiamo ogni tappa di Karim con una lettera dell'alfabeto, un esempio di percorso, detto ciclo hamiltoniano, può essere il seguente:

abcdefghijklmnopqrstua,

che sarà diverso, per esempio, da

abcdefghijklmnopqrsuta,

se associamo ad ogni passaggio di lettera la distanza tra gli indirizzi estratta dal tabellone di cui sopra, e le sommiamo, possiamo associare ad ogni percorso possibile la distanza totale da percorrere, e quindi indirettamente il suo costo. Il metodo di soluzione cosiddetto della "forza bruta" consiste nell'analisi di ciascun percorso possibile, nel calcolo del suo costo, e nel confronto tra queste soluzioni possibili, alla ricerca di quella minore, e quindi ottima.

Quanti percorsi dovranno essere analizzati? Il loro numero è 20! (venti fattoriale), cioè 20x19x18x17... x ...3x2x1. il risultato è 243290200817640000. Detto così non sembra un granchè. Per chi mastica di crittografia e sicurezza, corrisponde circa a trovare una password composta da 8 caratteri da 8 bit, cioè password del tipo µ2«K<+;E.

Dunque, un calcolatore, con un processore di ultima generazione, col clock ad almeno un paio di gigahertz, equipaggiato con un software velocissimo, come AZPR, può analizzare fino a 30 milioni di combinazioni al secondo.

Per trovare la soluzione ottima, questa combinazione hardware-software impiegherà:

81.096.733.606 secondi,

cioè 1.351.612.227 minuti,

cioè 22.526.870 ore,

quindi 938.619 giorni,

perciò 2.571 anni e mezzo.

Questi sono i limiti della forza bruta: di fronte ad un problema così banale la best available technology dell'umanità va in crisi.

Naturalmente esistono algoritmi più efficienti, esiste la possibilità di collegare più elaboratori e farli lavorare contemporaneamente, e grazie a questo si può ampliare la dimensione del problema risolvibile in tempi decenti. Ma la sostanza non cambia: alcuni tipi di problemi, anche con dimensioni attorno al 50, non solo non sono praticamente risolvibili attraverso gli attuali computer, ma si può ragionevolmente supporre che non lo saranno mai, qualunque sia il progresso futuro della velocità dei calcolatori.

Ma l'inventiva umana, il genio, ci viene in soccorso. Come? Primo, accontentandosi: può essere agevole trovare soluzioni sub-ottimali, e queste sono spesso soddisfacenti. Secondo, cercando algoritmi più efficienti, tipo gli euristici, magari basati su interessanti interazioni col mondo della biologia, come quelli genetici o l'affascinante Ant Colony Optimization, che ricava un algoritmo dal comportamento apparentemente caotico delle formiche. Terzo, provando a rovesciare gli attuali paradigmi tecnologici: il calcolatore digitale ci intristisce? Proviamo con quello quantistico: per esso esistono già algoritmi efficienti a risolvere problemi ex-difficili (ottima documentazione disponibile anche su ZEUSNews).

Ma non è tutto: talvolta la matematica, quando ci mostra percorsi logici che possono essere utilizzati al di fuori di essa, ci insegna a vivere. Quando le variabili in gioco sono molte, un problema puramente combinatoriale come quello di Karim, assomiglia molto ai piccoli e grandi crucci della vita reale, come la droga, il terrorismo, la tutela dei diritti d'autore, gli insetti che infestano la mia albizia. In questi casi, può essere utile trarre insegnamento dalla teoria: la forza bruta difficilmente porta alla soluzione.

Se questo articolo ti è piaciuto e vuoi rimanere sempre informato con Zeus News ti consigliamo di iscriverti alla Newsletter gratuita. Inoltre puoi consigliare l'articolo utilizzando uno dei pulsanti qui sotto, inserire un commento (anche anonimo) o segnalare un refuso.
© RIPRODUZIONE RISERVATA

Commenti all'articolo (ultimi 5 di 8)

kensan
Bell'articolo! Leggi tutto
23-7-2003 17:18

Vanni
Elementi finiti Leggi tutto
23-7-2003 13:24

Pinatubo
Human kind Leggi tutto
23-7-2003 12:50

Guerino Giancola
Segnalazione Leggi tutto
23-7-2003 10:01

Lele2k
Troppi ragionamenti inutili... Leggi tutto
23-7-2003 09:16

La liberta' di parola e' un diritto inviolabile, ma nei forum di Zeus News vige un regolamento che impone delle restrizioni e che l'utente e' tenuto a rispettare. I moderatori si riservano il diritto di cancellare o modificare i commenti inseriti dagli utenti, senza dover fornire giustificazione alcuna. Gli utenti non registrati al forum inoltre sono sottoposti a moderazione preventiva. La responsabilita' dei commenti ricade esclusivamente sui rispettivi autori. I principali consigli: rimani sempre in argomento; evita commenti offensivi, volgari, violenti o che inneggiano all'illegalita'; non inserire dati personali, link inutili o spam in generale.
E' VIETATA la riproduzione dei testi e delle immagini senza l'espressa autorizzazione scritta di Zeus News. Tutti i marchi e i marchi registrati citati sono di proprietà delle rispettive società. Informativa sulla privacy. I tuoi suggerimenti sono di vitale importanza per Zeus News. Contatta la redazione e contribuisci anche tu a migliorare il sito: pubblicheremo sui forum le lettere piu' interessanti.
Sondaggio
Con quale delle seguenti affermazioni, tutte relative a siti che vendono coupon e buoni sconto online, concordi di pi? (Se vuoi dare risposte multiple utilizza i commenti)
Sono un cliente abituale dei siti di coupon e in generale posso dichiararmi soddisfatto delle promozioni attivate tramite questo mezzo innovativo.
Apprezzo i coupon soprattutto per provare quelle strutture dove non sono mai stato, o servizi che non ho mai utilizzato prima.
Acquisto talvolta i coupon ma purtroppo molte volte non riesco a utilizzarli prima della loro scadenza, pertanto penso di diminuire questa attivit o di continuare a farlo saltuariamente.
Acquisto i coupon soprattutto per usufruire dello sconto e raramente acquisto nuovamente un servizio o torno in una struttura a "prezzo pieno".
Solitamente acquisto un coupon soltanto se conosco gi la struttura o il servizio offerto, non voglio fregature.
Mi capitato spesso di prendere delle fregature o di non essere servito alla stregua degli altri clienti, pertanto penso che non acquister pi coupon.
Non ho mai acquistato un coupon.

Mostra i risultati (1597 voti)
Ottobre 2019
Il sistema operativo per sopravvivere all'Apocalisse
Pegasus, la nuova interfaccia di Windows 10
Dal papà di Android uno smartphone radicalmente diverso
Otto mesi di carcere per chi rivelò gli stipendi d'oro sindacali
Windows, l'aggiornamento impedisce di stampare
Antibufala: la Tesla della polizia rimasta a secco durante un inseguimento
Esplode lo smartphone in carica, muore ragazzina
Settembre 2019
Windows, l'aggiornamento di ottobre mette il turbo al Pc
Tutta la verità sul caso del dominio Italia Viva
Ecco perché gli aggiornamenti Windows hanno così tanti bug
A che età dare lo smartphone ai propri figli?
Usa NULL come targa pensando di beffare il sistema informatico delle multe
Gli USA scaricano Huawei e sui portatili arriva Linux Deepin
Falla nelle SIM, vulnerabili 1 miliardo di telefoni
La Francia non vuole Libra in Europa
Tutti gli Arretrati


web metrics