L’euristica della distanza di Manhattan è probabilmente l’euristica più usata nella ricerca euristica, di sempre. Introdotta informalmente negli anni ’60 per il 15-puzzle, formalizzata nel paper A* del 1968, è ancora la prima cosa che ogni libro di IA insegna. Questo articolo riguarda perché funziona, cosa fa bene e dove smette di bastare.
La definizione
Per un puzzle scorrevole N×N, per ogni tessera (ignora il vuoto), calcola:
distance = | row_current − row_goal | + | col_current − col_goal |
Somma su tutte le tessere. Quella somma è la distanza di Manhattan della griglia attuale dall’obiettivo.
Perché "Manhattan"? Le strade di Manhattan sono una griglia regolare. Per andare da un angolo all’altro, cammini tot isolati est-ovest più tot isolati nord-sud. Non puoi tagliare in diagonale. Il numero totale di isolati percorsi è la distanza di Manhattan — chiamata anche distanza del taxi o norma L¹.
Per una tessera, la stessa logica: può muoversi orizzontalmente o verticalmente di una cella per mossa, ma non in diagonale. Il numero minimo di mosse per portarla da dove è a dove deve andare è la distanza in riga più la distanza in colonna.
Ammissibilità
A* richiede che l’euristica sia ammissibile: non deve mai sovrastimare il numero effettivo di mosse rimanenti. Se l’euristica sovrastima, A* potrebbe troncare presto il percorso ottimale e restituire una soluzione sub-ottimale.
La distanza di Manhattan è ammissibile perché:
- Ogni singola tessera deve viaggiare almeno la sua distanza in riga + distanza in colonna, perché le mosse sono passi unitari in riga o in colonna.
- Sommare su tutte le tessere non può sovrastimare, perché ogni mossa fa avanzare esattamente una tessera di esattamente una cella. (Muove anche il vuoto, ma non lo stiamo contando.)
- In effetti, la distanza vera è almeno la distanza di Manhattan perché le tessere devono spesso essere spostate da parte per lasciarne passare altre — ma mai meno.
Quindi Manhattan ≤ effettivo. Ammissibile.
Consistenza
Una proprietà più forte: la consistenza, talvolta chiamata monotonia dell’euristica. Un’euristica è consistente se, per ogni stato s e ogni successore s' tramite mossa m:
h(s) ≤ cost(m) + h(s')
In italiano: il valore dell’euristica non può scendere di più di uno quando fai una mossa.
La distanza di Manhattan è consistente perché una singola mossa cambia la distanza di Manhattan esattamente di +1 o −1. (Una tessera si muove di una cella, quindi il suo contributo all’euristica cambia di ±1; i contributi di tutte le altre tessere rimangono invariati.)
La consistenza conta perché garantisce che A* non riapra mai uno stato che ha già chiuso. Le implementazioni non devono gestire il caso di inconsistenza, il che semplifica codice e dimostrazioni.
Perché funziona così bene in pratica
Tre proprietà concrete:
È economica da calcolare. O(N²) per griglia — somma su tutte le tessere, ogni contributo a tempo costante. Calcolare h(s) richiede microsecondi su qualsiasi computer moderno.
È abbastanza stretta da potare in profondità. Per i 15-puzzle, il valore dell’euristica di Manhattan è in media il 75–90% della distanza vera. A* con un’euristica così stretta esplora una piccola frazione dello spazio degli stati.
Si combina bene con il conflitto lineare. Aggiungere 2 mosse per ogni "conflitto lineare" (due tessere nella stessa riga, entrambe appartengono a quella riga, ma in ordine errato) dà un’euristica strettamente più stretta a costo computazionale marginale.
Dove non basta
La distanza di Manhattan tratta le tessere come se potessero attraversarsi liberamente. Non possono. Il punto cieco più profondo:
Conflitti in una colonna o riga. Se le tessere 2 e 3 sono entrambe nella riga 1 ma in ordine errato, Manhattan dà loro le distanze in linea retta e non nota nulla. In realtà una di esse deve essere sollevata fuori dalla riga, l’altra fatta passare, e la prima rimessa. Sono almeno 2 mosse extra che Manhattan non vede. Il conflitto lineare corregge questo.
Struttura di "walking". Manhattan ignora come le tessere si relazionino tra loro all’interno di una riga o colonna quando tutte appartengono a quella riga o colonna. Una riga di quattro tessere in permutazione errata richiede più "scambi di riga" — una struttura che la walking distance cattura.
Interazioni di sottoinsiemi disgiunti. Per qualsiasi partizione disgiunta delle tessere, il costo ottimale di permutare ciascuna partizione in posizione è un limite inferiore più stretto di Manhattan (che è la partizione in singletons). I database di pattern additivi sfruttano questo.
La progressione è: Manhattan → Manhattan + conflitto lineare → walking distance → database di pattern. Ciascuno è un miglioramento netto.
Perché le griglie più grandi richiedono di più
La distanza di Manhattan è in media circa il 75–90% della distanza vera per il 15-puzzle. Per il 24-puzzle, è in media circa il 65%. Per il 35-puzzle, circa il 55%.
Il motivo: man mano che le griglie crescono, i conflitti tra tessere e la "walking structure" diventano più importanti rispetto alle distanze in linea retta. La distanza di Manhattan, che ignora entrambe, sottostima in modo più grave sulle griglie più grandi.
È per questo che i database di pattern sono essenzialmente obbligatori per la risoluzione del 24-puzzle e del 35-puzzle. L’euristica di Manhattan va bene per il 15-puzzle e l’8-puzzle ma perde troppe informazioni a dimensioni più grandi.
Intuizione geometrica
Un bel modo di pensare alla distanza di Manhattan: immagina un piano con una tessera che ci sta sopra. L’insieme dei punti che la tessera può raggiungere in k mosse è un rombo di lato k — punti a distanza di Manhattan ≤ k. (L’equivalente euclideo sarebbe un cerchio di raggio k.)
La distanza di Manhattan è la geometria naturale della locomozione su griglia. Quando hai un modello di movimento vincolato a passi su griglia, la distanza di Manhattan è la geometria; la distanza euclidea è irrilevante.
Cosa significa per gli sviluppatori di app
Se stai scrivendo un pulsante suggerimento per un’app di puzzle scorrevoli e vuoi che funzioni in millisecondi:
- 3×3 — Manhattan + conflitto lineare è più che sufficiente. A* esplora decine di stati; finisce in microsecondi.
- 4×4 — Manhattan + conflitto lineare è abbastanza veloce per un suggerimento (una mossa, non la soluzione ottimale completa). Per la soluzione ottimale completa, la walking distance è la scelta giusta.
- 5×5+ — Database di pattern. Manhattan non basta a stare dentro il budget di tempo di un pulsante suggerimento.
Slide Puzzle usa Manhattan + conflitto lineare per il pulsante suggerimento del 3×3 e del 4×4, walking distance per la calibrazione della difficoltà 4×4, e un database di pattern 5+5+5+9 per la calibrazione 5×5 e 6×6. L’euristica di Manhattan è la fondazione di tutti questi.
Un’intuizione finale
L’euristica della distanza di Manhattan è ciò che rende i puzzle scorrevoli ricercabili in primo luogo. Senza di essa, A* e IDA* degenererebbero in BFS — e BFS non finisce sul 15-puzzle nell’arco della vita dell’universo.
Quell’euristica è la singola riga di codice che trasforma un problema intrattabile in un calcolo da millisecondi. Vale la pena capirla bene.