Taula de continguts:
Definició: què significa Greedy Algorithm?
Un algorisme avariciós és una estratègia algorítmica que fa la millor elecció òptima en cada petita etapa amb l'objectiu que això acabi conduint a una solució òptima globalment. Això significa que l'algoritme tria la millor solució actualment sense tenir en compte les conseqüències. Escull la millor producció immediata, però no té en compte la imatge gran, per tant es considera avariciosa.
La Techopedia explica l'algoritme de Greedy
Un algorisme algorisme funciona triant la millor resposta possible a cada pas i passant al següent pas fins arribar al final, sense tenir en compte la solució global. Només s’espera que el camí que es faci sigui l’òptim globalment, però, com s’ha demostrat una i altra vegada, aquest mètode no sol trobar una solució òptima globalment. De fet, és totalment possible que les solucions a més curt termini òptimes portin al pitjor resultat global possible.
Penseu-hi com a una gran quantitat de dreceres en un negoci de fabricació: a curt termini s’estalvien grans quantitats en el cost de fabricació, però això condueix a la caiguda ja que la qualitat es veu compromesa, amb la qual cosa es produeixen rendiments del producte i vendes baixes a mesura que els clients es familiaritzin amb Producte “barat”. Però no sempre és així, hi ha moltes aplicacions en les quals l’algoritme avariciós funciona millor per trobar o aproximar la solució òptima globalment com ara construir un arbre de Huffman o un arbre d’aprenentatge de decisions.
Per exemple: Agafeu el camí que tingui la suma més gran en conjunt. Un algorisme avariciós prendria el camí blau, com a resultat de la miopia, més que el camí taronja, que obté la suma més gran.
Components:
- Un conjunt de dades candidat que necessita una solució
- Una funció de selecció que tria el millor contribuent a la solució final
- Una funció de viabilitat que ajuda la funció de selecció determinant si un candidat pot contribuir a la solució
- Funció objectiva que assigna un valor a una solució parcial
- Una funció de solució que indica que s'ha descobert la solució òptima
