Godus metodas yra viena iš tokių strategijų kaip „Skaldyk ir valdyk“, naudojamų problemoms spręsti. Šis metodas naudojamas optimizavimo problemoms spręsti. Optimizavimo problema yra problema, kuri reikalauja maksimalaus arba minimalaus rezultato. Supraskime per keletą terminų.
Greedy metodas yra paprasčiausias ir aiškiausias būdas. Tai ne algoritmas, o technika. Pagrindinė šio metodo funkcija yra ta, kad sprendimas priimamas remiantis šiuo metu turima informacija. Kad ir kokia esama informacija būtų, sprendimas priimamas nesijaudinant dėl dabartinio sprendimo poveikio ateityje.
kas yra ypatingas veikėjas
Šis metodas iš esmės naudojamas siekiant nustatyti įmanomą sprendimą, kuris gali būti optimalus arba ne. Galimas sprendimas yra poaibis, atitinkantis pateiktus kriterijus. Optimalus sprendimas yra tas sprendimas, kuris yra geriausias ir palankiausias poaibės sprendimas. Įmanomo atveju, jei pateiktus kriterijus atitinka daugiau nei vienas sprendimas, tie sprendimai bus laikomi įgyvendinamais, o optimalus sprendimas yra geriausias iš visų sprendimų.
Greedy metodo charakteristikos
Toliau pateikiamos godaus metodo ypatybės:
- Norint optimaliai sukonstruoti sprendimą, šis algoritmas sukuria du rinkinius, kur viename rinkinyje yra visi pasirinkti elementai, o kitame – atmesti elementai.
- Greedy algoritmas daro gerus vietinius pasirinkimus, tikėdamasis, kad sprendimas turėtų būti įmanomas arba optimalus.
Godaus algoritmo komponentai
Komponentai, kuriuos galima naudoti gobšiame algoritme, yra šie:
bourne vėl apvalkalas
Godaus algoritmo taikymai
- Jis naudojamas ieškant trumpiausio kelio.
- Jis naudojamas norint rasti mažiausią apimantį medį, naudojant pirminio algoritmo arba Kruskal algoritmą.
- Jis naudojamas darbų sekoje su terminu.
- Šis algoritmas taip pat naudojamas sprendžiant trupmeninės kuprinės problemą.
Greedy Algorithm pseudo kodas
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; } } Aukščiau pateiktas godus algoritmas. Iš pradžių sprendimui priskiriama nulinė reikšmė. Mes perduodame masyvą ir elementų skaičių gobšiame algoritme. For ciklo viduje mes pasirenkame elementą po vieną ir patikriname, ar sprendimas yra įmanomas, ar ne. Jei sprendimas yra įmanomas, mes atliekame sąjungą.
Supraskime per pavyzdį.
Tarkime, kad yra „P“ problema. Noriu keliauti iš A į B, kaip parodyta žemiau:
P: A → B
Problema ta, kad šią kelionę turime keliauti iš A į B. Yra įvairių sprendimų, kaip nukeliauti iš A į B. Iš A į B galime nuvažiuoti iki pėsčiomis, automobiliu, dviračiu, traukiniu, lėktuvu ir tt Kelionėje yra apribojimas, kad šią kelionę turime nukeliauti per 12 val. Jei skrendu traukiniu ar lėktuvu, šį atstumą galiu įveikti per 12 val. Yra daug šios problemos sprendimų, tačiau yra tik du sprendimai, atitinkantys apribojimą.
Jei sakome, kad kelionę turime padengti minimaliomis išlaidomis. Tai reiškia, kad šį atstumą turime nuvažiuoti kiek įmanoma mažiau, todėl ši problema žinoma kaip sumažinimo problema. Iki šiol turime du įmanomus sprendimus, t. y. vieną traukiniu ir kitą oru. Kadangi kelionė traukiniu kainuos minimalias išlaidas, tai yra optimalus sprendimas. Optimalus sprendimas taip pat yra įmanomas sprendimas, tačiau užtikrinantis geriausią rezultatą, kad sprendimas būtų optimalus sprendimas su minimaliomis sąnaudomis. Būtų tik vienas optimalus sprendimas.
Problema, kuriai reikalingas minimalus arba maksimalus rezultatas, tada ta problema vadinama optimizavimo problema. Godus metodas yra viena iš optimizavimo problemų sprendimo strategijų.
unix viršutinė komanda
Greedy algoritmo naudojimo trūkumai
Godus algoritmas priima sprendimus remdamasis kiekvienoje fazėje turima informacija, neatsižvelgdamas į platesnę problemą. Taigi, gali būti, kad gobšus sprendimas nepateikia geriausio kiekvienos problemos sprendimo.
Kiekviename etape jis vadovaujasi vietiniu optimaliu pasirinkimu, siekdamas rasti visuotinį optimalumą. Supraskime per pavyzdį.
sąrašą rūšiuoti java
Apsvarstykite žemiau pateiktą grafiką:
Turime keliauti nuo šaltinio iki kelionės tikslo minimaliomis išlaidomis. Kadangi turime tris įmanomus sprendimus, kurių sąnaudų keliai yra 10, 20 ir 5. 5 yra minimalių sąnaudų kelias, todėl tai yra optimalus sprendimas. Tai yra vietinis optimalus, ir tokiu būdu mes kiekviename etape randame vietinį optimalumą, kad galėtume apskaičiuoti visuotinį optimalų sprendimą.