El mètode cobdiciós és una de les estratègies com Divideix i venç utilitzades per resoldre els problemes. Aquest mètode s'utilitza per resoldre problemes d'optimització. Un problema d'optimització és un problema que exigeix ​​resultats màxims o mínims. Entenem-nos a través d'alguns termes.

El mètode Greedy és l'enfocament més senzill i directe. No és un algorisme, però és una tècnica. La funció principal d'aquest enfocament és que la decisió es prengui sobre la base de la informació disponible actualment. Sigui quina sigui la informació actual present, la decisió es pren sense preocupar-se de l'efecte de la decisió actual en el futur.

dividit per cadena java

Aquesta tècnica s'utilitza bàsicament per determinar la solució factible que pot ser òptima o no. La solució factible és un subconjunt que compleix els criteris donats. La solució òptima és la solució que és la millor i la més favorable del subconjunt. En el cas de factible, si més d'una solució compleix els criteris donats, aquestes solucions es consideraran factibles, mentre que la solució òptima és la millor entre totes les solucions.

Característiques del mètode Greedy

Les següents són les característiques d'un mètode cobdiciós:

• Per construir la solució d'una manera òptima, aquest algorisme crea dos conjunts on un conjunt conté tots els elements escollits i un altre conjunt conté els elements rebutjats.
• Un algorisme Greedy fa bones eleccions locals amb l'esperança que la solució sigui factible o òptima.

Components de l'algoritme Greedy

Els components que es poden utilitzar en l'algoritme greedy són:

cadena.conté java

Conjunt de candidats:Una solució que es crea a partir del conjunt es coneix com a conjunt candidat.Funció de selecció:Aquesta funció s'utilitza per triar el candidat o subconjunt que es pot afegir a la solució.Funció de viabilitat:Una funció que s'utilitza per determinar si el candidat o el subconjunt es pot utilitzar per contribuir a la solució o no.Funció objectiva:Una funció s'utilitza per assignar el valor a la solució o a la solució parcial.Funció de solució:Aquesta funció s'utilitza per saber si s'ha arribat a la funció completa o no.

Aplicacions de l'algoritme Greedy

• S'utilitza per trobar el camí més curt.
• S'utilitza per trobar l'arbre d'abast mínim mitjançant l'algoritme de prim o l'algoritme de Kruskal.
• S'utilitza en una seqüenciació de treballs amb una data límit.
• Aquest algorisme també s'utilitza per resoldre el problema de la motxilla fraccionada.

Pseudocodi de Greedy Algorithm

 Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } 

L'anterior és l'algoritme cobdiciós. Inicialment, la solució s'assigna amb un valor zero. Passem la matriu i el nombre d'elements a l'algoritme greedy. Dins del bucle for, seleccionem l'element un per un i comprovem si la solució és factible o no. Si la solució és factible, fem la unió.

Entenem-ho a través d'un exemple.

Suposem que hi ha un problema 'P'. Vull viatjar d'A a B que es mostra a continuació:

P: A → B

El problema és que hem de fer aquest trajecte d'A a B. Hi ha diverses solucions per anar d'A a B. Podem anar d'A a B per caminar, cotxe, bicicleta, tren, avió , etc. Hi ha una limitació en el trajecte que hem de fer aquest viatge en 12 hores. Si vaig en tren o en avió només, puc cobrir aquesta distància en 12 hores. Hi ha moltes solucions a aquest problema, però només hi ha dues solucions que satisfan la restricció.

Si diem que hem de cobrir el trajecte al mínim cost. Això vol dir que hem de recórrer aquesta distància el mínim possible, de manera que aquest problema es coneix com a problema de minimització. Fins ara, tenim dues solucions factibles, és a dir, una per tren i una altra per aire. Atès que viatjar en tren comportarà un cost mínim per això és una solució òptima. Una solució òptima també és la solució factible, però proporcionant el millor resultat perquè aquesta solució sigui la solució òptima amb el mínim cost. Només hi hauria una solució òptima.

El problema que requereix un resultat mínim o màxim llavors aquest problema es coneix com a problema d'optimització. El mètode Greedy és una de les estratègies utilitzades per resoldre els problemes d'optimització.

nombre sencer doble java

Desavantatges d'utilitzar l'algoritme Greedy

L'algoritme Greedy pren decisions basant-se en la informació disponible a cada fase sense considerar el problema més ampli. Per tant, pot haver-hi la possibilitat que la solució cobdiciosa no doni la millor solució per a cada problema.

Segueix l'opció òptima local en cada etapa amb la intenció de trobar l'òptim global. Entenem-ho a través d'un exemple.

inurl:.git/head

Considereu el gràfic que es mostra a continuació:

Hem de viatjar des de l'origen fins al destí amb el mínim cost. Com que tenim tres solucions factibles amb camins de cost com 10, 20 i 5, 5 és el camí de cost mínim, per tant, és la solució òptima. Aquest és l'òptim local, i d'aquesta manera, trobem l'òptim local en cada etapa per tal de calcular la solució òptima global.