Euristica ammissibile

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

Definizione modifica

Detti:

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

la funzione   si dice ammissibile se:[2]

 

Algoritmi di ricerca modifica

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.[1]

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

 

dove:

  •   è il nodo corrente
  •   è il costo dal nodo di partenza a quello corrente;
  •   è 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  , 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.[2][3] Un'euristica consistente è un particolare tipo di euristica ammissibile, tale che, detto   un possibile nodo successore del nodo corrente   vale la seguente regola:[2]

 

Usando un'euristica consistente, la funzione   risulterà monotonicamente non decrescente.[4]

Esempi modifica

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

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 mal posizionata 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:

 

Dove:

  •   è la generica tessera,
  •   è la funzione distanza di Manhattan,
  •   è la posizione corretta di  .

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 è:

 

La distanza di Manhattan è un'euristica ammissibile poiché è minore o uguale al numero di volte per cui ogni tessera dovrà essere mossa.[5] 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.

Note modifica

  1. ^ a b c Russell-Norvig, p. 129.
  2. ^ a b c Russell-Norvig, p. 130.
  3. ^ "consistente" è un falso amico di consistent, lett. "coerente"
  4. ^ Russell-Norvig, p. 132.
  5. ^ Korf, 2000.

Bibliografia modifica

Voci correlate modifica

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica