Исцрпна претрага

У рачунарству, бруте-форце претрага(груба сила) или исцрпљујућа претрага, такође позната и као генериши и тестирај, је општа техника решавања проблема која се састоји од систематичног набрајања свих могућих кандидата за решавање и провере да ли сваки кандидат задовољава проблем.

Да би брут-форце алгоритам пронасао делиоце природног броја н, он набраја све целе бројеве од 1 до корена из н, и проверава да ли сваки од њих дели н без остатка. Брут-форце приступ за проблем осам дама испитује све могуће аранжмане од 8 делова на 64-квадратној шаховској табли, и, за сваки аранжман, проверава да ли сваки (дама) део може да нападне било који други.

Док је брут-форце претрага једноставна за примену, и увек ће пронаћи решење ако постоји, његова цена сразмерна је броју кандидата решења – што у многим практичним проблемима претендује веома брзим растом како се величина проблема повећава. Дакле, бруте-форце претрага се обично користи када је величина проблема ограничена, или када постоји специфичан проблем хеуристике који може бити искоришћен да се смањи скуп кандидата решења до величине погодне за руковање. Метода се такође користи када је једноставност имплементације важнија од брзине.

То је случај, на пример, у критичним апликацијама где свака грешка у алгортиму има веома озбиљне последице; или када користите рачунар да докажете математичку теорему. Бруте-форце претрага је такодје корисна и као "основни" метход код бенчмаркинга других алгоритама или метахеуристике. Заиста, бруте-форце претраживање се може посматрати као најједноставнији метахеуристик. Бруте форце претраживање не треба мешати са бектрекингом, где велики скупови решења могу бити одбачени без експлицитног набрајања. Бруте-форце метода за проналажење ставки у табели - наиме, проверава све ставке ових других, секвенцијално – се зове линеарна претрага.

Имплементација бруте-форце претраге

Основни алгоритам

У жељи да се бруте-форце претрага примени на одређену класу проблема, морају се спровести четири фунцкије, прво-фирст,следеће-неxт, валидно-валид, и излаз-оутпут. Ова процедура треба да узме као параметар П у конкретном случају проблема које треба решити, а требало би да уради следеће:

1. фирст (П): генерише решење кандидата за прво П.
2. неxт (П, ц): генерисати следећи кандидат за П након тренутне ц.
3. валид (П, ц): проверите да ли кандидат ц је решење за П.
4. оутпут (П, ц): користити решење ц од П као погодно за примену.

Следећи поступак мора рећи када више не постоје кандидати за пример П, након садашњег ц. Погодан начин за то је да се врати на "нулту кандидата", неки конвенционални податак вредност и Λ да се разликује од стварног кандидата. Исто тако прво треба да врати Λ ако уопште нема кандидата за пример П. Бруте-форце метода се затим описује алгоритмом

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

На пример, када је у потрази за делиоцима број н, инстанца податка П је број н. Позив фирст(н) треба да врати 1 ако н $\geq$ 1, или Λ иначе; позив неxт(н,ц) треба да врати ц + 1 ако ц $<$ н, и Λ иначе; и валид(н,ц) треба да вратитачно ако и само ако ц је делилац за н. (У ствари, ако одаберете Λ да буде н + 1, тест н $\geq$ 1 и ц $<$ н је непотребан.)Бруте-форце алгоритам за претрагу позваће оутпут за сваког кандидата који је решење у датој инстанци П. Алгоритам се лако модификује да се заустави после проналажењу првог решења, или одређеног броја решења, или након тестирања одређеног броја кандидата, или након што је провео дату количину процесорског времена.

Комбинаторне експлозије

Главни недостатак бруте-форце методе је да је, за многе реалне проблеме, број природних кандидата претерано велики. На пример, ако тражимо делилац броја као што је горе описано, број тестираних кандидата ће бити управо дат број н. Дакле, ако н има шеснаест децималних цифара, каже, претрага ће захтевати извршење најмање 10¹⁵ инструкција, што ће заузети неколико дана на типичном рачунару. Ако је н случајни 64-битни природан број, који има 19 цифара у просеку, претрага ће трајати око 10година. Овај стрми пораст у броју кандидата, како и величина података расте, јавља се у свим врстама проблема. На пример, ако тражимо одређено преуређење од 10 слова, онда имамо 10! = 3.628.800 кандидата за разматрање, што типичан ПЦ може да генерише и тестира за мање од једне секунде. Међутим, додајући још једно слово — што је само 10% повећања величине података — повећаће број кандидата на 11 — за 1000%. За 20 слова, број кандидата је 20!, што је око 2.4×10¹⁸ или 2.4 трилиона; и претрага ће трајати око 10 година. Овај непожељан феномен се обично зове комбинаторна експлозија, или проклетство димензионалности..

Убрзавање бруте-форце претраге

Један од начина да се убрза бруте-форце алгоритам је да се смањи простор за претрагу, односно, скуп кандидата решења, користећи хеуристику специфичне класе проблема. На пример, у проблем осам дама изазов је да се постави осам краљица на стандардној шаховској табли тако да ниједна дама не напада било коју другу. Пошто свака дама може да се постави у било који од 64 квадрата, у принципу постоје 64⁸ = 281.474.976,710,656 могућности које треба размотрити. Међутим, пошто су све даме подједнаке, а никоје две могу бити постављене на истом квадрату, кандидати су комбинације сета од 8 квадрата из скупа свих 64 квадрата; што значи 64 бира 8 = 64!/56!/8! = 4.426.165,368 кандидата решења — око 1/60,000 претходне процене. Даље, решење са две даме у истој реду или колони не може бити решење. Због тога, можемо даље да ограничимо скуп тих кандидата.

Као што овај пример показује, мало анализе често ће довести до драстичног смањења броја кандидата решења, а може претворити и неподношљив у тривијалан проблем.

У неким случајевима, анализа може смањити кандидате на скуп свих важећих решења; то јест, она може дати алгоритам који директно набраја сва жељена решења (или нађе једно решење, по потреби), без губљења времена са тестовима и неважећим кандидатима. На пример, за проблем "наћи све целе бројеве између 1 и 1.000.000 да су равномерно дељиви са 417" наивни бруте-форце ће генерисати све целе бројеве у опсегу, тестирајући сваки од њих за дељивост. Међутим, тај проблем се може решити много ефикасније почињуући са 417 и више пута додајући 417 док број прелази 1.000.000 - што траје само 2398 (= 1.000.000 ÷ 417) корака, и нема тестова.

Мењање редоследа претраге простора

У апликацијама које захтевају само једно решење, а не сва решења, очекивана вредност извршавања бруте форце претраге често ће зависит од реда у којем су кандидати тестирани. Као генерално правило, треба прво тестирати најперспективније кандидате. На пример, у потрази за погодним делиоцем за случајни број н, боље је набројати делиоце кандидата у растућем редоследу, од 2 до н – 1, него обрнуто — јер је вероватноћа да је н дељив са ц 1/ц. Штавише, на вероватноћу кандидата да је валидан често утичу претходна неуспела покушавања. На пример, размотрити проблем проналажења 1 бита у датом 1000-битном низу П. У овом случају, кандидати решења су индекси 1 то 1000, и кандидат ц је валидан ако П[ц] = 1. Сада, претпоставимо да је први бит П једнако вероватно да ће бити 0 или 1, али после тога сваки бит је једнак претходном са 90% вероватноће. Ако су кандидати набројани у растућем поретку, 1 до 1000, број т кандидата испитатаних пре него успеха ће бити око 6, у просеку. На другу страну, ако су кандидати нумерисани у реду 1.11.21,31...991,2,12,22,32 итд., очекивана вредност т биче само мало мања од 2. Уопштено, простор претраге треба се набројати на такав начин да је следећи кандидат највероватније валидан,, с обзиром да је претходни покушаји нису били. Дакле, ако су валидни решења ће вероватно бити "груписана" у извесном смислу, и онда сваки нови кандидат треба да буде што је више могуће даље од претходних, у том смислу. Обрнуто, наравно, ако су решења равномерно распоређена вероватно више него што се очекивало.

Алтернативе бруте-форце претраге

Постоје многе друге методе претраге, које су дизајниране да искористе разне врсте делимичног знања које може имати о решењу. Хеуристика се такође може користити да раније прекида делова претраге. Један пример овога је минимаx принцип за претраживање игре дрвећа, који елиминише многа подстабла у раној фази претраге. У појединим областима, као што је језик, анализирајући технике, као што је графикон рашчлањивања може да искористи ограничења у проблему да се смањи експоненцијална сложеност проблема у полиномијалну сложеност проблема.У многим случајевима, као што је Цонстраинт Сатисфацтион Проблемс, један може драматично смањити простор за претрагу помоћу Цонстраинт пропагатион, да се ефикасно спроводи у Цонстраинт программинг језицима.Потрага простор за проблеме може се смањити заменом пуног проблема са поједностављеном верзијом. На пример, у компјутерском шаху, уместо обрачуна минимаx дрвета од свих могућих потеза за остатак игре, ограничено дрво са минимаx могућностима је урачунато, уз дрво које је орезано у одређеном броју потеза, а остатак дрвета се апроксимирастатиц евалуатион фунцтион.

У криптографији

Главни чланак: Бруте-форце аттацк

У криптографији, бруте-форце напад укључује систрматичну проверу свих могућих кључева све док се не нађе прави. Ова стратегија у теорији може бити коришћена против свих шифрованих података од стране нападач који није у стању да искористи сваку слабост у систему кодирања који би иначе чине његов задатак олакшали.

Дужина кључа коришћена у шифровању одређује практичну изводљивост обављања бруте форце напада, са дужим кључем експоненцијално је теже пробити од краткорочних кључева. Бруте форце напади могу бити мање ефикасни од заваравања кодираних пподатака, нешто што нападачу чини теже да препозна кад је пробио код. Једна од мера снаге за шифровање система је колико дуго би теоретски било потребно нападачу да монтира успешан бруте форце напад против њега.

Види још

• Напад грубе силе
• Велико О

Литература

• Паар, Цхристоф; Пелзл, Јан; Пренеел, Барт (2010). Ундерстандинг Црyптограпхy: А Теxтбоок фор Студентс анд Працтитионерс. Спрингер. стр. 7. ИСБН 978-3-642-04100-6.