logo

TechCodeview

Algorismes cobdiciosos

Algoritmes cobdiciosos són una classe d'algorismes que fan localment òptim opcions a cada pas amb l'esperança de trobar a òptim global solució. En aquests algorismes, les decisions es prenen a partir de la informació disponible en el moment actual sense tenir en compte les conseqüències d'aquestes decisions en el futur. La idea clau és seleccionar la millor opció possible a cada pas, donant lloc a una solució que potser no sempre és la més òptima, però sovint és prou bona per a molts problemes.

En aquest article, entendrem els algorismes cobdiciosos amb exemples. També analitzarem els problemes i les seves solucions mitjançant l'enfocament cobdiciós.

xifra romana de l'1 al 100

Algorismes cobdiciosos



Taula de contingut

Què és Greedy Algorithm?

A algorisme cobdiciós és un tipus d'algorisme d'optimització que fa opcions òptimes localment a cada pas per trobar una solució òptima globalment. Funciona amb el principi de prendre la millor opció ara sense tenir en compte les conseqüències a llarg termini.

Per saber què és el mètode cobdiciós i com utilitzar l'enfocament cobdiciós, llegiu el tutorial sobre l'algoritme cobdiciós:

Passos per crear un algorisme cobdiciós

Els passos per definir un algorisme cobdiciós són:

  1. Definiu el problema: Indiqueu clarament el problema a resoldre i l'objectiu a optimitzar.
  2. Identifiqueu l'opció cobdiciosa: Determineu l'opció òptima localment a cada pas en funció de l'estat actual.
  3. Feu l'elecció cobdiciosa: Seleccioneu l'opció cobdiciosa i actualitzeu l'estat actual.
  4. Repetiu: Continueu fent eleccions cobdiciosos fins que s'arribi a una solució.

Seguint els passos indicats, es pot aprendre a utilitzar algorismes cobdiciosos per trobar solucions òptimes.

Exemples d'algoritmes cobdiciosos

Els exemples d'algoritmes cobdiciosos són la millor manera d'entendre l'algorisme. Alguns exemples de la vida real d'algoritmes cobdiciosos són:

  • Motxilla fraccionada : Optimitza el valor dels articles que es poden incloure de manera fraccionada en una motxilla amb capacitat limitada.
  • algorisme de Dijkstra : Troba el camí més curt des d'un vèrtex font fins a tots els altres vèrtexs d'un gràfic ponderat.
  • algorisme de Kruskal : Troba l'arbre d'abast mínim d'un gràfic ponderat.
  • Codificació Huffman : Comprimeix les dades assignant codis més curts a símbols més freqüents.

Aplicacions de l'algoritme Greedy

Hi ha molts aplicacions del mètode greedy en DAA . Algunes aplicacions importants d'algoritmes cobdiciosos són:

  • Assignació de tasques als recursos per minimitzar el temps d'espera o maximitzar l'eficiència.
  • Selecció dels articles més valuosos per cabre en una motxilla amb capacitat limitada.
  • Dividir una imatge en regions amb característiques similars.
  • Reduir la mida de les dades eliminant la informació redundant.

Inconvenients/Limitacions de l'ús d'un algorisme cobdiciós

A continuació es mostren alguns desavantatges de l'algoritme Greedy:

  • És possible que els algorismes cobdiciosos no sempre trobin la millor solució possible.
  • L'ordre en què es consideren els elements pot afectar significativament el resultat.
  • Els algorismes cobdiciosos se centren en optimitzacions locals i poden perdre solucions millors que requereixin tenir en compte un context més ampli.
  • Els algorismes cobdiciosos no són aplicables als problemes on l'elecció cobdiciosa no condueix a una solució òptima.

Conceptes bàsics de l'algoritme Greedy:

  • Algoritmes cobdiciosos (estructura general i aplicacions)
  • Diferència entre l'algoritme Greedy i l'algoritme Divide and Conquer
  • Enfocament cobdiciós vs programació dinàmica
  • Comparació entre Greedy, Divide and Conquer i algorisme de programació dinàmica

Algoritmes Greedy estàndard:

  • Problema de selecció d'activitats
  • Problema de seqüenciació de treballs
  • Codificació Huffman
  • Descodificació de Huffman
  • Problema de connexió d'aigua
  • Canvis mínims per a l'equilibri de suports
  • Fracció egípcia
  • Els policies atrapen lladres
  • Problema d'ajust de prestatges
  • Assigna els ratolins als forats

Problemes cobdiciosos a Array:

  • Subconjunt de producte mínim d'una matriu
  • Maximitzeu la suma de la matriu després de K negacions mitjançant l'Ordenació
  • Suma mínima del producte de dues matrius
  • Suma mínima de la diferència absoluta de parells de dues matrius
  • Increment/disminució mínim perquè la matriu no sigui creixent
  • Matriu d'ordenació amb el revés al mig
  • Suma d'àrees de rectangles possible per a una matriu
  • La matriu lexicogràfica més gran amb com a màxim K intercanvis consecutius
  • Partició en dos subarrays de longituds k i (N – k) de manera que la diferència de sumes sigui màxima

Problemes cobdiciosos al sistema operatiu:

  • Algorisme First Fit en gestió de memòria
  • Algorisme Best Fit en gestió de memòria
  • Algorisme Worst Fit en gestió de memòria
  • Programació de la primera feina més curta
  • Programació de treballs amb dues feines permeses alhora
  • Programa per a l'algoritme de substitució òptima de pàgines

Problemes cobdiciosos al gràfic:

  • L'arbre d'abast mínim de Kruskal
  • Arbre d'abast mínim de Prim
  • Arbre d'abast mínim de Boruvka
  • Algoritme del camí més curt de Dijkastra
  • Algoritme de marcatge
  • Cost mínim per connectar totes les ciutats
  • Introducció al problema de flux màxim
  • Nombre de components d'un sol cicle en un gràfic no dirigit

Algoritme Greedy aproximat per a NP Complete:

  • Estableix el problema de la coberta
  • Problema d'embalatge de la paperera
  • Coloració de gràfics
  • Problema dels centres K
  • El problema de supercorda més curt
  • Solució aproximada per al problema del venedor ambulant mitjançant MST

Greedy per a casos especials de DP:

  • Problema de la motxilla fraccionada
  • Es requereix un nombre mínim de monedes

Problemes fàcils a Greedy Algoritme :

  • Divideix n en nombres compostos màxims
  • Compreu accions màximes si es poden comprar accions el dia i
  • Trobeu la quantitat mínima i màxima per comprar tots els N caramels
  • Suma màxima possible igual a la suma de tres piles
  • Dividiu el cuboide en cubs de manera que la suma de volums sigui màxima
  • Nombre màxim de clients que es poden satisfer amb una quantitat determinada
  • Rotacions mínimes per desbloquejar un pany circular
  • Sales mínimes per a m esdeveniments de n lots amb una programació determinada
  • Cost mínim per fer una matriu de mida 1 eliminant els parells més grans
  • Cost mínim per adquirir totes les monedes amb k monedes addicionals permeses amb cada moneda
  • Increment mínim en k operacions per fer que tots els elements siguin iguals
  • Trobeu el nombre mínim de bitllets de moneda i els valors que sumen la quantitat determinada
  • El subconjunt més petit amb una suma més gran que tots els altres elements

Problemes mitjans sobre Greedy Algoritme :

  • Màxim de trens per als quals es pot donar parada
  • Termes mínims de Fibonacci amb una suma igual a K
  • Dividiu 1 a n en dos grups amb una diferència mínima de suma
  • Paper tallat en un nombre mínim de quadrats
  • Diferència mínima entre grups de mida dos
  • Connecteu n cordes amb un cost mínim
  • Nombre mínim d'andanes necessaris per a una estació de tren/autobusos
  • Vèrtexs inicials mínims per recórrer tota la matriu amb condicions donades
  • Nombre palindròmic més gran per dígits permutant
  • Trobeu el nombre més petit amb un nombre determinat de dígits i la suma de dígits
  • Subseqüència lexicogràficament més gran de manera que cada caràcter apareix almenys k vegades

Problemes difícils a Greedy Algoritme :

  • Elements màxims que es poden igualar amb k actualitzacions
  • Minimitzar el flux d'efectiu entre amics
  • Cost mínim per tallar un tauler en quadrats
  • Cost mínim per processar m tasques on els costos de canvi
  • Temps mínim per acabar tots els treballs amb les limitacions donades
  • Minimitzar la diferència màxima entre les altures de les torres
  • Vores mínimes per revertir per fer el camí des d'una font a una destinació
  • Trobeu el cub més gran format eliminant els dígits mínims d'un nombre
  • Reorganitza els caràcters d'una cadena de manera que no hi hagi dos adjacents iguals
  • Reorganitzeu una cadena de manera que tots els mateixos caràcters es quedin d distància
  • Apreneu l'estructura de dades i els algorismes | Tutorial DSA
  • Les 20 principals preguntes d'entrevista d'algoritmes cobdiciosos
  • 'Pràctica de problemes' en algorismes cobdiciosos
  • 'Quiz' sobre algorismes cobdiciosos