Benvenuti in questa settima lezione della serie “Scuola Serale di Italian Geek“.
Queste brevi lezioni sono state progettate in modo tale da risultare volutamente sintetiche, dunque, per approfondimenti contattateci usando i commenti a fine articolo. Il codice presente nelle lezioni e’ funzionante ed e’ stato testato su compilatore gcc version 3.4.6 20060404 (Red Hat 3.4.6-9).
L’indice delle lezioni si trova qui.
Metodi euristici
I problemi reali sono sempre molto complessi e quasi mai e` possibile affrontarli e risolverli con un unico algoritmo. Normalmente e` necessario costruire un modello complesso in cui vari sottomodelli interagiscono fra loro. Alcuni di tali sottomodelli, possono essere di per se` difficili da risolvere e computazionalmente molto onerosi.
Quindi se il calcolo deve avvenire in tempi accettabili per potere prendere una decisione, e` necessario essere in grado di sviluppare metodi che, rinunciando “all’esattezza della soluzione”, hanno invece tempi di esecuzione piu` rapidi. Algoritmi che operano in tal senso, vengono detti algoritmi euristici o piu` semplicemente euristiche.
Vi sono algoritmi euristici che privilegiano soprattutto la velocita` di esecuzione, costruendo la soluzione con una semplice scansione lineare dei dati del problema. Questi algoritmi vengono definiti greedy. Normalmente gli algoritmi greedy producono soluzioni di bassa qualita`.
Algoritmi Greedy
In linea generale un algoritmo greedy costruisce una soluzione selezionando i suoi costituenti uno alla volta e senza mai ritornare sulle selezioni gia` fatte. L’ordine con cui i dati vengono presentati all’algoritmo e` basato su un criterio predefinito. Quindi tutta l’ingegnosita` di un metodo greedy risiede nel particolare criterio che presiede alla selezione e che deve essere definito in modo coerente con l’obiettivo del problema.
E` evidente che questo metodo produce una soluzione molto rapidamente, dato che viene richiesta una scansione lineare dei dati o al massimo un loro preliminare ordinamento. La velocita` di calcolo si paga pero` con soluzioni di qualita` molto bassa.
Tuttavia, dati i tempi molto rapidi di calcolo, non costa molto usare ripetutamente tale metodo, possibilmente con vari criteri alternativi. Di tutte le soluzioni calcolate si sceglie poi ovviamente la migliore.
Fra tutte le estensioni locali l’algoritmo sceglie la piu` conveniente. Ovvero quella estensione che sembra, almeno localmente, la piu` promettente per raggiungere una soluzione ottima. Uno schema generale per gli algoritmi greedy e` il seguente:
INPUT I (Istanza del problema)
S ← S0 (Soluzione parziale iniziale per I)
WHILE S puo` essere estesa DO
Trova l’estensione locale S0 di S piu` conveniente
S ← S0
ENDWHILE
OUTPUT S
Ovviamente questo schema non e’ una ricetta per costruire algoritmi greedy, ma e` solamente una descrizione di cio` che si intende per algoritmo greedy. E` chiaro infatti che ci sono molti dettagli, tutt’altro che marginali, che lo schema non tenta di specificare.
Di seguito i link per scaricare il pdf della lezione ed 1 file con il codice sorgente di esempio.
Download
- Lezione 7: Algoritmi Greedy
- greedy.c
La lezione precedente è stata sulle Tabelle Hash
Il prossimo appuntamento e’ per Venerdi’ 9 Dicembre 2011.
Alla prossima!
Puoi seguire Massimo Orazio Spata, l’autore di questo post, su Twitter.
Sei veramente bravo in qualcosa e desideri condividere questa conoscenza con gli altri? Stiamo cercando collaboratori per creare altri corsi nella Scuola Serale di Italian Geek. Se sei interessato, scrivici all’indirizzo:[email protected]
Articoli Simili:
- Impara a Programmare, Lezione 2: Algoritmi di ordinamento: Insertion Sort e Counting Sort
- Impara a Programmare: Guida alla programmazione di Algoritmi e Strutture Dati Avanzate in C
- Impara a Programmare, Lezione 1: Le Liste in C
Pacman
Nostradamus
Magical Cat Adventure
Snake