Euristica

Sento che questi sono difficili da definire per me, quindi inizierò con la riga di apertura di Wikipedia sull’argomento:

In informatica, intelligenza artificiale, e di ottimizzazione matematica, una funzione euristica (dal greco εὑρίσκω “io trovare, scoprire”) è una tecnica progettata per risolvere un problema di più rapidamente quando i metodi classici sono troppo lento, o per trovare una soluzione approssimata quando i metodi classici non riescono a trovare alcuna soluzione esatta. Ciò si ottiene scambiando ottimalità, completezza, accuratezza o precisione per velocità. In un certo senso, può essere considerato una scorciatoia.

È utile? Hai capito? Perche ‘ non capisco. Voglio dire, un po ‘ lo capisco, ed è una descrizione accurata, ma se questa fosse la prima volta che hai mai sentito parlare di un’euristica, non sono sicuro che tu possa ottenere il quadro completo di cosa sono le euristiche da questo. Forse se ti parlo solo dell’euristica di pathfinding di A*, otterrai una migliore comprensione.

Con l’algoritmo di Dijkstra, il focus era su un valore: la distanza più breve dall’indice di partenza. Il che, se ci pensi, è un po ‘ strano. Hai questo algoritmo che cerca di trovare nuovi percorsi più brevi verso una destinazione, ma il suo focus è sempre su dove è iniziato. Immagina qualcuno che va a fare la spesa, ma cammina all’indietro per tutta la strada, cercando di tenere d’occhio la loro casa fino a quando non arrivano al negozio. Nella vita reale, questo probabilmente non avrebbe funzionato, ma forse se hai dato loro il tempo di andare in tutta la città, alla fine potrebbe funzionare.

Andando fuori da questa stupida analogia, A* è diverso da Dijkstra perché suggerisce di girarsi e camminare in avanti. A*, come Dijkstra, tiene anche traccia di quanto lontano da casa è, ma la sua caratteristica unica è che tiene traccia di quanto è lontano dalla sua destinazione, anche. Quando si effettua il passo successivo, Dijkstra esaminerà quale percorso è attualmente il più breve, ma A * fa un ulteriore passo avanti e considera anche se quel passo lo sta avvicinando al suo obiettivo. Più semplicemente, A * ha una stima approssimativa della sua distanza rimanente dal suo obiettivo, e quando quella stima si avvicina a zero, sa che si sta muovendo nella giusta direzione. Questa è l’euristica che useremo nei nostri esempi.

Passando attraverso l’algoritmo

Questo sarà un esempio piuttosto semplice, ma dovrebbe mostrare il flusso di base e la ripetizione dell’algoritmo. Mi assicurerò di fornire collegamenti nei miei riferimenti ad altri esempi più complicati, ma questo dovrebbe essere un buon primer per quelli. Io uso un set-up simile a come ho dimostrato Dijkstra s.

Un’altra differenza tra Dijkstra e A* è che Dijkstra inizia immediatamente il loop, ma A* deve fare un po ‘ di set-up per il suo vertice iniziale. Quindi facciamolo ora, e avere un po ‘ di un’idea di come il tavolo sta andando a lavorare.

in Primo luogo, aggiungiamo Un per il set Aperto. Secondo, scopriremo la distanza di A dall’inizio. Naturalmente, la distanza da A ad A è zero, quindi verrà aggiunto al tavolo, e avrò che sia il numero nell’angolo in alto a sinistra del quadrato di A. Terzo, determineremo la distanza euristica. Possiamo farlo in molti modi, l’importante è misurare questa distanza allo stesso modo per ogni quadrato. Userò una distanza” in linea d’aria ” per tutte le distanze euristiche, il che significa che posso usare di nuovo il Teorema di Pitagora. In questo caso, calcoleremo √(202 + 302) e scopriremo che A è una distanza di 36.0555127546 from da L (arrotonderò le cifre decimali al decimo più vicino per risparmiare spazio). Aggiungerò questo al tavolo e lo posizionerò nell’angolo in alto a destra del quadrato di A. Infine, la somma. Aggiungerò la distanza più breve dall’inizio alla distanza euristica, la aggiungerò al tavolo e la posizionerò al centro del quadrato di A.

Questo è il nostro punto di partenza, e ora possiamo guardare i vicini di A e aggiungere i loro valori alla tabella.

in Primo luogo, aggiungiamo B, E, e F per Aprire il set. Quindi, possiamo trovare le loro distanze più brevi dall’inizio, e poiché tutto è a un passo dall’inizio, sarà solo 10 per B ed E, e 14 per la diagonale mossa a F. Per la distanza euristica, useremo il Teorema di Pitagora da ogni quadrato al vertice finale. Infine, otterremo le loro somme e aggiungeremo ” A ” a ciascuna delle loro precedenti colonne dei vertici.

A questo punto, abbiamo fatto tutto il necessario con A, quindi verrà spostato nel set chiuso e avremo bisogno di un nuovo vertice corrente. Per determinare quale vertice dovrebbe essere esaminato successivamente, esamineremo il set aperto e troveremo il vertice che ha la somma più bassa. In questo momento, questo è F con una somma di 36.1. Quindi, lo renderemo il vertice corrente e inizieremo a elaborare i valori per i suoi vicini.

F ha otto vicini, ma solo cinque sono andando essere modificata. In primo luogo, A è nel set chiuso ora, quindi non può essere cambiato ora. Per i restanti sette, li aggiungeremo al set aperto (a meno che non ne facciano già parte), quindi lavoriamo sulle loro distanze dall’inizio. Questo funzionerà molto come l’algoritmo di Dijikstra, e aggiungeremo la distanza di F dall’inizio a ciascuna distanza dei suoi vicini da F. Sul nostro tavolo, la distanza di F dall’inizio è 14, quindi compileremo 14+10=24 o 14+14=28 per questi. Tuttavia, B ed E hanno già distanze più brevi all’inizio, quindi i loro record di tabella non vengono aggiornati. Ciò lascia cinque vertici che verranno aggiornati, con C, I e K che ottengono 28 e G e J che ottengono 24 per la loro distanza dall’inizio. Quindi, utilizzare il Teorema di Pitagora per ciascuna delle distanze euristiche di questi vertici, quindi calcolare le loro somme e infine aggiungere “F” alla colonna vertice precedente per i vertici che sono stati aggiornati.

F è completo e verrà spostato nel set chiuso e verrà scelto un nuovo vertice corrente in base a quale vertice nel set aperto ha la somma più bassa. È molto vicino, ma K è un decimo più piccolo (E sì, questo è a causa di una differenza di arrotondamento, ma in questo caso, risulta essere un buon tie breaker). K sarà il nuovo vertice da esaminare, quindi iniziamo guardando i suoi vicini.

K ha sei vicini di casa, di cui tre già nel set Aperto, in modo che gli ultimi due H e L sarà aggiunto all’Aperto pure. Ora, calcoleremo le loro distanze dall’inizio. La distanza di K dall’inizio è 28, quindi lavoreremo con 28+10=38 per G, J e L e 28+14=42 per H. Tuttavia, G e J hanno già distanze più piccole per iniziare, quindi non verranno aggiornate. Troveremo le distanze euristiche per ciascuno, calcoleremo le loro somme e aggiungeremo ” K ” a ciascun vertice precedente che è stato aggiornato.

K è completo e spostato nel set chiuso, e il vertice successivo all’aperto con la somma più piccola è L, la nostra destinazione!

Ora, che L è l’attuale vertice, l’algoritmo termina, e possiamo usare il nostro tavolo per tracciare il percorso per tornare all’inizio:

• L precedente vertice K
• K precedente vertice F
• F’ precedente vertice è A, il vertice di partenza.

Quindi, questo significa che il percorso più breve è un >F >K > L.

Analizzando i risultati

Rispetto all’algoritmo di Dijkstra, A* ha lasciato un bel casino dietro di esso. Diamo un’occhiata ad alcuni punti dispari. Partendo, guarda il vertice C e la sua distanza dall’inizio: 28. Sembra strano perché A e C sono solo due mosse orizzontali l’una dall’altra, quindi la distanza più breve dovrebbe essere 20. In questo momento, C sembra pensare che il suo percorso più breve verso A sia di due mosse diagonali attraverso F.

Quando l’algoritmo di Dijkstra termina, dovrebbe fornire una tabella molto completa di distanze dal punto di partenza. Al contrario, la tabella di A * ha valori errati e manca completamente il vertice D. Ma ha ottenuto la stessa risposta che avrebbe avuto Dijkstra, e lo ha fatto molto più velocemente. Dijkstra avrebbe voluto guardare tutti i 12 vertici prima di dichiarare che ha trovato il percorso più breve; A* aveva solo bisogno di guardare 4 prima di trovare la strada giusta. Questo cambiamento di velocità è dovuto all’euristica che stavamo usando: tutte le volte che potevamo, volevamo chiudere la distanza con la nostra destinazione. Se torniamo alla definizione di Wikipedia per l’euristica, A* ha scambiato la completezza per la velocità.

Proviamo un altro piccolo esempio, ma con un’ostruzione sulla strada per la destinazione.

il punto di Partenza è il vertice in alto a sinistra, e Un* sta cercando di trovare il percorso più breve per il vertice in basso a destra. I quadrati neri rappresentano una lacuna nel grafico e non possono essere attraversati. Se A * sta seguendo la sua euristica di “avvicinarsi sempre alla destinazione”, quei quadrati neri lo porteranno in un vicolo cieco.

A questo punto, Un* vi aspetto per le più piccole somme, quali saranno le piazze sotto e a destra del vertice di partenza. A * esplorerà entrambi i percorsi, ma il percorso verso il basso si imbatterà in un altro vicolo cieco, e il percorso verso destra troverà un modo per aggirare i quadrati neri. Potrebbe essere un po ‘ diverso da questo, ma supponiamo che questo sia il modo in cui A* ha gestito questo scenario. Anche quando è stato tirato in vicoli ciechi, è stato in grado di tornare indietro e trovare un altro percorso, e non ha avuto bisogno di guardare ogni vertice (il vertice in alto a destra è stato saltato di nuovo). Ciò significa che quando una stella * è in esecuzione al suo peggio assoluto, è fondamentalmente veloce come le normali prestazioni di Dijkstra. Ogni algoritmo ha casi d’uso perfettamente validi, ma in termini di pathfinding e ricerca dei percorsi più brevi, A* è la scelta migliore.