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 ^[1]^[2]. 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 ^[3] 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

Note

↑ Judea Pearl, Heuristics: intelligent search strategies for computer problem solving, collana The Addison-Wesley series in artificial intelligence, Reprinted with corr, Addison-Wesley, 1985, ISBN 978-0-201-05594-8.
↑ Stuart J. Russell e Peter Norvig, 3. Risolvere i problemi con la ricerca, in Intelligenza artificiale. Un approccio moderno., traduzione di S. Gaburri, vol. 2, Pearson, 2021, ISBN 9788891904461.
↑ Michael J. Apter, The Computer Simulation of Behaviour, collana Routledge Library Editions: Artificial Intelligence Ser, Routledge, 2018, ISBN 978-1-351-02100-5.

Altri progetti

Wikimedia Commons contiene immagini o altri file sull'algoritmo euristico

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

[1] Judea Pearl, Heuristics: intelligent search strategies for computer problem solving, collana The Addison-Wesley series in artificial intelligence, Reprinted with corr, Addison-Wesley, 1985, ISBN 978-0-201-05594-8.

[2] Stuart J. Russell e Peter Norvig, 3. Risolvere i problemi con la ricerca, in Intelligenza artificiale. Un approccio moderno., traduzione di S. Gaburri, vol. 2, Pearson, 2021, ISBN 9788891904461.

[3] Michael J. Apter, The Computer Simulation of Behaviour, collana Routledge Library Editions: Artificial Intelligence Ser, Routledge, 2018, ISBN 978-1-351-02100-5.

[1]

[2]

[3]