From Wikipedia, the free encyclopedia
En matemàtiques, un algorisme voraç és un algorisme que, per resoldre un problema d'optimització, fa una seqüència d'eleccions, prenent en cada pas un òptim local,[1] amb l'esperança (no sempre complerta)[2] d'arribar a un òptim global. L'algorisme voraç no torna mai enrere per reavaluar les eleccions ja preses.
Tot algorisme voraç conté el següent:[3]
L'exemple més habitual é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.[4][5][6]
Altres exemples típics són el de minimitzar el recorregut que ha de fer un viatjant de comerç per a visitar una sèrie de clients distanciats entre ells (vegeu algorisme de Dijkstra)[7] o el d'empaquetar objectes de diferents volums en el mínim nombre de caixes idèntiques.[8]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.