Distanza euristica ammissibile a Manhattan

Question

Recentemente ho iniziato un corso introduttivo all'intelligenza artificiale e mi è stato assegnato un incarico per implementare una funzione euristica ammissibile in Python che risolva il 15-Puzzle con la ricerca A *.

Ho implementato la Manhattan Distance insieme ad altre euristiche. Il codice Python funzionava bene e l'algoritmo in realtà risolve il problema, ma ho qualche dubbio sul fatto che l'euristica a distanza di Manhattan sia ammissibile per questo particolare problema.

Secondo la teoria di un'euristica è ammissibile se maisovrastima il costo per raggiungere l'obiettivo. Ciò significa che l'euristica è ottimista e il costo che ritorna non è mai maggiore di quello attuale.

Quando lo stato iniziale è la seguente (0 significa slot vuoto):

1 2 3 4 
0 6 7 8 
5 9 10 12 
13 14 11 15 

mio programma risolve il problema con 5 movimenti, ma la somma del Manhattan distanze di ogni piastrella fuori luogo è pari a 10 che è il doppio del valore del costo effettivo. Quindi il costo reale è molto inferiore a quello stimato. Questo significa che l'euristica non è ammissibile o c'è qualcosa di sbagliato nella mia logica?

Ho pensato di contare solo la distanza di Manhattan del blocco vuoto, ma questo porterebbe a stati con costi stimati pari a zero quando il blocco vuoto si trova nella sua posizione corretta, ma le altre tessere non sono posizionate correttamente.

Answer 1

L'euristico Manhattan Distance è ammissibile in quanto considera ciascuna piastrella in modo indipendente (mentre in effetti le tessere interferiscono l'una con l'altra). Quindi è ottimista.

Nell'esempio la somma della distanza dalla posizione obiettivo di tutte le tessere è 5 (le tessere 5, 9, 10, 11, 15 ne richiedono una ciascuna).