Un * euristico, sopravvalutazione / sottovalutazione?

Question

Sono confuso riguardo ai termini sopravvalutazione / sottostima. Capisco perfettamente come funziona l'algoritmo A *, ma non sono sicuro degli effetti di un'euristica che sopravvaluta o sottostima.

La sovrastima è quando si prende il quadrato della linea diretta del birdview? E perché renderebbe l'algoritmo errato? La stessa euristica viene utilizzata per tutti i nodi.

La sottostima è sottovalutata quando si prende la squareroot della linea diretta birdview-line? E perché l'algoritmo è ancora corretto?

Non riesco a trovare un articolo che lo spieghi bene e in modo chiaro, quindi spero che qualcuno qui abbia una buona descrizione.

Answer 1

Stai sopravvalutando quando la stima dell'euristica è superiore al costo effettivo del percorso finale. Stai sottovalutando quando è più basso (non devi sottovalutare, devi solo non sopravvalutare; le stime corrette vanno bene). Se i costi del bordo del grafico sono tutti 1, gli esempi forniti forniranno sopravvalutazioni e sottostime, anche se la distanza delle coordinate piane funziona anche in uno spazio cartesiano.

La sopravvalutazione non rende esattamente l'algoritmo "errato"; ciò significa che non hai più un euristico ammissibile , che è una condizione affinché A * sia garantito per produrre un comportamento ottimale. Con un'euristica inammissibile, l'algoritmo può finire facendo tonnellate di lavoro superfluo esaminando i percorsi che dovrebbe essere ignorato e probabilmente trovando percorsi non ottimali a causa dell'esplorazione di quelli. Se ciò si verifica effettivamente dipende dallo spazio del problema. Succede perché il costo del percorso è "non congiunto" con il costo stimato, che essenzialmente fornisce all'algoritmo idee confuse su quali percorsi sono migliori di altri.

Non sono sicuro che l'avrai trovato, ma potresti voler consultare Wikipedia Un * articolo . Cito (e collegamento) principalmente perché è quasi impossibile per Google per questo.

Answer 2

Dal Wikipedia A * articolo , la parte rilevante della descrizione dell'algoritmo è:

  

L'algoritmo continua fino a quando un nodo obiettivo ha un valore f inferiore rispetto a qualsiasi nodo nella coda (o finché la coda non è vuota).

L'idea chiave è che, con sottostima, A * smetterà di esplorare un potenziale percorso verso l'obiettivo solo dopo aver saputo che il costo totale del percorso supererà il costo di un percorso noto verso l'obiettivo. Poiché la stima del costo di un percorso è sempre inferiore o uguale al costo reale del percorso, A * può scartare un percorso non appena il costo stimato supera il costo totale di un percorso noto.

Con la sopravvalutazione, A * non ha idea di quando può smettere di esplorare un potenziale percorso in quanto possono esserci percorsi con un costo effettivo inferiore ma un costo stimato più elevato rispetto al percorso attualmente più conosciuto verso l'obiettivo.

Answer 3

Per quanto ne so, in genere devi sottovalutare in modo da poter trovare ancora il percorso più breve. Puoi trovare una risposta più rapidamente sopravvalutando, ma potresti non trovare il percorso più breve. Ecco perché la sopravvalutazione è "errata", mentre la sottovalutazione può comunque fornire la soluzione migliore.

Mi dispiace di non essere in grado di fornire informazioni dettagliate sulle righe del birdview ...

Answer 4

Risposta breve

La risposta di @chaos è un po 'fuorviante imo (può essere evidenziata)

  

La sopravvalutazione non rende esattamente l'algoritmo "errato"; ciò significa che non hai più un euristico ammissibile, che è una condizione affinché A * sia garantito per produrre un comportamento ottimale. Con un'euristica inammissibile, l'algoritmo può finire facendo tonnellate di lavoro superfluo

come @AlbertoPL sta suggerendo

  

Puoi trovare una risposta più rapidamente sopravvalutando, ma potresti non trovare il percorso più breve.

Alla fine (oltre all'ottimale matematico), la soluzione ottimale dipende fortemente dal fatto che si considerino risorse di calcolo, tempo di esecuzione, tipi speciali di "Mappe" / Spazi di stato, ecc.

Risposta lunga

Ad esempio, potrei pensare a un'applicazione in tempo reale in cui un robot si avvicina più rapidamente all'obiettivo utilizzando un'euristica sopravvalutata perché il vantaggio temporale avviato partendo prima è maggiore del vantaggio temporale prendendo il percorso più breve ma aspettando più a lungo per calcolare questo soluzione.

Per darti un'idea migliore, condivido alcuni risultati esemplari che ho creato rapidamente con Python. I risultati derivano dallo stesso algoritmo A *, solo l'euristica differisce. Ogni nodo (cella della griglia) ha bordi per tutti e otto i vicini tranne i muri. I bordi diagonali costano sqrt (2) = 1,41

La prima immagine mostra i percorsi restituiti dell'algoritmo per un semplice esempio. Puoi vedere alcuni percorsi non ottimali dall'euristica sopravvalutata (rosso e ciano). D'altra parte ci sono più percorsi ottimali (blu, giallo, verde) e dipende dall'euristica quale si trova per prima.

Le diverse immagini mostrano tutti i nodi espansi quando viene raggiunta la destinazione. Il colore mostra il costo del percorso stimato usando questo nodo (considerando anche il percorso "già preso" dall'inizio a questo nodo; matematicamente è il costo finora più l'euristica per questo nodo). In qualsiasi momento l'algoritmo espande il nodo con il costo totale stimato più basso (descritto in precedenza).

1. Zero (blu)

• Corrisponde all'algoritmo Dijkstra
• Nodi espansi: 2685
• Lunghezza percorso: 89.669

2. In linea d'aria (giallo)

• Nodi espansi: 658
• Lunghezza percorso: 89.669
• https://i.stack.imgur.com/75eFV.png

3. Ideale (verde)

• Percorso più breve senza ostacoli (se si seguono le otto direzioni)
• Stima più alta possibile senza sopravvalutare (quindi "ideale")
• Nodi espansi: 854
• Lunghezza percorso: 89.669
• https://i.stack.imgur.com/VqMtF.png

4. Manhattan (rosso)

• Percorso più breve senza ostacoli (se non ti muovi in ??diagonale; in altre parole: il costo di "muoversi in diagonale" viene stimato come 2)
• sovrastima
• Nodi espansi: 562
• Lunghezza percorso: 92.840
• https://i.stack.imgur.com/gD9t4.png

5. Mentre il corvo vola dieci volte (ciano)

• sovrastima
• Nodi espansi: 188
• Lunghezza percorso: 99.811
• https://i.stack.imgur.com/SZuFH.png