Grådige algoritmer forklaret med eksempler

Hvad er en grådig algoritme?

Du har muligvis hørt om en masse algoritmiske designteknikker, mens du gennemsøger nogle af artiklerne her. Nogle af dem er:

  • Råstyrke
  • Opdel og sejr
  • Grådig programmering
  • Dynamisk programmering for at nævne nogle få. I denne artikel lærer du om, hvad en grådig algoritme er, og hvordan du kan bruge denne teknik til at løse mange programmeringsproblemer, der ellers ikke synes trivielle.

Forestil dig at du går på vandreture, og dit mål er at nå den højest mulige top. Du har allerede kortet, før du starter, men der er tusindvis af mulige stier vist på kortet. Du er for doven og har simpelthen ikke tid til at evaluere hver af dem. Skru kortet! Du begyndte at vandre med en simpel strategi - vær grådig og kortsynt. Bare tag stier, der skråner mest opad. Dette virker som en god strategi til vandreture. Men er det altid det bedste?

Efter turen sluttede, og hele din krop er øm og træt, ser du på vandrekortet for første gang. Åh gud! Der er en mudret flod, som jeg skulle have krydset, i stedet for at fortsætte med at gå opad. Dette betyder, at en grådig algoritme vælger det bedste øjeblikkelige valg og aldrig genovervejer sine valg. Med hensyn til optimering af en løsning betyder det simpelthen, at den grådige løsning vil forsøge at finde lokale optimale løsninger - som kan være mange - og måske går glip af en global optimal løsning.

Formel definition

Antag, at du har en objektiv funktion, der skal optimeres (enten maksimeret eller minimeret) på et givet tidspunkt. En grådig algoritme træffer grådige valg ved hvert trin for at sikre, at den objektive funktion er optimeret. Den grådige algoritme har kun et skud for at beregne den optimale løsning, så den aldrig går tilbage og vender beslutningen.

Grådige algoritmer har nogle fordele og ulemper:

  • Det er ret let at komme med en grådig algoritme (eller endda flere grådige algoritmer) til et problem. At analysere køretiden for grådige algoritmer vil generelt være meget lettere end for andre teknikker (som Divide and conquer). For Opdel og erobre teknikken er det ikke klart, om teknikken er hurtig eller langsom. Dette skyldes, at størrelsen på hvert rekursionsniveau bliver mindre, og antallet af underproblemer stiger.
  • Den vanskelige del er, at for grådige algoritmer skal du arbejde meget hårdere for at forstå korrekthedsproblemer. Selv med den korrekte algoritme er det svært at bevise, hvorfor den er korrekt. At bevise, at en grådig algoritme er korrekt, er mere en kunst end en videnskab. Det involverer en masse kreativitet. Normalt ser det ud til at være trivielt at komme op med en algoritme, men det er et helt andet problem at bevise, at den faktisk er korrekt.

Intervalplanlægningsproblem

Lad os dykke ned i et interessant problem, som du kan støde på i næsten enhver branche eller enhver livsstil. Nogle eksempler på problemet er som følger:

  • Du får et sæt N tidsplaner for forelæsninger for en enkelt dag på et universitet. Tidsplanen for en bestemt forelæsning er af den form (s tid, f tid), hvor s tid repræsenterer starttidspunktet for den forelæsning, og ligeledes f tiden repræsenterer sluttiden. På baggrund af en liste over N forelæsningsplaner er vi nødt til at vælge det maksimale sæt forelæsninger, der skal holdes i løbet af dagen, så   ingen af ​​forelæsningerne overlapper hinanden, dvs. hvis forelæsning Li og Lj er inkluderet i vores valg, så starttidspunktet for j > = sluttid for i eller omvendt .
  • Din ven arbejder som en lejrrådgiver, og han har ansvaret for at organisere aktiviteter for et sæt campister. En af hans planer er følgende mini-triatlon-øvelse: hver deltager skal svømme 20 omgange i en pool, derefter cykle 10 miles og derefter løbe 3 miles.
  • Planen er at sende deltagerne forskudt ud via følgende regel: deltagerne skal bruge puljen en ad gangen. Med andre ord svømmer den første deltager de 20 omgange, går ud og begynder at cykle.
  • Så snart denne første person er ude af puljen, begynder en anden deltager at svømme de 20 omgange; så snart han eller hun er ude og begynder at cykle, begynder en tredje deltager at svømme osv.
  • Hver deltager har en forventet svømningstid, en forventet cykeltid og en forventet køretid. Din ven ønsker at beslutte en tidsplan for triatlon: en rækkefølge, hvor deltagerne starter i rækkefølge.
  • Lad os sige, at afslutningstiden for en tidsplan er det tidligste tidspunkt, hvor alle deltagere bliver færdige med alle tre ben i triathlon, forudsat at tidsfremskrivningerne er nøjagtige. Hvad er den bedste rækkefølge for at sende folk ud, hvis man ønsker, at hele konkurrencen skal være overstået hurtigst muligt? Mere præcist, giv en effektiv algoritme, der producerer en tidsplan, hvis afslutningstid er så lille som muligt

Forelæsningsplanlægningsproblemet

Lad os se på de forskellige tilgange til løsning af dette problem.

Tidligste starttid,  dvs. vælg det interval, der har den tidligste starttid. Se på følgende eksempel, der bryder løsningen. Denne løsning mislykkedes, fordi der kunne være et interval, der starter meget tidligt, men som er meget langt. Dette betyder, at den næste strategi, som vi kunne prøve, er, hvor vi ser på mindre intervaller først.

Tidligste starttid først

Mindste interval Først  dvs. du ender med at vælge forelæsningerne i rækkefølge efter deres samlede interval, der kun er deres   finish time - start time. Igen er denne løsning ikke korrekt. Se på følgende tilfælde.

Korteste interval først

Du kan tydeligt se, at den korteste intervalforelæsning er den i midten, men det er ikke den optimale løsning her. Lad os se på endnu en løsning på dette problem, der får indsigt i denne løsning.

Mindst modstridende interval Først  dvs. du skal se på intervaller, der forårsager det mindste antal konflikter. Endnu en gang har vi et eksempel, hvor denne tilgang ikke finder en optimal løsning.

Mindst modstridende interval først

Diagrammet viser os, at det mindst modstridende interval er det i midten med kun 2 konflikter. Derefter kan vi kun vælge de to intervaller i slutningen med konflikter 3 hver. Men den optimale løsning er at vælge de 4 intervaller på det øverste niveau.

Tidligste afslutningstid først . Dette er den tilgang, der altid giver os den mest optimale løsning på dette problem. Vi hentede en masse indsigter fra tidligere tilgange og kom til sidst på denne tilgang. Vi sorterer intervallerne efter stigende rækkefølge på deres sluttider, og derefter begynder vi at vælge intervaller helt fra starten. Se på følgende pseudokode for mere klarhed.

function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end 

Hvornår bruger vi grådige algoritmer

Grådige algoritmer kan hjælpe dig med at finde løsninger på mange tilsyneladende hårde problemer. Det eneste problem med dem er, at du måske finder den rigtige løsning, men du kan muligvis ikke kontrollere, om det er den rigtige. Alle de grådige problemer deler en fælles ejendom, at en lokal optima i sidste ende kan føre til et globalt minimum uden at genoverveje det sæt valg, der allerede er overvejet.

Grådige algoritmer hjælper os med at løse mange forskellige slags problemer, som:

Korteste sti-problem:

Minimum Spanning Tree Problem i en graf

Huffman-kodningsproblem

K-centrets problem