Algoritmo euristico: differenze tra le versioni

Versione delle 23:24, 19 ott 2013

Versione delle 22:36, 9 nov 2013

Riga 1:

{{F|informatica|febbraio 2013}}

'''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 esempio quelli [[NP-difficile|NP-Hard]]) come l'il [[Problema del commesso viaggiatore|algoritmoproblema 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:

Riga 8:

== Esempi di algoritmi euristici ==

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

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

* [[Algoritmo di Kernighan-Lin]]