Euristica ammissibile

L'euristica ammissibile è una delle condizioni di ottimalità degli algoritmi di ricerca informata. L'euristica è detta ammissibile quando l'errore di previsione non è mai in eccesso. L'esempio classico di euristica ammissibile consiste nella misurazione del cammino tra diverse città. L'algoritmo di ricerca informata può stimare il costo del cammino tra le diverse città mediante la misurazione della distanza in linea d'aria tra le stesse. Tale previsione di costo è sempre in difetto (non è mai in eccesso) rispetto alla distanza reale tra le stesse poiché le strade non congiungono mai le città perfettamente in linea retta.

Dati due punti sul piano A e B, non esiste cammino inferiore alla linea retta che congiunge i due punti. In tal modo, la stima del costo di cammino "in linea d'aria" è sempre inferiore rispetto al costo del cammino effettivo (stradale). L'euristica ammissibile è una delle condizioni di ottimalità degli algoritmi di ricerca informata sugli alberi logici. L'errore assoluto, ossia la differenza tra il costo effettivo del cammino (distanza reale) e il costo stimato (distanza in linea d'aria) è sempre positivo.

Non sempre l'euristica è ammissibile. In alcuni problemi il costo cammino non può essere semplicemente stimato tramite la distanza geometrica in linea retta tra due punti. In tali casi l'euristica degli algoritmi di ricerca informata, come ad esempio la ricerca a stella, non è ottimale.

Consistenza euristica. L'euristica ammissibile è una condizione debole di ottimalità della ricerca informata. Nel caso della ricerca soluzioni in un grafo si ricorre alla condizione di consistenza euristica. La consistenza euristica ( monotonicità ) è considerata una condizione forte di ottimalità. Una euristica ammissibile può anche non essere consistente. Viceversa, una euristica consistente è anche un'euristica ammissibile.