In informatica, uneuristica 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: 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:
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 è:
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.."consistente" è un falso amico di consistent, lett. "coerente" Un'euristica consistente è un particolare tipo di euristica ammissibile, tale che, detto un possibile nodo successore del nodo corrente vale la seguente regola:
Usando un'euristica consistente, la funzione risulterà monotonicamente non decrescente..
Esempi Due esempi differenti di euristiche ammissibili possono essere applicati al gioco del quindici: distanza di Hamming distanza del taxi
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 del taxi può essere usata per indicare il numero di mosse che separano ogni tessera dalla sua posizione corretta. La funzione euristica può quindi essere definita come segue:
Dove: è la generica tessera, è la funzione distanza del taxi, è 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 del taxi di ciascuna tessera. La distanza totale per questa specifica istanza è:
La distanza del taxi è 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.
Note
Bibliografia
Voci correlate Funzione euristica Algoritmo di ricerca Rilassamento (approssimazione)
Categoria:Intelligenza artificiale