subproblemet

Subproblemet er en mindre forekomst av et større problem som må løses for å kunne løse det opprinnelige problemet. I informatikk og matematikk brukes ofte problemdeling, der et komplekst problem deles inn i ett eller flere subproblemer som har liknende struktur som hovedproblemet.

Når subproblemene løses, kan løsningene kombineres for å danne en løsning av det overordnede problemet. Dette mønsteret kjennetegnes av to viktige egenskaper: optimal delstruktur og overlappende delproblemer. Optimal delstruktur betyr at en optimal løsning kan bygges av optimale løsninger av delproblemene. Overlappende delproblemer betyr at samme subproblem ofte dukker opp flere ganger i beregningen, slik at løsningene på subproblemene kan gjenbrukes.

Metoder som ofte brukes inkluderer rekursjon, divide-and-conquer-teknikker, dynamisk programmering og memoisering. Når subproblemene overlapper og deres løsninger kan lagres og gjenbrukes, gir dette ofte betydelige effektiviseringer.

Eksempel: i fibonaccifunksjonen beregnes F(n) som F(n-1) pluss F(n-2). Hver beregning skaper subproblemene som ofte løses flere ganger i en naiv rekursiv løsning. Ved å lagre løsningen på hvert subproblem (memoisering) eller ved å beregne dem i riktig rekkefølge (dynamisk programmering), fås en betydelig raskere løsning.

Subproblemet er derfor en grunnleggende byggestein i mange algoritmer og problemløsningsmetoder, og forståelse av dets egenskaper er sentralt for design av effektive løsninger.