Brute force er etdatalogiudtryk 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, sombrute force and ignorance.

Eksempler på brute force:

• Primtalsfaktorisering af et taln, hvorndivideres med samtlige tal fra 2 til og medn. 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 placere8 dronninger på etskakbræ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 muligenøgler til enkrypteret tekst. Sebrute 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 affrihedsgrader. 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.

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

1. start (P): starten af løsningsrummetP.
2. næste (P,c): den næste mulige løsning afP efter den nuværendec.
3. kontrol (P,c): afgør omc er en løsning tilP.
4. uddata (P,c): udskriv (eller benyt) løsningenc afP som det ønskes.

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

c${\displaystyle \leftarrow }$start(P)whilec${\displaystyle \ne }$ Λdoifkontrol(P,c)thenuddata(P,c)c${\displaystyle \leftarrow }$næste(P,c)

• Datalogi