Heuristik: Definition, typer, eksempler og brug i algoritmer
Lær hvad heuristik er — definition, typer, praktiske eksempler og anvendelse i algoritmer. Forstå fordele, begrænsninger og hvordan heuristikker forbedrer løsninger.
En heuristik er en praktisk måde at løse et problem på. Det er bedre end tilfældigheder, men det virker ikke altid. En person udvikler en heuristik ved at bruge intelligens, erfaring og sund fornuft. Forsøg og fejl er den enkleste heuristik, men også en af de svageste. Tommelfingerregel og "kvalificerede gæt" er andre betegnelser for simple heuristikker. Da en heuristik ikke er sikker på at opnå et resultat, er der altid undtagelser. Ordet kommer fra det græske heuriskein, "at finde" eller "at opdage" — derfor bruges heuristikker ofte, når en sikker eller fuldstændig løsning er svær eller dyr at opnå.
Nogle gange er heuristikker ret vage: "Se før du springer" er en vejledning i adfærd, men "tænk over konsekvenserne" er lidt mere klart. Nogle gange er en heuristik en hel række trin. Når læger undersøger en patient, gennemgår de en hel række prøver og observationer. De finder måske ikke ud af, hvad der er galt, men de giver sig selv den bedste chance for at lykkes. Dette kaldes en diagnose. I praksis kombineres ofte flere heuristikker: enkle regler, tjeklister og prioriteringsregler, så arbejdet bliver både hurtigt og robust.
Inden for datalogi er en "heuristik" en slags algoritme. Algoritmer skrives for at finde en god løsning på et problem. En heuristisk algoritme kan normalt finde ret gode løsninger, men der er ingen garanti eller beviser for, at løsningerne er korrekte. Den tid, det tager at køre algoritmen, er en anden faktor at tage i betragtning. Heuristikker bruges især, når eksakt beregning er for langsom (NP‑hårde problemer), eller når man har brug for et svar hurtigt i en praktisk situation.
Typer af heuristikker
- Enkle tommelfingerregler: Let anvendelige regler, fx "vælg den billigste løsning først".
- Forsøg og fejl: Prøv muligheder og lær af resultaterne — enkel, men ofte ineffektiv.
- Grådige algoritmer: Vælger lokalt bedste valg i håb om et godt globalt resultat (fx i knapsack‑approximation).
- Lokalsøgning: Ændr en nuværende løsning lidt ad gangen for at finde forbedringer (hill climbing, tabu search).
- Metaheuristikker: Overordnede strategier der styrer søgningen, fx simulated annealing og genetiske algoritmer.
- Admissible heuristics: I søgealgoritmer (fx A*) bruges heuristikker der aldrig overvurderer omkostningen til målet for at sikre optimalitet under visse betingelser.
Eksempler
- Hverdagsbeslutninger: "Se før du springer", "køb billigere mærke først".
- Medicinsk diagnose: Læger bruger tjeklister og mønstre for at indsnævre mulige sygdomme.
- Ruteplanlægning: Brug af nærmeste‑nabo‑valg eller heuristikker der estimerer afstand til mål (som i A*).
- Optimering: Til f.eks. skemalægning eller routing bruger man ofte lokal søgning eller genetiske algoritmer for at finde gode løsninger hurtigt.
- Kognitionsforskning: Menneskelige heuristikker som tilgængelighed (availability), repræsentativitet og forankring (anchoring) forklarer hurtige beslutninger — men også systematiske fejl (bias).
Fordele og ulemper
- Fordele: Hurtigere beslutninger, lavere beregningsomkostning, praktisk anvendelige i virkelige problemer, ofte tilstrækkeligt gode løsninger.
- Ulemper: Ingen garanti for optimalitet eller korrekthed, kan give fejl eller bias, kræver ofte tuning og empirisk evaluering.
Hvornår bør man bruge heuristikker?
- Når eksakte metoder er for langsomme eller umulige i praksis.
- Når man skal have et svar hurtigt og kan tolerere, at det ikke er perfekt.
- Når man vil kombinere hurtige vurderinger med efterfølgende kontrol eller verifikation (fallback til dyrere, sikre metoder ved behov).
Vurdering og bedste praksis
- Test heuristikken empirisk på realistiske eksempler for at måle kvalitet og robusthed.
- Tune parametre og kombinér flere heuristikker for bedre præstation.
- Overvåg resultater i produktion og hav sikkerhedscheck, hvis fejlagtige svar kan få alvorlige konsekvenser.
- For kritiske anvendelser (medicin, sikkerhed) brug heuristik som støtte til — ikke erstatning for — formel verifikation eller ekspertevaluering.
Sammenfattende er heuristikker nyttige redskaber både i dagligdagen og i datalogi: de gør komplekse problemer håndterbare ved at bytte fuldstændig sikkerhed for hurtighed og praksisnær anvendelighed. Forståelse af deres begrænsninger og omhyggelig testning gør dem mest effektive.
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).
Spørgsmål og svar
Spørgsmål: Hvad er en heuristik?
Svar: En heuristik er en praktisk måde at løse et problem på, som er bedre end tilfældighederne, men som ikke altid virker.
Q: Hvordan udvikles heuristikker?
Svar: En person udvikler en heuristik ved at bruge intelligens, erfaring og sund fornuft.
Spørgsmål: Hvad er den enkleste heuristik?
Svar: Den enkleste heuristik er forsøg og fejl.
Spørgsmål: Hvad er andre navne for simple heuristikker?
A: Andre navne på simple heuristikker er tommelfingerregler og "kvalificerede gæt".
Spørgsmål: Er der altid undtagelser fra heuristikken?
A: Ja, da det ikke er sikkert, at en heuristik giver et resultat, er der altid undtagelser.
Spørgsmål: Hvad er en diagnose inden for lægevidenskaben?
A: En diagnose er en hel række faser, som lægerne gennemgår, når de undersøger en patient, for at give sig selv de bedste chancer for at få succes.
Spørgsmål: Hvad er en "heuristik" inden for datalogi?
A: Inden for datalogi er en heuristik en slags algoritme, som normalt kan finde ret gode løsninger, men der er ingen garanti for eller beviser for, at løsningerne er korrekte.
Søge