En matemàtiques, un algorisme voraç és un algorisme que, per resoldre un problema d'optimització, fa una seqüència d'eleccions, prenent a cada pas un òptim local,, pàgina 125. amb l'esperança (no sempre acomplerta), pàgina 199. d'arribar a un òptim global. L'algorisme voraç no torna mai enrere per reavaluar les eleccions ja preses.
Esquema Tot algorisme voraç conté el següent:, pàgines 135-136. Un conjunt no infinit de candidats, de possibles solucions (parcials o totals) del problema, Una funció de selecció, que ens permet seleccionar el millor dels candidats, Una funció de factibilitat, que ens permet avaluar si el candidat ajuda a resoldre el problema, Una funció solució, que avalua si el conjunt de candidats seleccionats soluciona el problema (totalment o parcialment).
Exemples miniatura|Un algorisme voraç determina el mínim nombre de monedes al tornar un canvi. Aquests són els pasos que qualsevol persona fa emulant un algorisme voraç per obtenir els 36 cèntims utilitzant monedes només de {1, 5, 10, 20} cèntims.
Un exemple típic és el de tornar un canvi amb el mínim de monedes de determinat valor. A la dreta es pot veure com s'escullen les monedes per tornar un canvi de 36 cèntims. El conjunt de candidats és {20, 10, 5, 1}, la funció de selecció és escollir sempre la de valor més alt, la funció de factibilitat és no superar mai els 36 cèntims amb els candidats escollits, la funció solució és aconseguir 36 cèntims.
Els algorismes voraços no garanteixen sempre una solució, ni que la solució obtinguda sigui l'òptima. En l'exemple anterior, si el conjunt de candidats hagués sigut {50, 20, 10, 5, 2}, l'algorisme no retornaria cap solució perquè en arribar a 35 cèntims {20+10+5} no tindria cap candidat que ajudés a resoldre el problema. En canvi, és obvi que existeix una solució amb {20+10+2+2+2}. En general, l'algorisme voraç produeix sempre una solució quan el conjunt de candidats té estructura de matroide., pàgines 370 i 393 i ss., pàgina 148., pàgina 200.
Altres exemples són el de minimitzar el recorregut que ha de fer un viatjant de comerç per visitar una sèrie de clients distanciats entre ells (vegeu algorisme de Dijkstra), pàgines 137 i següents. o el d'empaquetar objectes de diferents volums en el mínim nombre de caixes idèntiques., pàgina 197.
Referències
Bibliografia
Vegeu també Algorisme de Huffman Algorisme de Dijkstra Algorisme heurístic
Enllaços externs
Categoria:Algorismes