Úvod do algoritmu Brute Force
„Data jsou nová ropa“ je to nová mantra, která vládne globální ekonomice. Žijeme v digitálním světě a každé podnikání se točí kolem dat, která se promítají do zisků a pomáhají odvětvím udržet si náskok před konkurencí. S rychlou digitalizací, exponenciálním nárůstem obchodního modelu založeného na aplikacích, jsou počítačové zločiny neustálou hrozbou. Jednou takovou běžnou činností, kterou hackeři vykonávají, je brutální síla.
Brute Force je přístup k pokusům a omylům, kdy útočníci používají programy k vyzkoušení různých kombinací, aby se dostali do libovolných webových stránek nebo systémů. Používají automatizovaný software k opakovanému generování kombinace ID uživatele a hesla, dokud nakonec nevytvoří správnou kombinaci.
Brute-Force Search
Brute force search je nejběžnější vyhledávací algoritmus, protože nevyžaduje žádné znalosti domény, vše, co je vyžadováno, je popis stavu, legální operátoři, počáteční stav a popis cílového stavu. Nezlepšuje výkon a při testování možných kombinací se zcela spoléhá na výpočetní výkon.
Algoritmus hrubé síly prohledává všechny pozice v textu mezi 0 a nm, ať už se zde výskyt vzoru začíná nebo ne. Po každém pokusu posune vzor doprava přesně o 1 pozici. Časová složitost tohoto algoritmu je O (m * n). takže pokud budeme hledat n znaků v řetězci m znaků, bude to trvat n * m pokusů.
Podívejme se na klasický příklad cestujícího prodavače, který algoritmu snadno porozumí.
Předpokládejme, že prodejce musí cestovat do 10 různých měst v zemi a chce určit nejkratší možné trasy ze všech možných kombinací. Algoritmus hrubé síly zde jednoduše spočítá vzdálenost mezi všemi městy a vybere nejkratší.
Dalším příkladem je pokus o zlomení 5místného hesla, pak hrubá síla může trvat až 105 pokusů o rozbití kódu.
Brute Force Sort
Při technice třídění hrubou silou je seznam dat prohledáván vícekrát, aby se našel nejmenší prvek v seznamu. Po každé iteraci nad seznamem nahradí nejmenší prvek na začátek zásobníku a zahájí další iteraci z druhých nejmenších dat v seznamu.
Výše uvedené prohlášení lze psát v pseudokódu následovně.
Zde je problém velikosti 'n' a základní operací je 'if' test, kde jsou datové položky porovnávány v každé iteraci. Nebude rozdíl mezi nejhorším a nejlepším případem, protože počet swapů je vždy n-1.
Brute Force String Matching
Jsou-li všechny znaky ve vzoru jedinečné, lze použít Brute force string matching s komplexností Big O (n). kde n je délka řetězce. Brute force String matching porovnává vzorek s podřetězcem textového znaku po znaku, dokud nezíská neshodný znak. Jakmile je nalezena neshoda, zbývající znak podřetězce bude zrušen a algoritmus se přesune na další podřetězec.
Níže uvedené pseudokódy vysvětlují logiku odpovídající řetězci. Zde se algoritmus snaží hledat vzorec P (0… m-1) v textu T (0… .n-1).
v tomto případě by nejhorším případem bylo, kdyby se posun k jinému podřetězci neuskutečnil, dokud nebude M Th srovnání.
Nejbližší pár
Údaj o problému: Najít dva nejbližší body v sadě n bodů v dvojrozměrné kartézské rovině. Existuje n scénářů, ve kterých tento problém nastává. Příkladem skutečného života by byl systém řízení letového provozu, kde musíte monitorovat letadla létající blízko sebe a musíte zjistit nejbezpečnější minimální vzdálenost, kterou by tato letadla měla udržovat.
Zdroj: Wikipedia
Algoritmus hrubé síly vypočítává vzdálenost mezi každou odlišnou sadou bodů a vrací indexy bodu, pro který je vzdálenost nejmenší.
Brutální síla řeší tento problém časovou složitostí (O (n2)), kde n je počet bodů.
Pod pseudokódem používá algoritmus hrubé síly k nalezení nejbližšího bodu.
Konvexní obal
Prohlášení o problému : Konvexní trup je nejmenší polygon, který obsahuje všechny body. Konvexní trup množiny bodu je nejmenší konvexní mnohoúhelník obsahující s.
Konvexní trup pro tuto sadu bodů je konvexní mnohoúhelník s vrcholy na P1, P5, P6, P7, P3
Čárový segment P1 a Pn množiny n bodů je součástí konvexního trupu pouze tehdy, pokud všechny ostatní body množiny leží uvnitř polygonové hranice tvořené liniovým segmentem.
Pojďme to spojit s gumičkou,
Bod (x1, y1), (x2, y2) vytvoří přímku ax + podle = c
Když a = y2-y1, b = x2-x1 a c = x1 * y2 - x2 * y1 a rozdělí rovinu osou + by-c 0
Takže musíme zkontrolovat ax + by-c pro další body.
Brute force řeší tento problém časovou složitostí O (n 3 )
Vyčerpávající vyhledávání
U diskrétních problémů, u kterých není známo efektivní řešení, se stává nutností testovat každé možné řešení postupně.
Vyčerpávající vyhledávání je činnost zaměřená na systematické nalezení všech možných řešení problému.
Zkusme vyřešit problém Traveling salesman Problem (TSP) pomocí Brute taxativního vyhledávacího algoritmu.
Problémové prohlášení: Existují n města, která musí prodavač cestovat, chce najít nejkratší cestu, která pokrývá všechna města.
Uvažujeme o vyřešení tohoto problému u Hamilton Circuit. Pokud existuje obvod, pak jakýkoli bod může začít vrcholy a koncové vrcholy. Jakmile jsou vybrány počáteční vrcholy, pak potřebujeme pouze pořadí pro zbývající vrcholy, tj. N-1
Pak bude (n-1)! Možné kombinace a celkové náklady na výpočet cesty by byly O (n). takže celková časová složitost by byla O (n!).
Závěr
Nyní, když jsme dosáhli konce tohoto výukového programu, doufám, že jste nyní dostali spravedlivou představu o tom, co je Brute Force. Viděli jsme také různé algoritmy Brute Force, které můžete použít ve vaší aplikaci.
Doporučené články
Toto byl průvodce Brute Force Algorithm. Zde jsme diskutovali základní pojmy algoritmu Brute Force. Další informace naleznete také v dalších navrhovaných článcích -
- Co je to algoritmus?
- Rozhovor s otázkami algoritmu
- Úvod do algoritmu
- Algoritmus v programování