Nell’ipotesi che P ≠ NP (vedi l’articolo P è uguale a NP?), purtroppo per alcuni problemi di ottimizzazione non esistono algoritmi di risoluzione efficienti. Eppure, come spesso accade in matematica, la loro formulazione è talvolta così semplice da non far immaginare la difficoltà che vi si nasconde. Prendiamo, per esempio, il celebre problema del commesso viaggiatore: dato un insieme di città, quale percorso di lunghezza minima consente di visitarle tutte e di tornare al punto di partenza? Malgrado la sua semplicità, non esiste alcun algoritmo che permetta di risolvere efficacemente questo problema: persino il migliore richiederebbe un tempo che cresce esponenzialmente con il numero di città. Che fare quando si vuole risolvere in un tempo «accettabile» (dell’ordine di qualche minuto) un problema «di grandi dimensioni» (del tipo di quelli che si incontrano nella pratica)?
Le euristiche… -----------------
La prima soluzione consiste nell’uso di euristiche (dal greco heuriskein, che significa «trovare»). Lo scopo di un’euristica è trovare una soluzione che rispetti i vincoli del problema e sia «di buona qualità» secondo il criterio di ottimizzazione considerato. La soluzione non sarà necessariamente ottimale, ma un’euristica efficace cerca di trovarne una di buona qualità entro il tempo di risoluzione assegnato.
Per esempio, per il problema del commesso viaggiatore, l’euristica del vicino più prossimo è semplice: si sceglie come prossima città da visitare quella per cui la distanza dalla città corrente è minima, e si procede così fino ad aver visitato tutte le città. Si torna poi alla prima città visitata, ottenendo un percorso (o circuito). Questa euristica è rapida, ma in pratica dà risultati piuttosto scarsi: nulla garantisce infatti che l’ultima città visitata sia «vicina» alla prima, il che può produrre un percorso finale lungo e penalizzante.