Algoritmi su Grafi
Ricerca del percorso minimo: Dijkstra, A* e BFS a confronto
Una demo funzionante di quattro algoritmi di ricerca su grafi, con pesi reali, topografia e rotte marittime. Vedi come si comportano in modo diverso sullo stesso percorso.
Trovare il percorso minimo tra due nodi in un grafo è uno dei problemi fondamentali dell'informatica. Lo stesso codice che risolve questo problema su una mappa italiana alimenta i navigatori GPS, i sistemi di consegna, i motori di raccomandazione, i videogiochi. Questa demo mostra quattro implementazioni reali, a confronto sullo stesso grafo.
Ogni algoritmo è scritto da zero, senza librerie esterne: strutture dati, coda di priorità, euristica di distanza, tutto visibile nel comportamento. La rete include rilievi topografici e penali di costo reali, non solo distanza in linea d'aria.
I quattro metodi a confronto
Ogni metodo affronta il problema in modo diverso. Alcuni garantiscono sempre il percorso migliore, altri rinunciano alla certezza in cambio di velocità. Usare quello giusto dipende dal contesto: quanto è grande la rete? Quanto conta la precisione? Hai un'idea di dove si trova la destinazione?
Dijkstra
Cerca in tutte le direzioni e garantisce sempre il percorso più corto. Preciso ma più lento su reti grandi perché non usa informazioni sulla posizione della destinazione.
A* (A-star)
Come Dijkstra, ma si orienta verso la destinazione usando la distanza in linea d'aria. Più veloce senza perdere la garanzia di trovare il percorso ottimale.
Ricerca in Ampiezza
Esplora livello per livello, partendo dalle città vicine. Funziona bene quando tutti i collegamenti hanno lo stesso costo, ma non tiene conto delle distanze reali.
Greedy Best-First
Va sempre verso ciò che sembra più vicino all'arrivo. Veloce, ma può sbagliarsi sul percorso reale perché ignora il costo dei tratti già percorsi.
Cosa impari guardando questa demo
- Perché alcuni metodi trovano sempre il percorso migliore e altri possono sbagliare
- Come il costo di ogni tratto stradale cambia completamente il risultato finale
- La differenza tra esplorare in modo sistematico e puntare direttamente all'obiettivo
- Quanto lavoro fa il programma: quante città visita prima di arrivare alla soluzione
- Perché un metodo più "intelligente" non è sempre quello che esplora meno
Come usare la demo
Seleziona una città di partenza e una di arrivo dalla mappa. Scegli il metodo di ricerca dal menu. Premi Play per vedere l'animazione automatica, oppure Step per avanzare un passo alla volta e osservare ogni singola decisione del programma.
Prova a eseguire più metodi sullo stesso tragitto: vedrai città diverse colorate durante l'esplorazione, percorsi finali di lunghezza diversa, e un contatore che mostra quante tappe sono state visitate prima di trovare la soluzione.
Questi concetti si usano ogni giorno nello sviluppo professionale
Vuoi un metodo per applicarli sul tuo codice reale, con un architetto senior al tuo fianco?
Prova la demo
Seleziona partenza e arrivo, scegli il metodo e osserva. Usa Play per l'animazione automatica o Step per avanzare manualmente.
Drag: pan
Alt + mouse: tilt 3D
Clic nodo: alterna start/end