Underproblemer

Underproblemer, eller delproblemer, er mindre opgaver som tilsammen udgør et større problem. Ved at opdele et problem i mindre dele kan hver del løses separat og derefter kombineres for at få en løsning på det oprindelige problem. Denne tilgang anvendes bredt i problemløsning og algoritmedesign.

I algoritmedesign bruges underproblemer særligt i metoder som rekursion og dynamisk programmering. Løsningen af hovedproblemet defineres ofte gennem løsningen af flere underproblemer og sammensætningen af deres løsninger. Ofte har man basale tilfælde, der ikke kan deles yderligere, som fungerer som endepunkter i rekursionen.

Eksempler: Fibonacci-tal, hvor F(n) = F(n-1) + F(n-2), kan udtrykkes som to underproblemer. Merge sort deler en liste i halve, løser hver halvdel som underproblem og fletter resultaterne. I korteste-vej-problemer beregnes ofte korteste afstande til mellemliggende noder og kombineres derefter til den endelige løsning.

Vigtige egenskaber er overlappende underproblemer og optimal understruktur. Overlappende underproblemer betyder, at de samme subproblemer opstår flere gange, hvilket gør memoisering eller bottom-up dynamisk programmering særligt effektivt. Optimal understruktur betyder, at en optimal løsning til hovedproblemet består af optimale løsninger til sine underproblemer.

Anvendelser spænder fra undervisning i problemløsning til softwareudvikling og forskning, hvor opdeling af komplekse opgaver i mindre dele letter forståelse, test og vedligeholdelse.

Se også: dynamisk programmering, divide and conquer.