Algoritmo euristico: differenze tra le versioni

Versione delle 16:31, 22 nov 2013

Versione attuale delle 18:19, 25 mar 2023

(16 versioni intermedie di 8 utenti non mostrate)

Riga 1:

{{F|programmazione|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, quelliin [[NP-difficile|NP-Hard]])caso comedi ilelevata [[problema del commessocomplessità viaggiatorecomputazionale]],) in quantoo per determinatetrovare dimensioniuna dellesoluzione istanzeapprossimata, l'algoritmonel euristicocaso riescein acui ricavarei unametodi soluzioneclassici approssimativamentefalliscano moltonel vicinatrovare auna quellasoluzione ottimaesatta. NonostanteIl talerisultato proprietàviene nonottenuto sicercando possadi verificareequilibrare sistematicamentegli néobiettivi adi priorimaggiori ottimizzazione, sicompletezza, trattaaccuratezza spessoe velocità 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;

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

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

== Esempi di algoritmi euristici ==

* 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]]

* [[Problema dellodel zaino#Algoritmocommesso Greedyviaggiatore|Algoritmo risolutivo del Problema dellodel commesso zainoviaggiatore]]

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

* [[Algoritmo di Kernighan-Lin]]

== Altri progetti ==

[[Categoria:Algoritmi]]

{{Interprogetto|preposizione=sull'}}

{{portale|informatica}}

[[Categoria:Algoritmi|Euristico]]

[[Categoria:Ricerca operativa]]