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. Ved at udnytte at der højst kan stå en dronning i hver række og søjle kan antallet af placeringer, der skal undersøges, reduceres til 40.320 (8!).
• 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.