Perché la mia euristica per l'algoritmo A * non è accettabile? - algoritmo, ricerca, intelligenza artificiale, una stella, euristica

Sto esaminando il CS 188 disponibile al pubblico all'indirizzo edx.org. Proprio ora devo sviluppare un'euristica per una ricerca A * per mangiare tutti i pellet come mostrato qui:

La mia euristica che ero sicuro avrebbe funzionato, (come sia ammissibile che coerente) è andata così:

• inizializza l'accumulatore euristico chiamato h per essere 0
• inizializza pos per essere la posizione corrente di pacman
• mentre il pellet non viene mangiato:
  • ottenere il pellet più vicino da pos usando la ricerca astar (distanza Manhattan come euristica)
  • aggiungi la distanza a h
  • rimuovere il pellet dai pellets
  • impostare pos per essere la posizione del pellet

Memorizzo anche le distanze precedentemente calcolate cosìla ricerca astar per trovare il pellet più vicino non è fatta se è già stata fatta prima in un altro calcolo di uno stato, è in grado di risolvere il problema molto rapidamente e il risultato è ottimale.

Quando uso questo algoritmo in autograder, fallisce il test di ammissibilità.

Non ti preoccupare, non ti sto chiedendo una soluzioneil problema, solo perché la mia attuale soluzione non è ammissibile? Quando passo l'esempio nella figura nella mia testa l'euristica non sta mai sopravvalutando il costo.

Quindi se qualcuno è stato in grado di capirlo, e ha qualche idea, il tuo contributo è molto apprezzato!

risposte:

Un'euristica per A * deve fornire un numero talenon è altro che il miglior costo possibile. La tua euristica è una soluzione avida plausibile che non garantisce questo. Supponiamo che ci sia una singola linea di pallini e che il pacman sia leggermente fuori centro su questa linea. La soluzione più economica è capire quale estremità della linea è più vicina, mangiare tutti i granuli fino alla fine di quella linea, e poi spostarsi nella direzione opposta per mangiare tutti gli altri pellet senza dover fare retromarcia nella metà più lunga della linea.

La tua golosa euristica si muove prima di tuttoil pellet è il più vicino al pac-man che potrebbe non essere il lato che ha la distanza più breve, quindi in questo caso potrebbe non restituire un costo non superiore al costo ottimale - restituisce il costo di una possibile soluzione che potrebbe non essere ottimale.

Ecco il modo di impostare l'euristica che è fattibileper il tuo problema. Innanzitutto, se il tuo obiettivo è quello di mangiare tutti i pellet in una distanza minima, la tua soluzione è troppo avida per ottenere una soluzione fattibile. Ecco il modo di ridisegnare la tua euristica: -

Obiettivo: mangiare tutti i pellet nella lunghezza minima del percorso.

Stima euristica:

1.> Utilizzare A * per calcolare indipendentemente tutti i percorsi più brevi dalla posizione corrente a pellet.

2.> Funzione costo: (somma di tutti i pellet non visitati percorso più breve da corrente) * 2 + distanza totale dallo stato iniziale.

La funzione di costo è il limite superiore.

Nota: ci può essere un modo più efficiente per calcolare i percorsi più brevi per i pallini non consumati in ogni stato. Avrebbe bisogno di qualche ricerca.