Brute force

Brute force er et datalogiudtryk der dækker over en udtømmende afsøgning af et løsningsrum, f.eks. afprøvning af samtlige mulige input til en funktion, indtil det ønskede resultat optræder. Metoden betegnes undertiden, når snedigere og hurtigere metoder kendes, som brute force and ignorance.

Eksempler på brute force:

• Primtalsfaktorisering af et tal n, hvor n divideres med samtlige tal fra 2 til og med n. Dette er også et eksempel på at en lille smule omtanke kan reducere indsatsen voldsomt i forhold til brute force; idet man f.eks. kan nøjes med 2 og alle ulige tal fra 3 og op til ${\displaystyle {\sqrt {n}}}$.
• Opgaven at placere 8 dronninger på et skakbræt, så ingen af dem truer hinanden. En brute force-strategi i dette tilfælde kunne være at undersøge samtlige mulige placeringer af dronninger på skakbrættet. Denne metode vil kræve undersøgelse af 178.462.987.637.760 (64 * 63 * 62 * 61 * 60 * 59 * 58 * 57) forskellige positioner, hvilket understreger at selv simpelt udseende problemer kan have et meget stort antal løsninger.
• Afsøgning af samtlige mulige nøgler til en krypteret tekst. Se brute force-angreb.

Brute force-algoritmer er simple at konstruere, og vil altid finde en løsning på problemet, hvis en sådan findes. Problemet er at der for mange problemformuleringer er et meget stort antal potentielle løsninger. Ofte vil antallet af mulig løsninger vokse langt hurtigere end antallet af frihedsgrader. For eksempel er der med 4 dronninger på et 4x4 udsnit af et skakbræt kun 43.680 mulige løsninger at undersøge.

På grund af disse forhold er brute force-algoritmer kun anvendelige når det mulige antal løsninger er lille, eller når der findes en metode til begrænsning af mulighederne. Et eksempel er 8-dronning problemet, hvor man på forhånd indser at der kun kan være en dronning for hver række og kolonne. Denne overvejelse indskrænker det oprindelige problem til 40.320 mulige løsninger.

Brute force-algoritmens opbygning

Løsning af et problem ved hjælp af brute force kræver fire funktioner, start, næste, kontrol og uddata. Disse funktioner har som input en parameter P, der beskriver det specifikke problem der ønskes løst. Funktionernes opførsel er:

1. start (P): starten af løsningsrummet P.
2. næste (P, c): den næste mulige løsning af P efter den nuværende c.
3. kontrol (P, c): afgør om c er en løsning til P.
4. uddata (P, c): udskriv (eller benyt) løsningen c af P som det ønskes.

Funktionen næste skal også fortælle om der er flere løsningskandidater til P efter den nuværende c. En ofte anvendt metode er at returnere en løsningskandidat A, der uden videre kan genkendes som værende udenfor løsningsrummet. Tilsvarende skal funktionen start returnere A, hvis der slet ikke findes løsningskandidater. Brute force-metoden kan herefter udtrykkes som:

c ${\displaystyle \gets }$ start(P)
while c ${\displaystyle \neq }$ Λ do
  if kontrol(P,c) then uddata(P, c)
  c ${\displaystyle \gets }$ næste(P,c)