Algoritmo euristico: differenze tra le versioni

Versione delle 02:31, 18 feb 2013

Versione attuale delle 18:19, 25 mar 2023

(21 versioni intermedie di 13 utenti non mostrate)

Riga 1:

{{F|informaticaprogrammazione|febbraio 2013}}

'''[[Algoritmo]] euristico''' (o ''[[euristica]]''): in [[matematica]] e [[informatica]] è un particolare tipo di [[algoritmo]] (cioè procedimento) la cui soluzione non è la soluzione ottimaprogettato per quelrisolvere datoun [[problema]]. Nonostantepiù questovelocemente, possiamonel affermarecaso chein costituiscecui spessoi unametodi stradaclassici obbligatasiano pertroppo risolverelenti probleminel molto difficilicalcolo (ad esempio, in caso di quellielevata [[NP-difficile|NP-Hardcomplessità computazionale]]) comeo l'[[Problemaper deltrovare commessouna viaggiatore|algoritmosoluzione delapprossimata, commessonel viaggiatore]],caso in quantocui peri determinatemetodi dimensioniclassici dellefalliscano istanzenel l'algoritmo euristico riesce a ricavaretrovare una soluzione approssimativamenteesatta. moltoIl vicinarisultato aviene quellaottenuto ottima.cercando Nonostantedi taleequilibrare proprietàgli nonobiettivi sidi possamaggiori verificare sistematicamente né aottimizzazione, prioricompletezza, siaccuratezza trattae spessovelocità di una soluzione disponibile in tempi ragionevoliesecuzione.

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 possibili motivi:

* La risoluzione del problema ottimo può essere impossibile;

L'euristica è un approccio di risoluzione dei problemi molto diffuso nella [[simulazione]] per vari possibili motivi tra cui:

* La risoluzione del problema ottimo può essere troppo costoso in termini di tempo o di capacità di elaborazione.

* Lala risoluzione ottimale del problema ottimo può essere impossibile;

* Lala risoluzione ottimale del problema ottimo può essere troppo costosocostosa in termini di tempo o di capacità di elaborazione.

== Esempi di algoritmi euristici ==

* [[Problema del commesso viaggiatore|Algoritmo risolutivo del Problema del commesso viaggiatore]]

* [[Problema dello zaino#Algoritmo Greedy|Algoritmo risolutivo del Problema dello zaino]]

* [[Algoritmo di Kernighan-Lin]]

== Altri progetti ==

{{Interprogetto|preposizione=sull'}}

{{portale|informatica}}

[[Categoria:Algoritmi|Euristico]]

* [[Problema del commesso viaggiatore|Algoritmo del commesso viaggiatore]]

* [[Problema dello zaino#Algoritmo Greedy|Problema dello zaino]]

[[Categoria:Algoritmi]]

[[Categoria:Ricerca operativa]]