Iscrpna pretraga

U računarstvu, brute-force pretraga(gruba sila) ili iscrpljujuća pretraga, takođe poznata i kao generiši i testiraj, je opšta tehnika rešavanja problema koja se sastoji od sistematičnog nabrajanja svih mogućih kandidata za rešavanje i provere da li svaki kandidat zadovoljava problem.

Da bi brut-force algoritam pronasao delioce prirodnog broja n, on nabraja sve cele brojeve od 1 do korena iz n, i proverava da li svaki od njih deli n bez ostatka. Brut-force pristup za problem osam dama ispituje sve moguće aranžmane od 8 delova na 64-kvadratnoj šahovskoj tabli, i, za svaki aranžman, proverava da li svaki (dama) deo može da napadne bilo koji drugi.

Dok je brut-force pretraga jednostavna za primenu, i uvek će pronaći rešenje ako postoji, njegova cena srazmerna je broju kandidata rešenja – što u mnogim praktičnim problemima pretenduje veoma brzim rastom kako se veličina problema povećava. Dakle, brute-force pretraga se obično koristi kada je veličina problema ograničena, ili kada postoji specifičan problem heuristike koji može biti iskorišćen da se smanji skup kandidata rešenja do veličine pogodne za rukovanje. Metoda se takođe koristi kada je jednostavnost implementacije važnija od brzine.

To je slučaj, na primer, u kritičnim aplikacijama gde svaka greška u algortimu ima veoma ozbiljne posledice; ili kada koristite računar da dokažete matematičku teoremu. Brute-force pretraga je takodje korisna i kao "osnovni" method kod benčmarkinga drugih algoritama ili metaheuristike. Zaista, brute-force pretraživanje se može posmatrati kao najjednostavniji metaheuristik. Brute force pretraživanje ne treba mešati sa bektrekingom, gde veliki skupovi rešenja mogu biti odbačeni bez eksplicitnog nabrajanja. Brute-force metoda za pronalaženje stavki u tabeli - naime, proverava sve stavke ovih drugih, sekvencijalno – se zove linearna pretraga.

Implementacija brute-force pretrage

Osnovni algoritam

U želji da se brute-force pretraga primeni na određenu klasu problema, moraju se sprovesti četiri funckije, prvo-first,sledeće-next, validno-valid, i izlaz-output. Ova procedura treba da uzme kao parametar P u konkretnom slučaju problema koje treba rešiti, a trebalo bi da uradi sledeće:

1. first (P): generiše rešenje kandidata za prvo P.
2. next (P, c): generisati sledeći kandidat za P nakon trenutne c.
3. valid (P, c): proverite da li kandidat c je rešenje za P.
4. output (P, c): koristiti rešenje c od P kao pogodno za primenu.

Sledeći postupak mora reći kada više ne postoje kandidati za primer P, nakon sadašnjeg c. Pogodan način za to je da se vrati na "nultu kandidata", neki konvencionalni podatak vrednost i Λ da se razlikuje od stvarnog kandidata. Isto tako prvo treba da vrati Λ ako uopšte nema kandidata za primer P. Brute-force metoda se zatim opisuje algoritmom

c $\gets$ first(P)
while' c $\neq$ Λ do
 if' valid(P,c) then output(P, c)
 c $\gets$ next(P,c)
end while

Na primer, kada je u potrazi za deliocima broj n, instanca podatka P je broj n. Poziv first(n) treba da vrati 1 ako n $\geq$ 1, ili Λ inače; poziv next(n,c) treba da vrati c + 1 ako c $<$ n, i Λ inače; i valid(n,c) treba da vratitačno ako i samo ako c je delilac za n. (U stvari, ako odaberete Λ da bude n + 1, test n $\geq$ 1 i c $<$ n je nepotreban.)Brute-force algoritam za pretragu pozvaće output za svakog kandidata koji je rešenje u datoj instanci P. Algoritam se lako modifikuje da se zaustavi posle pronalaženju prvog rešenja, ili određenog broja rešenja, ili nakon testiranja određenog broja kandidata, ili nakon što je proveo datu količinu procesorskog vremena.

Kombinatorne eksplozije

Glavni nedostatak brute-force metode je da je, za mnoge realne probleme, broj prirodnih kandidata preterano veliki. Na primer, ako tražimo delilac broja kao što je gore opisano, broj testiranih kandidata će biti upravo dat broj n. Dakle, ako n ima šesnaest decimalnih cifara, kaže, pretraga će zahtevati izvršenje najmanje 10¹⁵ instrukcija, što će zauzeti nekoliko dana na tipičnom računaru. Ako je n slučajni 64-bitni prirodan broj, koji ima 19 cifara u proseku, pretraga će trajati oko 10godina. Ovaj strmi porast u broju kandidata, kako i veličina podataka raste, javlja se u svim vrstama problema. Na primer, ako tražimo određeno preuređenje od 10 slova, onda imamo 10! = 3.628.800 kandidata za razmatranje, što tipičan PC može da generiše i testira za manje od jedne sekunde. Međutim, dodajući još jedno slovo — što je samo 10% povećanja veličine podataka — povećaće broj kandidata na 11 — za 1000%. Za 20 slova, broj kandidata je 20!, što je oko 2.4×10¹⁸ ili 2.4 triliona; i pretraga će trajati oko 10 godina. Ovaj nepoželjan fenomen se obično zove kombinatorna eksplozija, ili prokletstvo dimenzionalnosti..

Ubrzavanje brute-force pretrage

Jedan od načina da se ubrza brute-force algoritam je da se smanji prostor za pretragu, odnosno, skup kandidata rešenja, koristeći heuristiku specifične klase problema. Na primer, u problem osam dama izazov je da se postavi osam kraljica na standardnoj šahovskoj tabli tako da nijedna dama ne napada bilo koju drugu. Pošto svaka dama može da se postavi u bilo koji od 64 kvadrata, u principu postoje 64⁸ = 281.474.976,710,656 mogućnosti koje treba razmotriti. Međutim, pošto su sve dame podjednake, a nikoje dve mogu biti postavljene na istom kvadratu, kandidati su kombinacije seta od 8 kvadrata iz skupa svih 64 kvadrata; što znači 64 bira 8 = 64!/56!/8! = 4.426.165,368 kandidata rešenja — oko 1/60,000 prethodne procene. Dalje, rešenje sa dve dame u istoj redu ili koloni ne može biti rešenje. Zbog toga, možemo dalje da ograničimo skup tih kandidata.

Kao što ovaj primer pokazuje, malo analize često će dovesti do drastičnog smanjenja broja kandidata rešenja, a može pretvoriti i nepodnošljiv u trivijalan problem.

U nekim slučajevima, analiza može smanjiti kandidate na skup svih važećih rešenja; to jest, ona može dati algoritam koji direktno nabraja sva željena rešenja (ili nađe jedno rešenje, po potrebi), bez gubljenja vremena sa testovima i nevažećim kandidatima. Na primer, za problem "naći sve cele brojeve između 1 i 1.000.000 da su ravnomerno deljivi sa 417" naivni brute-force će generisati sve cele brojeve u opsegu, testirajući svaki od njih za deljivost. Međutim, taj problem se može rešiti mnogo efikasnije počinjuući sa 417 i više puta dodajući 417 dok broj prelazi 1.000.000 - što traje samo 2398 (= 1.000.000 ÷ 417) koraka, i nema testova.

Menjanje redosleda pretrage prostora

U aplikacijama koje zahtevaju samo jedno rešenje, a ne sva rešenja, očekivana vrednost izvršavanja brute force pretrage često će zavisit od reda u kojem su kandidati testirani. Kao generalno pravilo, treba prvo testirati najperspektivnije kandidate. Na primer, u potrazi za pogodnim deliocem za slučajni broj n, bolje je nabrojati delioce kandidata u rastućem redosledu, od 2 do n – 1, nego obrnuto — jer je verovatnoća da je n deljiv sa c 1/c. Štaviše, na verovatnoću kandidata da je validan često utiču prethodna neuspela pokušavanja. Na primer, razmotriti problem pronalaženja 1 bita u datom 1000-bitnom nizu P. U ovom slučaju, kandidati rešenja su indeksi 1 to 1000, i kandidat c je validan ako P[c] = 1. Sada, pretpostavimo da je prvi bit P jednako verovatno da će biti 0 ili 1, ali posle toga svaki bit je jednak prethodnom sa 90% verovatnoće. Ako su kandidati nabrojani u rastućem poretku, 1 do 1000, broj t kandidata ispitatanih pre nego uspeha će biti oko 6, u proseku. Na drugu stranu, ako su kandidati numerisani u redu 1.11.21,31...991,2,12,22,32 itd., očekivana vrednost t biče samo malo manja od 2. Uopšteno, prostor pretrage treba se nabrojati na takav način da je sledeći kandidat najverovatnije validan,, s obzirom da je prethodni pokušaji nisu bili. Dakle, ako su validni rešenja će verovatno biti "grupisana" u izvesnom smislu, i onda svaki novi kandidat treba da bude što je više moguće dalje od prethodnih, u tom smislu. Obrnuto, naravno, ako su rešenja ravnomerno raspoređena verovatno više nego što se očekivalo.

Alternative brute-force pretrage

Postoje mnoge druge metode pretrage, koje su dizajnirane da iskoriste razne vrste delimičnog znanja koje može imati o rešenju. Heuristika se takođe može koristiti da ranije prekida delova pretrage. Jedan primer ovoga je minimax princip za pretraživanje igre drveća, koji eliminiše mnoga podstabla u ranoj fazi pretrage. U pojedinim oblastima, kao što je jezik, analizirajući tehnike, kao što je grafikon raščlanjivanja može da iskoristi ograničenja u problemu da se smanji eksponencijalna složenost problema u polinomijalnu složenost problema.U mnogim slučajevima, kao što je Constraint Satisfaction Problems, jedan može dramatično smanjiti prostor za pretragu pomoću Constraint propagation, da se efikasno sprovodi u Constraint programming jezicima.Potraga prostor za probleme može se smanjiti zamenom punog problema sa pojednostavljenom verzijom. Na primer, u kompjuterskom šahu, umesto obračuna minimax drveta od svih mogućih poteza za ostatak igre, ograničeno drvo sa minimax mogućnostima je uračunato, uz drvo koje je orezano u određenom broju poteza, a ostatak drveta se aproksimirastatic evaluation function.

U kriptografiji

Главни чланак: Brute-force attack

U kriptografiji, brute-force napad uključuje sistrmatičnu proveru svih mogućih ključeva sve dok se ne nađe pravi. Ova strategija u teoriji može biti korišćena protiv svih šifrovanih podataka od strane napadač koji nije u stanju da iskoristi svaku slabost u sistemu kodiranja koji bi inače čine njegov zadatak olakšali.

Dužina ključa korišćena u šifrovanju određuje praktičnu izvodljivost obavljanja brute force napada, sa dužim ključem eksponencijalno je teže probiti od kratkoročnih ključeva. Brute force napadi mogu biti manje efikasni od zavaravanja kodiranih ppodataka, nešto što napadaču čini teže da prepozna kad je probio kod. Jedna od mera snage za šifrovanje sistema je koliko dugo bi teoretski bilo potrebno napadaču da montira uspešan brute force napad protiv njega.

Vidi još

• Napad grube sile
• Veliko O

Literatura

• Paar, Christof; Pelzl, Jan; Preneel, Bart (2010). Understanding Cryptography: A Textbook for Students and Practitioners. Springer. стр. 7. ISBN 978-3-642-04100-6.