Greedy algoritmer er en type algoritmisk tilnærming som gjør lokale optimale valg i hvert trinn med håp om å finne en globalt optimal løsning. De brukes mye til å løse ulike planleggingsproblemer der oppgaver må tildeles ressurser effektivt og innenfor bestemte begrensninger.

Forstå greedy algoritmer

En grådig algoritme bygger opp en løsningsbit etter stykke, alltid velge det neste stykket som tilbyr den mest umiddelbare fordelen. Denne tilnærmingen er enkel og ofte effektiv, noe som gjør det egnet for problemer der optimale løsninger kan oppnås gjennom lokal optimalisering.

Søknader i Planlegging

I planleggingsproblemer brukes grådige algoritmer til å tildele ressurser som tidsautomater, maskiner eller personell. De hjelper i oppgaver som jobbplanlegging, oppgaveprioritering og ressurstildeling, som tar sikte på å minimere total ferdigstillelsestid eller maksimere ressursutnyttelsen.

Vanlige planleggingsproblemer

  • Aktivitetsvalg Problem: Velger det maksimale antall aktiviteter som ikke overlapper.
  • Interval Planlegging: Tildeler ressurser til oppgaver med start og slutttider.
  • Job Planlegger med Deadlines: Planlegger jobber for å møte tidsfrister mens den minimerer seniteten.
  • Resource Alocation: Skill mellom begrensede ressurser blant konkurrerende oppgaver.