- Attuale
- In coda
- Definitivo
- Percorso
- Stima in linea d'aria
Ricerca A*
La ricerca A* trova un percorso più breve da una partenza a un arrivo, come l'algoritmo di Dijkstra, ma sa più o meno dove si trova l'arrivo. Ogni nodo riceve una stima della distanza rimanente, la linea d'aria fino all'arrivo, e la ricerca prosegue sempre dal nodo con la minore distanza finora più quella stima. Fai clic su un nodo per partire da lì, scegli un arrivo e procedi passo per passo per vedere la ricerca puntare verso l'arrivo e lasciare intatti interi angoli del grafo. Premi Avvia per guardare la ricerca, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Fai clic su un nodo per farne la partenza; passa il clic su Arrivo e fai clic su un altro nodo per farne l'arrivo. Il numero su ogni arco è la sua lunghezza, il numero su ogni nodo la sua distanza finora, e la linea tratteggiata la stima in linea d'aria della distanza rimanente. La riga sotto il grafo è la coda, a partire dal punteggio più basso, con il punteggio di ciascuno: la distanza finora più la stima. Nuovo grafo crea un altro grafo; scegli quanti nodi e archi deve avere. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Fai clic su un nodo per farne la partenza. Passa il clic su Arrivo e fai clic su un altro nodo per farne l'arrivo.
- Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto della ricerca.
- Osserva i punteggi in coda e la stima in linea d'aria tratteggiata. Alla fine, confronta i nodi che sono serviti ad A* con quelli dell'algoritmo di Dijkstra.
Come funziona la ricerca A*
Dai alla partenza distanza 0 e mettila in una coda. Ogni nodo in coda ha un punteggio: la sua distanza finora più una stima della distanza rimanente. Ripeti: prendi il nodo con il punteggio più basso e rendi definitiva la sua distanza. Se è l'arrivo, fermati. Altrimenti, per ogni vicino non definitivo, aggiungi la lunghezza dell'arco alla distanza del nodo; se è minore della distanza finora del vicino, abbassala, ricorda il nodo come via per arrivarci e metti il vicino in coda con il suo nuovo punteggio.
Perché la stima non deve mai essere troppo lunga
A* trova un percorso più breve finché la stima non dice mai che l'arrivo è più lontano di quanto sia davvero: una stima ammissibile. La linea d'aria lo è, perché nessuna strada tra due luoghi è più corta della linea d'aria. Una stima troppo lunga può far saltare ad A* il percorso migliore; una stima di 0 ovunque trasforma A* nell'algoritmo di Dijkstra, che è sicuro ma cerca in tutte le direzioni. Migliore è la stima, meno nodi servono ad A*. Nell'app ogni arco è lungo quanto è disegnato, arrotondato per eccesso, quindi la linea d'aria è una stima sicura.
Domande frequenti
Che cos'è la ricerca A*?
Un algoritmo di pathfinding che trova un percorso più breve da una partenza a un arrivo. Funziona come l'algoritmo di Dijkstra, ma ordina la coda per distanza finora più una stima della distanza rimanente, così punta verso l'arrivo invece di allargarsi in tutte le direzioni.
Che cos'è un'euristica ammissibile?
Una stima della distanza dall'arrivo che non è mai più lunga della vera distanza minima. Con una stima ammissibile, A* trova sempre un percorso più breve. La distanza in linea d'aria su una mappa è l'esempio classico.
A* è più veloce dell'algoritmo di Dijkstra?
Di solito sì, quando ti serve la via verso un solo arrivo e hai una buona stima: A* rende definitivi meno nodi, perché i nodi lontani dall'arrivo ricevono punteggi alti. Con una stima di 0 fa esattamente ciò che fa l'algoritmo di Dijkstra. L'algoritmo di Dijkstra è la scelta migliore quando ti servono le distanze verso tutti i nodi.
Dove si usa A*?
Nei videogiochi per muovere i personaggi attorno agli ostacoli, nei navigatori, nella pianificazione dei movimenti dei robot e nei risolutori di rompicapi come il gioco del 15 (15-puzzle), dove la stima conta quanto le tessere sono lontane dal loro posto.
Il mio grafo viene inviato da qualche parte?
No. Il grafo viene creato e visitato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor