Úvod do algoritmu hrubej sily
„Dáta sú novou ropou“ je to nová mantra, ktorá vládne svetovej ekonomike. Žijeme v digitálnom svete a každé podnikanie sa točí okolo údajov, ktoré sa premietajú do ziskov a pomáhajú odvetviam udržať si náskok pred konkurenciou. Vďaka rýchlej digitalizácii, exponenciálnemu nárastu obchodného modelu založeného na aplikáciách, sú počítačové zločiny stále hrozbou. Jednou z takýchto bežných aktivít, ktorú hackeri vykonávajú, je brutálna sila.
Brute Force je metóda pokusov a omylov, pri ktorej útočníci používajú programy na vyskúšanie rôznych kombinácií na prienik na akékoľvek webové stránky alebo systémy. Používajú automatizovaný softvér na opakované generovanie kombinácií User ID a hesiel, kým nakoniec nevytvoria správnu kombináciu.
Brute-Force Search
Hľadanie hrubou silou je najbežnejším vyhľadávacím algoritmom, pretože nevyžaduje žiadne znalosti domény. Vyžaduje sa iba opis stavu, zákonní operátori, počiatočný stav a opis cieľového stavu. Nezlepšuje výkon a úplne sa spolieha na výpočtový výkon pri vyskúšaní možných kombinácií.
Algoritmus hrubej sily vyhľadáva všetky polohy v texte medzi 0 a nm, či tam výskyt vzoru začína alebo nie. Po každom pokuse posunie vzor doprava presne o 1 pozíciu. Časová zložitosť tohto algoritmu je O (m * n). takže ak hľadáme n znakov v reťazci m znakov, bude to trvať n * m pokusov.
Pozrime sa na klasický príklad cestujúceho obchodníka, ktorý algoritmu ľahšie porozumie.
Predpokladajme, že predajca musí cestovať po 10 rôznych mestách v krajine a chce určiť najkratšiu možnú trasu zo všetkých možných kombinácií. Tu algoritmus hrubej sily jednoducho vypočíta vzdialenosť medzi všetkými mestami a vyberie najkratšie.
Iným príkladom je pokus o prelomenie 5-ciferného hesla, potom hrubá sila môže trvať až 105 pokusov o rozlúsknutie kódu.
Brute Force Sort
Pri technike triedenia hrubou silou sa zoznam údajov prehľadá viackrát, aby sa v ňom našiel najmenší prvok. Po každej iterácii nad zoznamom nahradí najmenší prvok na začiatok stohu a začne ďalšiu iteráciu z druhých najmenších údajov v zozname.
Vyššie uvedené vyhlásenie možno písať v pseudokódu nasledovne.
V tomto prípade je problémom veľkosť „n“ a základnou operáciou je test „if“, kde sa porovnávajú údajové položky v každej iterácii. Nebude žiadny rozdiel medzi najhorším a najlepším prípadom, pretože počet swapov nie je vždy n-1.
Brute Force String Matching
Ak sú všetky znaky vo vzorke jedinečné, je možné použiť Brute force string matching so zložitosťou Big O (n). kde n je dĺžka reťazca. Brute force String matching porovnáva vzorec s podreťazcom textového znaku po znaku, až kým nezíska nezhodujúci sa znak. Len čo sa zistí nesúlad, zostávajúci znak podreťazca sa vynechá a algoritmus sa presunie na ďalšie podreťazec.
Nižšie uvedené pseudokódy vysvetľujú logiku porovnávania reťazcov. Tu sa algoritmus pokúša vyhľadať vzorec P (0… m-1) v texte T (0… .n-1).
tu najhorší prípad by nastal, keď by sa prechod na iné podreťazce neuskutočnil, kým sa nevykoná porovnanie M.
Najbližší pár
Údaj o probléme: Nájsť dva najbližšie body v množine n bodov v dvojrozmernej karteziánskej rovine. Existuje množstvo scenárov, v ktorých tento problém nastáva. Príkladom skutočného života by bol systém riadenia letovej prevádzky, kde musíte monitorovať lietadlá, ktoré lietajú blízko seba, a musíte zistiť najbezpečnejšiu minimálnu vzdialenosť, ktorú by tieto lietadlá mali udržať.
Zdroj: Wikipedia
Algoritmus hrubej sily vypočíta vzdialenosť medzi každou odlišnou množinou bodov a vráti indexy bodu, pre ktorý je vzdialenosť najmenšia.
Brute force rieši tento problém časovou zložitosťou (O (n2)), kde n je počet bodov.
Pod pseudokódom sa používa algoritmus hrubej sily na nájdenie najbližšieho bodu.
Konvexný trup
Vyhlásenie o probléme : Konvexný trup je najmenší polygón, ktorý obsahuje všetky body. Konvexný trup množiny s bodu je najmenší konvexný mnohouholník obsahujúci s.
Konvexný trup pre túto množinu bodov je konvexný mnohouholník so vrcholmi na P1, P5, P6, P7, P3.
Čiarový segment P1 a Pn množiny n bodov je súčasťou konvexného trupu iba vtedy, ak všetky ostatné body množiny ležia vo vnútri hranice mnohouholníka tvoreného čiarou.
Poďme to spojiť s gumičkou,
Bod (x1, y1), (x2, y2) tvorí priamku ax + pomocou = c
Keď a = y2-y1, b = x2-x1 ac = x1 * y2 - x2 * y1 a delí rovinu axou + by-c 0
Takže musíme skontrolovať ax + by-c pre ďalšie body.
Brute force vyriešiť tento problém s časovou zložitosť O (n 3 )
Vyčerpávajúce vyhľadávanie
Pre diskrétne problémy, v ktorých nie je známe efektívne riešenie, je potrebné testovať každé možné riešenie postupne.
Vyčerpávajúce hľadanie je činnosť zameraná na systematické nájdenie všetkých možných riešení problému.
Pokúsme sa vyriešiť problém obchodného cestujúceho (TSP) pomocou algoritmu vyčerpávajúceho vyhľadávania Brute.
Problémové vyhlásenie: Existujú n mestá, ktoré predajca potrebuje cestovať, chce nájsť najkratšiu trasu, ktorá pokrýva všetky mestá.
Uvažujeme o riešení problému Hamilton Circuit. Ak existuje obvod, potom ktorýkoľvek bod môže začať vrcholy a koncové vrcholy. Po výbere počiatočných vrcholov potom potrebujeme iba poradie pre zostávajúce vrcholy, tj n-1
Potom bude (n-1)! Možné kombinácie a celkové náklady na výpočet cesty by boli O (n). takže celková časová zložitosť by bola O (n!).
záver
Teraz, keď sme dosiahli koniec tohto tutoriálu, dúfam, že ste teraz dostali reálnu predstavu o tom, čo je Brute Force. Videli sme tiež rôzne algoritmy Brute Force, ktoré môžete použiť vo svojej aplikácii.
Odporúčané články
Toto bol sprievodca po Brute Force Algorithm. Tu sme diskutovali o základných pojmoch algoritmu Brute Force. Viac informácií nájdete aj v ďalších navrhovaných článkoch -
- Čo je to algoritmus?
- Otázky týkajúce sa rozhovoru s algoritmom
- Úvod do algoritmu
- Algoritmus v programovaní