Heuristik

Baggrund

Heuristik er kunsten at finde en passende løsning på et problem ved hjælp af begrænset viden og kort tid. Mere formelt set er heuristikker baseret på erfaring; de kan fremskynde søgningen efter en løsning ved hjælp af enkle regler. En fuldstændig søgning kan tage for lang tid eller være for vanskelig at gennemføre.

Mere præcist er heuristikker strategier, der anvender let tilgængelige, men løst anvendelige oplysninger til at styre problemløsning hos mennesker og maskiner.

Heuristik kan anvendes inden for nogle videnskabelige områder, men ikke inden for andre: I økonomi er en løsning, der er en procent forkert, ofte acceptabel; et teleskop, der har en fejl på en grad, er sandsynligvis ubrugeligt, hvis det er rettet mod et fjerntliggende objekt. Det samme teleskop, der er rettet mod vinduet på den anden side af gaden, vil sandsynligvis tolerere denne fejl; en fejl på én grad vil ikke have stor betydning på en kort afstand.

Heuristik kan bruges til at estimere et svar, som derefter gøres mere klart ved at udføre en nøjagtig løsning i meget lille skala, måske for at spare tid, penge eller arbejdskraft på et projekt - f.eks. kan et heuristisk gæt på, hvor meget vægt en bro forventes at kunne bære, bruges til at bestemme, om broen skal være lavet af træ, sten eller stål, og passende mængder af det nødvendige materiale kan købes, mens den nøjagtige konstruktion af broen færdiggøres.

Brugen af heuristikker på visse meget tekniske områder kan dog være skadelig - datalogi er et eksempel herpå. Programmering af en computer til at udføre mere eller mindre de ønskede handlinger kan resultere i alvorlige fejl. Derfor skal computeropgaver generelt være ret nøjagtige. Der er dog visse områder, hvor computere kan beregne heuristiske løsninger uden risiko - Googles søgeteknologi er f.eks. stærkt afhængig af heuristik, idet den producerer "næsten-miss"-matches til en søgeforespørgsel, når der ikke kan findes et nøjagtigt match. Dette giver brugeren mulighed for at rette op på eventuelle fejl, som søgningen giver. Eksempel: Hvis man søger efter navnet "Peter Smith" og ikke kan finde det nøjagtige navn, matcher søgemaskinen heuristisk "Pete Smith" i stedet, og den person, der bruger søgemaskinen, skal afgøre, om Pete og Peter er den samme person.

Eksempler

Polya

Her er nogle andre almindeligt anvendte heuristikker fra Polya's bog fra 1945, How to Solve It:

• Hvis du har svært ved at forstå et problem, kan du prøve at tegne et billede.
• Hvis du ikke kan finde en løsning, kan du prøve at antage, at du har en løsning, og se, hvad du kan udlede heraf ("arbejde baglæns").
• Hvis problemet er abstrakt, kan du prøve at undersøge et konkret eksempel.
• Prøv først at løse et mere generelt problem: "Opfinderens paradoks": den mere ambitiøse plan har måske større chancer for at lykkes.

Problemer med pakning

Et eksempel, hvor heuristikker er nyttige, er en slags pakningsproblem. Problemet består i at pakke en række genstande. Der er regler, der skal overholdes. F.eks. har hver genstand en værdi og en vægt. Problemet er nu at få de mest værdifulde genstande med den mindst mulige vægt. Et andet eksempel er at få plads til en række genstande af forskellig størrelse på et begrænset sted, f.eks. i bagagerummet på en bil.

For at få den perfekte løsning på problemet skal alle muligheder afprøves. Dette er ofte ikke en god løsning, da det tager lang tid at prøve dem, og i gennemsnit skal halvdelen af mulighederne prøves, indtil der er fundet en løsning. Så det, de fleste mennesker vil gøre, er at starte med den største genstand, få plads til den og derefter forsøge at arrangere de andre genstande omkring den. Dette vil give en god løsning, for det meste. Der er dog tilfælde, hvor en sådan løsning er meget dårlig, og hvor en anden teknik må anvendes.

Der er derfor tale om en heuristisk løsning.

Eksempel på et pakningsproblem. Dette er et endimensionelt (med begrænsninger) Knapsack-problem: Hvilke kasser skal vælges for at maksimere pengebeløbet og holde den samlede vægt under 15 kg? Et flerdimensionelt problem kunne tage hensyn til kassernes tæthed eller dimensioner, sidstnævnte er et typisk pakningsproblem. (Løsningen i dette tilfælde er at vælge alle kasserne ud over den grønne).