Algoritmo euristico: differenze tra le versioni

Versione delle 17:17, 17 giu 2008

Versione delle 22:37, 13 dic 2008

Riga 1:

'''Algoritmo euristico''' ( o ''[[euristica]]''): in [[matematica]] e [[informatica]] è un particolare tipo di [[algoritmo]] (cioè procedimento) la cui [[soluzione]] non è la soluzione [[ottima]] per quel dato [[problema]]. Nonostante questo, possiamo affermare che costituisce spesso una strada obbligata per risolvere problemi molto difficili (ad es.esempio quelli [[NP-difficile|NP-Hard]]) come l' [[Problema del commesso viaggiatore|Algoritmo del commesso viaggiatore]], in quanto per determinate dimensioni delle istanze l'algoritmo euristico riesce a ricavare una soluzione approssimativamente molto vicina a quella ottima. Nonostante tale proprietà non si possa verificare sistematicamente né 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.

== Esempi di algoritmi euristici ==

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

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

[[Categoria:Algoritmi]]

[[Categoria:Ricerca operativa]]