ALGORITMO GREEDY
Un algoritmo greedy tenta di
costruire una soluzione ottima partendo
da una soluzione parziale iniziale ed estendendola a poco a poco fino a quando
questo non è più possibile.
Quando l’algoritmo tenta di estendere una soluzione parziale non lo fa
considerando tutte le possibili estensioni (che potrebbero essere
numerosissime) ma solamente quelle che chiamiamo estensioni locali. Le
estensioni locali di una soluzione parziale rappresentano in qualche modo le
più piccole estensioni possibili e sono relativamente poche. Fra tutte le
estensioni locali l’algoritmo sceglie la più conveniente. Ovvero quella
estensione che sembra, almeno localmente, la più promettente per raggiungere una soluzione
ottima.
Fonti:
