Algoritmo euristico
Algoritmo euristico (o euristica): in matematica e informatica è un particolare tipo di algoritmo progettato per risolvere un problema più velocemente, nel caso in cui i metodi classici siano troppo lenti nel calcolo (ad esempio, in caso di elevata complessità computazionale) o per trovare una soluzione approssimata, nel caso in cui i metodi classici falliscano nel trovare una soluzione esatta. Il risultato viene ottenuto cercando di equilibrare gli obiettivi di maggiori ottimizzazione, completezza, accuratezza e velocità di esecuzione.
I metodi euristici costituiscono spesso una strada obbligata per risolvere problemi molto difficili (ad esempio quelli di tipo NP-difficile) come il problema del commesso viaggiatore, in quanto per determinate dimensioni delle istanze l'algoritmo euristico riesce a ricavare una soluzione approssimativamente vicina a quella ottima. Nonostante tale proprietà non si possa verificare sistematicamente a priori, si tratta spesso di una soluzione disponibile in tempi ragionevoli.
L'euristica è un approccio di risoluzione dei problemi molto diffuso nella simulazione per vari motivi tra cui:
- la risoluzione ottimale del problema può essere impossibile;
- la risoluzione ottimale del problema può essere troppo costosa in termini di tempo o di capacità di elaborazione.
Esempi di algoritmi euristici
[modifica | modifica wikitesto]- Algoritmo risolutivo del Problema del commesso viaggiatore
- Algoritmo risolutivo del Problema dello zaino
- Algoritmo di Kernighan-Lin
Altri progetti
[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file sull'algoritmo euristico
