Mantkārīgi algoritmi ir algoritmu klase, kas veido lokāli optimāls izvēles katrā solī ar cerību atrast a globālais optimālais risinājums. Šajos algoritmos lēmumi tiek pieņemti, pamatojoties uz šobrīd pieejamo informāciju, neņemot vērā šo lēmumu sekas nākotnē. Galvenā ideja ir katrā solī izvēlēties labāko iespējamo izvēli, lai rastu risinājumu, kas ne vienmēr ir optimālākais, bet bieži vien ir pietiekami labs daudzām problēmām.

Šajā rakstā mēs sapratīsim mantkārīgos algoritmus ar piemēriem. Aplūkosim arī problēmas un to risinājumus, izmantojot mantkārīgo pieeju.

Mantkārīgi algoritmi

Satura rādītājs

• Kas ir mantkārīgs algoritms?
• Soļi mantkārīga algoritma izveidei
• Mantkārīgo algoritmu piemēri
• Mantkārīgā algoritma pielietojumi
• Mantkārīga algoritma izmantošanas trūkumi/ierobežojumi
• Mantkārīgā algoritma pamati
• Standarta alkatīgie algoritmi
• Mantkārīgas problēmas masīvā
• Mantkārīgas problēmas operētājsistēmā
• Mantkārīgas problēmas grafikā
• Aptuvenais mantkārīgs algoritms NP Complete
• Mantkārīgs DP īpašiem gadījumiem
• Vienkāršas problēmas mantkārīgā algoritmā
• Vidējas problēmas mantkārīgā algoritmā
• Grūtās problēmas mantkārīgā algoritmā

Kas ir mantkārīgs algoritms?

A mantkārīgs algoritms ir optimizācijas algoritma veids, kas veic lokāli optimālas izvēles katrā solī, lai atrastu globāli optimālu risinājumu. Tā darbojas pēc principa izvēlēties labāko risinājumu tagad, neņemot vērā ilgtermiņa sekas.

Lai uzzinātu, kas ir mantkārīgā metode un kā izmantot mantkārīgo pieeju, izlasiet doto pamācību par Mantkārīgo algoritmu:

Soļi mantkārīga algoritma izveidei

Mantkārīga algoritma noteikšanas darbības ir šādas:

1. Definējiet problēmu: Skaidri norādiet risināmo problēmu un optimizējamo mērķi.
2. Identificējiet mantkārīgo izvēli: Nosakiet lokāli optimālo izvēli katrā solī, pamatojoties uz pašreizējo stāvokli.
3. Izdari mantkārīgo izvēli: Izvēlieties mantkārīgo izvēli un atjauniniet pašreizējo stāvokli.
4. Atkārtojiet: Turpiniet izdarīt mantkārīgas izvēles, līdz tiek panākts risinājums.

Veicot norādītās darbības, var uzzināt, kā izmantot alkatīgus algoritmus, lai atrastu optimālus risinājumus.

Mantkārīgo algoritmu piemēri

Mantkārīgu algoritmu piemēri ir labākais veids, kā izprast algoritmu. Daži mantkārīgu algoritmu reālās dzīves piemēri:

• Daļēja mugursoma : Optimizē to priekšmetu vērtību, kurus var daļēji iekļaut mugursomā ar ierobežotu ietilpību.
• Dijkstras algoritms : Atrod īsāko ceļu no avota virsotnes uz visām pārējām virsotnēm svērtā grafikā.
• Kruskal algoritms : Atrod svērtā grafika minimālo aptverošo koku.
• Hafmena kodēšana : Saspiež datus, biežāk sastopamiem simboliem piešķirot īsākus kodus.

Mantkārīgā algoritma pielietojumi

Tur ir daudz mantkārīgās metodes pielietojumi DAA . Dažas svarīgas mantkārīgo algoritmu lietojumprogrammas ir šādas:

• Uzdevumu piešķiršana resursiem, lai samazinātu gaidīšanas laiku vai palielinātu efektivitāti.
• Vērtīgāko priekšmetu atlase, lai ietilptu mugursomā ar ierobežotu ietilpību.
• Attēla sadalīšana reģionos ar līdzīgām īpašībām.
• Datu apjoma samazināšana, noņemot lieko informāciju.

Mantkārīga algoritma izmantošanas trūkumi/ierobežojumi

Tālāk ir minēti daži Mantkārīgā algoritma trūkumi:

• Mantkārīgi algoritmi ne vienmēr var atrast labāko iespējamo risinājumu.
• Elementu izskatīšanas secība var būtiski ietekmēt rezultātu.
• Mantkārīgi algoritmi koncentrējas uz lokālu optimizāciju, un tie var palaist garām labākus risinājumus, kas jāapsver plašākā kontekstā.
• Mantkārīgi algoritmi nav piemērojami problēmām, kurās mantkārīga izvēle nenoved pie optimāla risinājuma.

Mantkārīgā algoritma pamati:

• Mantkārīgi algoritmi (vispārējā struktūra un lietojumprogrammas)
• Atšķirība starp mantkārīgo algoritmu un sadali un iekaro algoritmu
• Mantkārīga pieeja pret dinamisku programmēšanu
• Greedy, Divide and Conquer un dinamiskās programmēšanas algoritmu salīdzinājums

Standarta alkatīgie algoritmi:

• Aktivitātes izvēles problēma
• Darba secības problēma
• Hafmena kodēšana
• Hafmena dekodēšana
• Ūdens savienojuma problēma
• Minimālie mijmaiņas darījumi kronšteinu balansēšanai
• Ēģiptes frakcija
• Policisti ķer zagļus
• Problēma ar plauktu uzstādīšanu
• Piešķiriet pelēm Holes

Mantkārīgas problēmas masīvā:

• Masīva minimālā produktu apakškopa
• Maksimizēt masīva summu pēc K noliegumiem, izmantojot kārtošanu
• Minimālā divu masīvu reizinājuma summa
• Divu masīvu pāru absolūtās starpības minimālā summa
• Minimālais palielinājums/samazinājums, lai masīvs nebūtu pieaugošs
• Kārtošanas masīvs ar reversu ap vidu
• Masīvam iespējamā taisnstūru laukumu summa
• Lielākais leksikogrāfiskais masīvs ar ne vairāk kā K secīgiem mijmaiņas darījumiem
• Sadalīšana divās apakšgrupās ar garumu k un (N – k) tā, lai summu starpība būtu maksimālā

Mantkārīgas problēmas operētājsistēmā:

• Pirmais Fit algoritms atmiņas pārvaldībā
• Best Fit algoritms atmiņas pārvaldībā
• Sliktākā atbilstības algoritms atmiņas pārvaldībā
• Īsākais darbs vispirms
• Darba plānošana ar diviem atļautiem darbiem vienlaikus
• Programma optimālam lapu aizstāšanas algoritmam

Mantkārīgas problēmas diagrammā:

• Kruskala minimālais stiepšanās koks
• Prim minimālais aptverošais koks
• Boruvkas minimālais aptverošais koks
• Dijkastra īsākā ceļa algoritms
• Ciparnīcas algoritms
• Minimālās izmaksas, lai savienotu visas pilsētas
• Maksimālās plūsmas problēmas ievads
• Viena cikla komponentu skaits nevirzītā grafikā

Aptuvenais alkatības algoritms NP Complete:

• Iestatīt vāka problēmu
• Tvertnes iepakošanas problēma
• Grafika krāsošana
• K-centru problēma
• Īsākā superstring problēma
• Aptuvens risinājums ceļojošā pārdevēja problēmai, izmantojot MST

Mantkārīgs īpašiem DP gadījumiem:

• Frakcionēta mugursomas problēma
• Nepieciešamais minimālais monētu skaits

Vienkāršas problēmas vietnē Greedy Algoritms :

• Sadaliet n maksimālajos saliktajos skaitļos
• Pērciet maksimālos krājumus, ja i akcijas var iegādāties i-tajā dienā
• Atrodi minimālo un maksimālo summu, lai iegādātos visas N konfektes
• Maksimālā iespējamā summa, kas vienāda ar trīs kaudzīšu summu
• Sadaliet kuboīdu kubos tā, lai tilpumu summa būtu maksimāla
• Maksimālais klientu skaits, kas var būt apmierināti ar doto daudzumu
• Minimālais apgriezienu skaits, lai atbloķētu apļveida slēdzeni
• Minimālās telpas m pasākumiem no n grupām ar noteiktu grafiku
• Minimālās izmaksas, lai izveidotu 1. izmēra masīvu, noņemot lielākos pārus
• Minimālās izmaksas visu monētu iegādei ar k papildu monētām, kas atļautas ar katru monētu
• Minimālais pieaugums par k darbībām, lai visi elementi būtu vienādi
• Atrodiet minimālo valūtas banknošu un vērtību skaitu, kas atbilst norādītajai summai
• Mazākā apakškopa, kuras summa ir lielāka par visiem citiem elementiem

Vidējas problēmas ar Greedy Algoritms :

• Maksimālais vilcienu skaits, kuriem var nodrošināt apstāšanās
• Minimālie Fibonači vārdi, kuru summa ir vienāda ar K
• Sadaliet 1 līdz n divās grupās ar minimālo summu starpību
• Papīrs sagriezts minimālajā kvadrātu skaitā
• Minimālā atšķirība starp otrā izmēra grupām
• Savienojiet n virves ar minimālām izmaksām
• Dzelzceļa/autoostai nepieciešamais minimālais platformu skaits
• Minimālās sākotnējās virsotnes, lai šķērsotu visu matricu ar dotajiem nosacījumiem
• Lielākais palindromiskais skaitlis, mainot ciparus
• Atrodiet mazāko skaitli ar norādīto ciparu skaitu un ciparu summu
• Leksikogrāfiski lielākā apakšsecība, kurā katra rakstzīme atkārtojas vismaz k reizes

Grūtās problēmas vietnē Greedy Algoritms :

• Maksimālais elementu skaits, ko var padarīt vienādus ar k atjauninājumiem
• Samaziniet naudas plūsmu draugu lokā
• Minimālās izmaksas dēļa sagriešanai kvadrātos
• Minimālās izmaksas, lai apstrādātu m uzdevumus, kur pārslēgšanās izmaksas
• Minimālais laiks visu darbu pabeigšanai ar noteiktiem ierobežojumiem
• Samaziniet maksimālo atšķirību starp torņu augstumiem
• Minimālās malas, kas jāapgriež, lai izveidotu ceļu no avota līdz galamērķim
• Atrodiet lielāko kubu, kas izveidots, no skaitļa izdzēšot minimālos ciparus
• Pārkārtojiet rakstzīmes virknē tā, lai divas blakus esošās nebūtu vienādas
• Pārkārtojiet virkni tā, lai visas tās pašas rakstzīmes būtu d attālumā

Ātrās saites:

• Uzziniet datu struktūru un algoritmus | DSA apmācība
• 20 populārākie mantkārīgo algoritmu intervijas jautājumi
• “Prakses problēmas” mantkārīgos algoritmos
• “Viktorīna” par mantkārīgiem algoritmiem