Euristica ammissibile

In informatica, un'euristica ammissibile è una funzione euristica che non sovrastima mai il costo effettivamente necessario per raggiungere l'obiettivo. Intuitivamente, una funzione ammissibile è "ottimistica", in quanto sottostima sempre il costo effettivo.

Definizione

Detti:

• $n$ la variabile indicante il nodo corrente nel contesto di una ricerca su un grafo,
• $h(n)$ una funzione euristica usata per stimare il costo, a partire da $n$, per arrivare al nodo finale,
• $c(n)$ il costo effettivo, a partire da $n$, per arrivare al nodo finale,

la funzione $h(n)$ si dice ammissibile se:

$h(n)\leq c(n)\ \forall n$

Algoritmi di ricerca

Le euristiche ammissibili sono usate negli algoritmi di ricerca per stimare quanto costa raggiungere lo stato corrispondente all'obiettivo prefissato. Per essere considerata ammissibile, il risultato di una funzione euristica deve essere sempre (indipendentemente dallo stato considerato) minore o uguale al costo effettivamente necessario per raggiungere l'obiettivo.

Se un algoritmo di ricerca per alberi usa un'euristica ammissibile, allora è ottimale.

Per esempio, nell'A* la funzione di valutazione è:

$f(n)=g(n)+h(n)$

dove:

• $n$ è il nodo corrente
• $g(n)$ è il costo dal nodo di partenza a quello corrente;
• $h(n)$ è il costo stimato dal nodo corrente all'obiettivo.

Usando un'euristica non ammissibile, l'algoritmo A* potrebbe trascurare la soluzione ottimale, a causa di una sovrastima di $f(n)$, giungendo a una soluzione sotto-ottimale.

Per un algoritmo di ricerca su grafi è invece necessaria una condizione leggermente più stringente. Gli algoritmi di ricerca su grafi sono infatti ottimali se basati su euristiche consistenti (falso amico per consistent, lett. "coerente"). Un'euristica consistente è un particolare tipo di euristica ammissibile, tale che, detto $n'$ un possibile nodo successore del nodo corrente $n$ vale la seguente regola:

$h(n)-h(n')\leq c(n,n')\ \forall (n,n')$

Usando un'euristica consistente, la funzione $f(n)$ risulterà monotonicamente non decrescente.

Esempi

Due esempi differenti di euristiche ammissibili possono essere applicati al gioco del quindici:

• distanza di Hamming
• distanza di Manhattan

La distanza di Hamming può essere usata per indicare il numero totale di tessere posizionate erroneamente. Un'euristica di questo tipo è intuitivamente ammissibile, in quanto il numero totale di mosse per disporre le tessere correttamente è sicuramente maggiore o uguale al numero di tessere aventi posizione errata (ogni tessera malposizionata deve essere mossa almeno una volta). Di conseguenza, il costo—espresso in numero di mosse—per arrivare all'obiettivo è maggiore o uguale alla distanza di Hamming.

La distanza di Manhattan può essere usata per indicare il numero di mosse (secondo la geometria del taxi) che separano ogni tessera dalla sua posizione corretta. La funzione euristica può quindi essere definita come segue:

$h(n)=\sum _{t}d({\text{t, p(t)}})$

Dove:

• $t$ è la generica tessera,
• $d()$ è la funzione distanza di Manhattan,
• $p(t)$ è la posizione corretta di $t$.

La tabella seguente rappresenta una specifica istanza del gioco del quindici con tessere non ordinate:

43	61	30	81
72	123	93	144
153	132	14	54
24	101	111

I pedici mostrano la distanza di Manhattan di ciascuna tessera. La distanza totale per questa specifica istanza è:

$h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36$

La distanza di Manhattan è un'euristica ammissibile poiché è minore o uguale al numero di volte per cui ogni tessera dovrà essere mossa. Infatti, ogni tessera dovrà essere mossa per un numero di volte maggiore o uguale al numero di passi che sarebbero necessari per arrivare alla posizione corretta se la tessera in questione potesse muoversi senza modificare la posizione delle altre.

Bibliografia

• S.J. Russell e P. Norvig, Intelligenza artificiale. Un approccio moderno, traduzione di Stefano Gaburri, 2ª ed., Prentice Hall, aprile 2005, ISBN 88-7192-228-X.
• (EN) Richard E. Korf, Recent Progress in the Design and Analysis of Admissible Heuristic Functions (PDF), vol. 1864, Springer, 2000, pp. 45–55, DOI:10.1007/3-540-44914-0_3. URL consultato il 26 aprile 2010.

Voci correlate

• Funzione euristica
• Algoritmo di ricerca
• Rilassamento (approssimazione)