Căutare cu forță brută - Brute-force search

În informatică , căutarea forței brute sau căutarea exhaustivă , cunoscută și sub numele de generare și testare , este o tehnică de rezolvare a problemelor și o paradigmă algoritmică foarte generală care constă în enumerarea sistematică a tuturor candidaților posibili pentru soluție și verificarea dacă fiecare candidat satisface afirmația problemei. .

Un algoritm de forță brută care găsește divizorii unui număr natural n ar enumera toate numerele întregi de la 1 la n și ar verifica dacă fiecare dintre ele împarte n fără rest. O abordare cu forță brută pentru puzzle-ul celor opt regine ar examina toate aranjamentele posibile din 8 piese pe tabla de șah de 64 de pătrate și pentru fiecare aranjament, va verifica dacă fiecare piesă (regină) poate ataca oricare alta.

În timp ce o căutare cu forță brută este ușor de implementat și va găsi întotdeauna o soluție dacă există, costurile de implementare sunt proporționale cu numărul de soluții candidate - care, în multe probleme practice, tinde să crească foarte repede pe măsură ce dimensiunea problemei crește ( § Explozie combinatorie ). Prin urmare, căutarea cu forță brută este de obicei utilizată atunci când dimensiunea problemei este limitată sau când există euristici specifice problemei care pot fi utilizate pentru a reduce setul de soluții candidate la o dimensiune gestionabilă. Metoda este utilizată și atunci când simplitatea implementării este mai importantă decât viteza.

Acesta este cazul, de exemplu, în aplicațiile critice în care orice erori din algoritm ar avea consecințe foarte grave sau atunci când se utilizează un computer pentru a demonstra o teoremă matematică . Căutarea cu forță brută este, de asemenea, utilă ca metodă de bază atunci când se compară alți algoritmi sau metaheuristică . Într-adevăr, căutarea cu forță brută poate fi privită ca fiind cea mai simplă metaheuristică . Căutarea forței brute nu trebuie confundată cu retrocedarea , unde seturile mari de soluții pot fi aruncate fără a fi enumerate în mod explicit (ca în soluția computerizată manuală la problema celor opt regine de mai sus). Metoda forței brute pentru a găsi un articol într-un tabel - și anume, verifica toate intrările acestuia din urmă, secvențial - se numește căutare liniară .

Implementarea căutării cu forță brută

Algoritm de bază

În ordine candidat pentru P după cel actual c .

valabil ( P , c ): Verificați dacă candidatul c este o soluție pentru P .
ieșire ( P , c ): utilizați soluția c din P după cum este adecvat aplicației.

Următoarea procedură trebuie , de asemenea , spune când nu există mai mulți candidați pentru instanță P , după cel curent c . O modalitate convenabilă de a face acest lucru este de a returna un „candidat nul”, o anumită valoare convențională a datelor Λ care este distinctă de orice candidat real. În mod similar, prima procedură ar trebui să se întoarcă Λ în cazul în care nu există candidați , la toate pentru instanță P . Metoda forței brute este apoi exprimată prin algoritm

c ← first(P)
while c ≠ Λ do
    if valid(P,c) then
        output(P, c)
    c ← next(P, c)
end while

De exemplu, atunci când căutați divizorii unui număr întreg n , datele de instanță P sunt numărul n . Apelul primul ( n ) trebuie să returneze întreg 1 dacă n ≥ 1, sau Λ altfel; apelul următor ( n , c ) ar trebui să returneze c + 1 dacă c < n și Λ în caz contrar; și valid ( n , c ) ar trebui să returneze adevărat dacă și numai dacă c este divizor al lui n . (De fapt, dacă vom alege Λ să fie n + 1, testele n ≥ 1 și c < n sunt inutile.) Algoritmul de căutare forță brută de mai sus va suna de ieșire pentru fiecare candidat , care este o soluție la instanță dată P . Algoritmul este ușor modificat pentru a se opri după găsirea primei soluții sau a unui număr specificat de soluții; sau după testarea unui număr specificat de candidați sau după ce ați petrecut o anumită cantitate de timp CPU .

Explozie combinatorie

Principalul dezavantaj al metodei forței brute este că, pentru multe probleme din lumea reală, numărul candidaților naturali este prohibitiv de mare. De exemplu, dacă căutăm divizorii unui număr așa cum este descris mai sus, numărul de candidați testați va fi numărul dat n . Deci, dacă n are șaisprezece cifre zecimale, să spunem, căutarea va necesita executarea a cel puțin 10 ¹⁵ instrucțiuni de computer, care vor dura câteva zile pe un computer tipic . Dacă n este un număr natural aleatoriu pe 64 de biți , care are în medie aproximativ 19 cifre zecimale, căutarea va dura aproximativ 10 ani. Această creștere accentuată a numărului de candidați, pe măsură ce crește dimensiunea datelor, apare în tot felul de probleme. De exemplu, dacă căutăm o anumită rearanjare de 10 litere, atunci avem 10! = 3.628.800 de candidați de luat în considerare, pe care un PC tipic îi poate genera și testa în mai puțin de o secundă. Cu toate acestea, adăugarea unei alte litere - care reprezintă doar o creștere de 10% a dimensiunii datelor - va înmulți numărul candidaților cu 11, o creștere de 1000%. Pentru 20 de litere, numărul de candidați este de 20 !, ceea ce înseamnă aproximativ 2,4 × 10 ¹⁸ sau 2,4 chintillion ; iar căutarea va dura aproximativ 10 ani. Acest fenomen nedorit este denumit în mod obișnuit explozia combinatorie sau blestemul dimensionalității .

Un exemplu de caz în care complexitatea combinatorie duce la limita de solvabilitate este rezolvarea șahului . Șahul nu este un joc rezolvat . În 2005, toate finalurile jocului de șah cu șase piese sau mai puțin au fost rezolvate, arătând rezultatul fiecărei poziții dacă a fost jucat perfect. A fost nevoie de încă zece ani pentru a completa baza de masă cu încă o piesă de șah adăugată, completând astfel o bază de masă de 7 bucăți. Adăugarea unei piese în plus la un final de șah (făcând astfel o bază de masă de 8 piese) este considerată intratabilă datorită complexității combinatorii adăugate.

Accelerarea căutărilor cu forță brută

O modalitate de a accelera un algoritm de forță brută este de a reduce spațiul de căutare, adică setul de soluții candidate, prin utilizarea euristicilor specifice clasei de probleme. De exemplu, în problema celor opt regine , provocarea este de a plasa opt regine pe o tablă de șah standard, astfel încât nici o regină să nu atace pe alta. Deoarece fiecare regină poate fi plasată în oricare dintre cele 64 de pătrate, în principiu există 64 ⁸ = 281.474.976.710.656 posibilități de luat în considerare. Cu toate acestea, deoarece reginele sunt toate la fel și că nu pot fi așezate două regine pe același pătrat, candidații sunt toate modalitățile posibile de a alege un set de 8 pătrate din set toate cele 64 de pătrate; ceea ce înseamnă 64 alege 8 = 64! / (56! * 8!) = 4.426.165.368 soluții candidate - aproximativ 1 / 60.000 din estimarea anterioară. Mai mult, niciun aranjament cu două regine pe același rând sau aceeași coloană nu poate fi o soluție. Prin urmare, putem restrânge în continuare setul de candidați la aceste aranjamente.

Așa cum arată acest exemplu, un pic de analiză va duce adesea la reduceri dramatice ale numărului de soluții candidate și poate transforma o problemă intraductibilă într-una banală.

În unele cazuri, analiza poate reduce candidații la setul tuturor soluțiilor valabile; adică poate produce un algoritm care enumeră direct toate soluțiile dorite (sau găsește o soluție, după caz), fără a pierde timpul cu testele și generarea de candidați invalizi. De exemplu, pentru problema „găsiți toți numerele între 1 și 1.000.000 care sunt divizibile în mod egal cu 417” o soluție naivă de forță brută ar genera toate numerele întregi din interval, testând fiecare dintre ele pentru divizibilitate. Cu toate acestea, această problemă poate fi rezolvată mult mai eficient începând cu 417 și adăugând în mod repetat 417 până când numărul depășește 1.000.000 - ceea ce necesită doar 2398 (= 1.000.000 ÷ 417) pași și fără teste.

Reordonarea spațiului de căutare

În aplicațiile care necesită o singură soluție, mai degrabă decât toate soluțiile, timpul de funcționare așteptat al unei căutări cu forță brută va depinde adesea de ordinea în care sunt testați candidații. Ca regulă generală, ar trebui să testăm mai întâi cei mai promițători candidați. De exemplu, atunci când căutați un divizor adecvat al unui număr aleatoriu n , este mai bine să enumerați divizorii candidati în ordine crescătoare, de la 2 la n - 1 , decât invers - deoarece probabilitatea ca n este divizibil cu c este 1 / c . Mai mult decât atât, probabilitatea ca un candidat să fie valid este adesea afectată de studiile anterioare nereușite. De exemplu, ia în considerare problema de a găsi un 1 bit într - un șir de caractere dat 1000 de biți P . În acest caz, soluțiile candidate sunt indicii 1 la 1000, iar un candidat c este valid dacă P [ c ] = 1 . Acum, să presupunem că primul bit al lui P este la fel de probabil să fie 0 sau 1 , dar fiecare bit ulterior este egal cu cel anterior cu 90% probabilitate. Dacă candidații sunt enumerați în ordine crescătoare, de la 1 la 1000, numărul t de candidați examinați înainte de succes va fi de aproximativ 6, în medie. Pe de altă parte, dacă candidații sunt enumerați în ordinea 1,11,21,31 ... 991,2,12,22,32 etc., valoarea așteptată a t va fi doar puțin mai mult de 2. Mai mult în general, spațiul de căutare ar trebui să fie enumerat în așa fel încât următorul candidat să fie cel mai probabil să fie valid, având în vedere că studiile anterioare nu au fost . Deci, dacă soluțiile valabile sunt probabil „grupate” într-un anumit sens, atunci fiecare nou candidat ar trebui să fie cât mai departe posibil de cele anterioare, în același sens. Discuția se menține, desigur, dacă soluțiile sunt probabil răspândite mai uniform decât se aștepta întâmplător.

Alternative la căutarea cu forță brută

Există multe alte metode de căutare, sau metaheuristică, care sunt concepute pentru a profita de diferite tipuri de cunoștințe parțiale pe care le putem avea despre soluție. Euristicile pot fi, de asemenea, folosite pentru a face o tăiere timpurie a unor părți ale căutării. Un exemplu în acest sens este principiul minimax pentru căutarea copacilor de joc, care elimină mulți subarburi într-un stadiu incipient al căutării. În anumite domenii, cum ar fi analiza limbajului, tehnici precum analiza grafică pot exploata constrângerile problemei pentru a reduce o problemă de complexitate exponențială într-o problemă de complexitate polinomială. În multe cazuri, cum ar fi în Probleme de satisfacție a constrângerilor , se poate reduce dramatic spațiul de căutare prin propagarea constrângerii , care este implementată eficient în limbajele de programare Constraint . Spațiul de căutare pentru probleme poate fi, de asemenea, redus prin înlocuirea problemei complete cu o versiune simplificată. De exemplu, în șahul computerului , mai degrabă decât să calculeze arborele minimax complet al tuturor mișcărilor posibile pentru restul jocului, se calculează un arbore mai limitat de posibilități minimax, arborele fiind tăiat la un anumit număr de mișcări, iar restul a arborelui fiind aproximată printr-o funcție de evaluare statică .

În criptografie

În criptografie , un atac cu forță brută implică verificarea sistematică a tuturor cheilor posibile până când se găsește cheia corectă. Această strategie poate fi utilizată, teoretic, împotriva oricăror date criptate (cu excepția unui tampon unic ) de către un atacator care nu este capabil să profite de vreo slăbiciune dintr-un sistem de criptare care altfel i-ar ușura sarcina.

Lungimea cheii utilizate în criptare determină fezabilitatea practica de a efectua un atac brute force, cu chei mai lungi exponențial mai dificil de a sparge decât cele mai scurte. Atacurile cu forță brută pot fi mai puțin eficiente prin ascunderea datelor care urmează a fi codificate, ceea ce face mai dificil pentru un atacator să recunoască atunci când a spart codul. Una dintre măsurile de rezistență a unui sistem de criptare este cât timp ar dura teoretic un atacator să lanseze un atac de forță brută cu succes împotriva acestuia.

Languages

In other projects