logo

TechCodeview

Godūs algoritmai

Godūs algoritmai yra algoritmų klasė, kuri sukuria lokaliai optimalus pasirinkimai kiekviename žingsnyje su viltimi rasti a pasaulinis optimalus sprendimas. Šiuose algoritmuose sprendimai priimami remiantis šiuo metu turima informacija, neatsižvelgiant į šių sprendimų pasekmes ateityje. Pagrindinė idėja yra kiekviename žingsnyje pasirinkti geriausią įmanomą pasirinkimą, kad būtų pasiektas sprendimas, kuris ne visada gali būti optimaliausias, bet dažnai pakankamai geras daugeliui problemų.

Šiame straipsnyje mes suprasime godžius algoritmus su pavyzdžiais. Taip pat žvelgsime į problemas ir jų sprendimus naudodami gobšų požiūrį.

Godūs algoritmai



Turinys

Kas yra godus algoritmas?

A godus algoritmas yra optimizavimo algoritmo tipas, kuris atlieka lokaliai optimalius sprendimus kiekviename žingsnyje, kad rastų globaliai optimalų sprendimą. Jis veikia pagal principą pasirinkti geriausią variantą dabar, neatsižvelgiant į ilgalaikes pasekmes.

Norėdami sužinoti, kas yra godus metodas ir kaip naudoti godų metodą, perskaitykite pateiktą „Godaus algoritmo“ pamoką:

Godaus algoritmo kūrimo žingsniai

Veiksmai, skirti apibrėžti godų algoritmą, yra šie:

  1. Apibrėžkite problemą: Aiškiai nurodykite problemą, kurią reikia išspręsti, ir tikslą, kurį reikia optimizuoti.
  2. Nustatykite gobšų pasirinkimą: Pagal dabartinę būseną nustatykite lokaliai optimalų pasirinkimą kiekviename žingsnyje.
  3. Padarykite gobšų pasirinkimą: Pasirinkite gobšų pasirinkimą ir atnaujinkite dabartinę būseną.
  4. Pakartokite: Tęskite gobšus pasirinkimus, kol pasieksite sprendimą.

Atlikus nurodytus veiksmus, galima išmokti naudoti godžius algoritmus ieškant optimalių sprendimų.

Godaus algoritmo pavyzdžiai

Gobšių algoritmų pavyzdžiai yra geriausias būdas suprasti algoritmą. Kai kurie godūs algoritmai realiame gyvenime yra šie:

  • Dalinė kuprinė : Optimizuoja daiktų, kuriuos galima dalimis įtraukti į ribotos talpos kuprinę, vertę.
  • Dijkstros algoritmas : Suranda trumpiausią kelią nuo šaltinio viršūnės iki visų kitų svertinio grafiko viršūnių.
  • Kruskal algoritmas : Suranda mažiausią svertinio grafiko apimantį medį.
  • Huffmano kodavimas : Suglaudina duomenis priskirdamas trumpesnius kodus dažnesniems simboliams.

Godaus algoritmo taikymai

Yra daug godaus metodo taikymas DAA . Kai kurios svarbios gobšų algoritmų programos yra šios:

  • Užduočių priskyrimas ištekliams siekiant sumažinti laukimo laiką arba padidinti efektyvumą.
  • Vertingiausių daiktų pasirinkimas, kad tilptų į ribotos talpos kuprinę.
  • Vaizdo padalijimas į panašių savybių regionus.
  • Sumažinti duomenų dydį pašalinant perteklinę informaciją.

Godaus algoritmo naudojimo trūkumai / apribojimai

Žemiau yra keletas „Gedaus algoritmo“ trūkumų:

  • Godūs algoritmai ne visada gali rasti geriausią įmanomą sprendimą.
  • Elementų svarstymo tvarka gali labai paveikti rezultatą.
  • Godūs algoritmai sutelkia dėmesį į vietinį optimizavimą ir gali praleisti geresnius sprendimus, kuriems reikia atsižvelgti į platesnį kontekstą.
  • Godūs algoritmai netaikomi problemoms, kai gobšus pasirinkimas neduoda optimalaus sprendimo.

Godaus algoritmo pagrindai:

  • Godūs algoritmai (bendra struktūra ir programos)
  • Skirtumas tarp godaus algoritmo ir skaldyk ir užkariauk algoritmo
  • Godus požiūris prieš dinaminį programavimą
  • Greedy, Divide and Conquer ir dinaminio programavimo algoritmų palyginimas

Standartiniai godūs algoritmai:

  • Veiklos pasirinkimo problema
  • Darbų sekos problema
  • Huffmano kodavimas
  • Huffmano dekodavimas
  • Vandens prijungimo problema
  • Minimalūs mainai, skirti balansavimui
  • Egipto frakcija
  • Policininkai gaudo vagis
  • Lentynų montavimo problema
  • Priskirkite peles prie skylių

Godžios problemos masyve:

  • Minimalus masyvo produktų poaibis
  • Padidinkite masyvo sumą po K neigimo naudodami Rūšiavimą
  • Mažiausia dviejų masyvų sandaugos suma
  • Mažiausia dviejų masyvų porų absoliutaus skirtumo suma
  • Minimalus padidėjimas / mažinimas, kad masyvas nedidėtų
  • Rūšiavimo masyvas su reversu aplink vidurį
  • Galima masyvo stačiakampių plotų suma
  • Didžiausias leksikografinis masyvas su daugiausia K keitimų iš eilės
  • Padalijimas į dvi dalis, kurių ilgis k ir (N – k), kad sumų skirtumas būtų didžiausias

Godžios problemos operacinėje sistemoje:

  • Pirmasis pritaikymo algoritmas atminties valdyme
  • Geriausias atminties valdymo algoritmas
  • Blogiausias atminties valdymo algoritmas
  • Trumpiausias darbas pirmas tvarkaraštis
  • Darbo planavimas leidžiant vienu metu atlikti du darbus
  • Optimalaus puslapio keitimo algoritmo programa

Godžios problemos diagramoje:

  • Kruskalo mažiausias besitęsiantis medis
  • Prim minimalus besitęsiantis medis
  • Boruvkos mažiausias besitęsiantis medis
  • Dijkastros trumpiausio kelio algoritmas
  • Rinkimo algoritmas
  • Minimali kaina sujungti visus miestus
  • Max Flow problemos įvadas
  • Vieno ciklo komponentų skaičius nenukreiptame grafike

Apytikslis „Greedy“ algoritmas, skirtas „NP Complete“:

  • Nustatyti dangtelio problemą
  • Dėžės pakavimo problema
  • Grafiko dažymas
  • K-centrų problema
  • Trumpiausia superstygos problema
  • Apytikslis keliaujančio pardavėjo problemos sprendimas naudojant MST

Gobšus ypatingiems DP atvejams:

  • Dalinės kuprinės problema
  • Reikalingas minimalus monetų skaičius

Lengvos „Greedy“ problemos Algoritmas :

  • Padalinkite n į didžiausius sudėtinius skaičius
  • Pirkite maksimalias atsargas, jei i akcijas galima nusipirkti i-tą dieną
  • Raskite mažiausią ir didžiausią sumą, kad nusipirktumėte visus N saldainius
  • Didžiausia galima suma lygi trijų krūvų sumai
  • Padalinkite stačiakampį į kubus taip, kad tūrių suma būtų didžiausia
  • Didžiausias klientų, kurie gali būti patenkinti nurodytu kiekiu, skaičius
  • Mažiausias apsisukimų skaičius, norint atrakinti apskritą užraktą
  • Minimalios patalpos m renginiams iš n partijų su nurodytu grafiku
  • Minimali kaina, norint sukurti 1 dydžio masyvą pašalinus didesnes poras
  • Minimali visų monetų įsigijimo kaina, kai su kiekviena moneta leidžiama pridėti k papildomų monetų
  • Mažiausias k operacijų padidėjimas, kad visi elementai būtų lygūs
  • Raskite minimalų valiutų banknotų skaičių ir vertes, kurių suma atitinka nurodytą sumą
  • Mažiausias poaibis, kurio suma didesnė už visus kitus elementus

Vidutinės „Greedy“ problemos Algoritmas :

  • Maksimalus traukinių, kuriems gali būti suteiktas sustojimas, skaičius
  • Minimalūs Fibonačio nariai, kurių suma lygi K
  • Padalinkite nuo 1 iki n į dvi grupes su minimaliu skirtumu
  • Popierius supjaustomas į minimalų skaičių kvadratų
  • Minimalus skirtumas tarp antrojo dydžio grupių
  • Sujunkite n virves su minimaliomis sąnaudomis
  • Minimalus peronų skaičius, reikalingas geležinkelio / autobusų stočiai
  • Minimalios pradinės viršūnės, kad būtų galima pereiti visą matricą tam tikromis sąlygomis
  • Didžiausias palindrominis skaičius permutuojant skaitmenis
  • Raskite mažiausią skaičių su nurodytu skaitmenų skaičiumi ir skaitmenų sumą
  • Leksikografiškai didžiausia seka, kad kiekvienas simbolis kartotųsi bent k kartų

Sunkios „Greedy“ problemos Algoritmas :

  • Maksimalus elementų skaičius, kuris gali būti lygus k atnaujinimams
  • Sumažinkite pinigų srautus tarp draugų
  • Minimalios lentos pjaustymo į kvadratus kaina
  • Minimali kaina apdoroti m užduočių, kai kainuoja perėjimas
  • Minimalus laikas užbaigti visus darbus su nurodytais apribojimais
  • Sumažinkite didžiausią skirtumą tarp bokštų aukščių
  • Minimalūs kraštai, kuriuos reikia pakeisti, kad būtų sudarytas kelias nuo šaltinio iki paskirties vietos
  • Raskite didžiausią kubą, sudarytą išbraukus minimalius skaitmenis iš skaičiaus
  • Pertvarkykite simbolius eilutėje taip, kad nebūtų dviejų vienodų gretimų
  • Pertvarkykite eilutę taip, kad visi tie patys simboliai būtų d atstumu
  • Sužinokite duomenų struktūrą ir algoritmus | DSA mokymo programa
  • 20 geriausių godžių algoritmų interviu klausimų
  • „Praktikos problemos“ gobšiuose algoritmuose
  • „Viktorina“ apie godius algoritmus