In generale, l'euristica è un modo di dare priorità a certi percorsi di calcolo rispetto ad altri quando si cerca la soluzione di un problema.
Il tuo calcolo può essere visto come trovare un percorso dallo stato iniziale del tuo algoritmo allo stato finale (dove viene calcolata la soluzione del problema). Su quel percorso, ci sono molti stati interni e si passa da uno all'altro.
Ora, come si fa a sapere quale percorso scegliere se ci sono più scelte possibili da uno stato ad altri stati? Idealmente, vorresti sapere esattamente quale stato devi scegliere in modo che l'intero percorso sia ottimale (e se il tuo algoritmo ha la proprietà dell'ottimo locale, allora sei a posto). Ma molte volte semplicemente non si sa; si va alla cieca attraverso lo spazio degli stati nella speranza di trovare lo stato finale, per così dire.
In tali situazioni, si potrebbe scegliere di impiegare l'euristica. Cioè si sceglie lo stato successivo basandosi su qualche "ipotesi educata", una sorta di argomentazione razionalmente supportata, che potrebbe non essere sempre corretta, ma generalmente aumenterà la probabilità che ci si muova verso lo stato finale.
È difficile spiegare l'euristica in generale perché gli approcci differiscono molto a seconda del problema. Vi faccio un esempio:
Problema del cavaliere degli scacchi: data una scacchiera di dimensioni n per n e una posizione iniziale [p, q] sulla scacchiera, trovare un percorso del pezzo del cavaliere attraverso la scacchiera in modo che visiti ogni campo esattamente una volta.
Ora, tali problemi sono spesso risolti usando il backtracking. Si dovrebbe semplicemente muovere il cavaliere, seguendo uno schema fisso, segnando ogni campo che passa e ricordando il percorso che ha fatto. Se non può passare oltre, si "scarta" la mossa precedente e si fa invece quella successiva nello schema. In questo modo, alla fine, proverete tutti i percorsi possibili. Alcuni di essi possono essere soluzioni valide al problema.
Ora, ho implementato questo algoritmo nel mio primo anno all'Università, circa 20 anni fa. L'ho eseguito sul mio PC 486; una macchina piuttosto lenta, ma poiché la quantità di percorsi possibili aumenta molto velocemente con l'aumentare delle dimensioni della scacchiera, i risultati saranno più o meno applicabili anche oggi. Così, per una scacchiera di dimensioni 5x5, la soluzione è stata trovata quasi istantaneamente. 6x6, decine di secondi, se ricordo bene. 7x7, un paio d'ore, ma sì... 8x8-overnight e ancora nessuna soluzione.
Così, proviamo qualche euristica. Il 1° tentativo che ho provato è stato quello di provare sempre la mossa da cui c'era il maggior numero di mosse possibili. Questo ha senso, giusto? Andrò dove ho più possibilità di continuare... Ha funzionato per la scacchiera 8x8, la soluzione è stata trovata in mezz'ora o qualcosa del genere, ma anche per la 9x9, di nuovo, nessuna fortuna durante la notte.
Allora, proviamo qualcosa di folle. Proviamo a scegliere la mossa da cui ci sono meno mosse possibili. Non ha senso, vero? Perché dovrei preferire il percorso che probabilmente è sbagliato? Beh, si scopre che questa euristica funziona brillantemente. Sul 486, la scacchiera 25x25 non era un problema, la prima soluzione trovata in una frazione di secondo, le altre seguivano molto rapidamente, il contatore correva e correva...
Perché? Beh, dirigendo il cavaliere verso i campi da cui aveva il minor numero di mosse possibili, abbiamo ristretto la larghezza del sottoalbero di mosse che poteva fare da quello stato. Poiché la profondità di quell'albero è limitata (da n volte n, il numero dei campi della scacchiera), il numero di stati in quel sottoalbero diminuisce rapidamente. Quindi testerete un sottoalbero stretto molto più velocemente di uno largo. Se c'è almeno una soluzione in quel sottoalbero stretto, la troverete rapidamente.
Quindi quello che abbiamo fatto qui è stato: abbiamo deliberatamente scelto di preferire certi calcoli (quelli con meno stati) contro altri e li abbiamo provati per primi. Arriveremmo comunque alle altre se la soluzione non venisse trovata; alla fine, tutti i percorsi possibili sarebbero stati provati. Ma selezionando saggiamente le mosse locali, si possono evitare molti vicoli ciechi.
E così funziona l'euristica.