Introducere în algoritmul Forțelor Brute
„Datele sunt uleiul nou”, aceasta este noua mantră care conduce economia globală. Trăim în lumea digitală și fiecare afacere se învârte în jurul datelor care se traduce în profituri și ajută industriile să rămână în fața concurenței lor. Odată cu digitalizarea rapidă, o creștere exponențială a modelului de business bazat pe aplicație, infracțiunile informatice reprezintă o amenințare constantă. Una dintre aceste activități comune pe care hackerii o desfășoară este forța Brute.
Brute Force este o abordare de încercare și eroare, în care atacatorii folosesc programe pentru a încerca diverse combinații pentru a intra în orice site-uri sau sisteme. Folosesc software automat pentru a genera repetitiv combinațiile de ID-uri și parole utilizator, până când va genera în cele din urmă combinația potrivită.
Căutare Brute-Force
Căutarea cu forțe brute este cel mai frecvent algoritm de căutare, deoarece nu necesită nicio cunoaștere a domeniului, tot ceea ce este necesar este o descriere a stării, operatori legali, starea inițială și descrierea unei stări țintă. Nu îmbunătățește performanțele și se bazează complet pe puterea de calcul pentru a încerca combinații posibile.
Algoritmul forței brute caută toate pozițiile din text între 0 și nm dacă apariția modelului începe acolo sau nu. După fiecare încercare, schimbă modelul la dreapta cu exact 1 poziție. Complexitatea timpului acestui algoritm este O (m * n). Deci, dacă căutăm n caractere dintr-un șir de m caractere, atunci va fi nevoie de n * m încearcă.
Să vedem un exemplu clasic de vânzător în călătorie pentru a înțelege algoritmul într-o manieră ușoară.
Să presupunem că un vânzător trebuie să călătorească 10 orașe diferite dintr-o țară și vrea să determine cele mai scurte rute posibile din toate combinațiile posibile. Aici algoritmul de forță brută calculează pur și simplu distanța dintre toate orașele și îl selectează pe cel mai scurt.
Un alt exemplu este să faceți o încercare de a sparge parola de 5 cifre, atunci forța brută poate dura până la 10 5 încercări de a fisura codul.
Sortare forță brută
În tehnica de sortare a forței brute, lista de date este scanată de mai multe ori pentru a găsi cel mai mic element din listă. După fiecare iterație de pe listă, înlocuiește cel mai mic element în partea de sus a stivei și începe următoarea iterație din a doua cea mai mică date din listă.
Afirmația de mai sus poate fi scrisă în pseudo-cod după cum urmează.
Aici problema are dimensiunea „n”, iar operația de bază este testul „dacă” în care sunt comparate elementele de date pentru fiecare iterație. Nu va fi nici o diferență între cel mai rău caz și cel mai bun caz, deoarece numărul de swap nu este întotdeauna n-1.
Potrivirea brută cu șiruri de forțe
Dacă toate caracterele din model sunt unice, atunci potrivirea brutei de forțe brute pot fi aplicate cu complexitatea Big O (n). unde n este lungimea șirului. Forța brută Potrivirea șirului compară modelul cu subîncărcarea unui text de text după caracter până când devine un caracter nepotrivit. De îndată ce se constată o nepotrivire, caracterul rămas al subcadrului este abandonat și algoritmul se mută la următoarea substrat.
Pseudo-codurile de mai jos explică logica de potrivire a șirurilor. Aici algoritmul încearcă să caute un model de P (0… m-1) în textul T (0… .n-1).
aici cel mai rău caz ar fi atunci când trecerea la o altă substrat nu se face până la comparația M Th .
Cea mai apropiată pereche
Enunț de problemă: Pentru a afla cele două puncte apropiate într-un set de n puncte în planul cartezian bidimensional. Există un număr de scenarii în care apare această problemă. Un exemplu de viață real ar fi într-un sistem de control al traficului aerian, unde trebuie să monitorizați avioanele care zboară aproape unul de celălalt și trebuie să aflați distanța minimă cea mai sigură pe care ar trebui să o mențină aceste avioane.
Sursa: Wikipedia
Algoritmul forței brute calculează distanța dintre fiecare set distinct de puncte și returnează indexurile punctului pentru care distanța este cea mai mică.
Forța brută rezolvă această problemă cu complexitatea în timp a lui (O (n2)) unde n este numărul de puncte.
Sub pseudo-cod se folosește algoritmul forței brute pentru a găsi cel mai apropiat punct.
Coca convexă
Problema : O coca convexă este cel mai mic poligon care conține toate punctele. Coca convexă a unui set de puncte este cel mai mic poligon convex care conține s.
Coca convexă pentru acest set de puncte este poligonul convex cu vârfuri la P1, P5, P6, P7, P3
Un segment de linie P1 și Pn al unui set de n puncte este o parte a cavei convexe dacă și numai dacă toate celelalte puncte ale mulțimii se află în interiorul graniței poligonului format din segmentul de linie.
Să o raportăm cu banda de cauciuc,
Punctul (x1, y1), (x2, y2) face linia ax + de = c
Când a = y2-y1, b = x2-x1 și c = x1 * y2 - x2 * y1 și împarte planul cu ax + by-c 0
Deci trebuie să verificăm ax + by-c pentru celelalte puncte.
Forța brută rezolvă această problemă cu complexitatea în timp a O (n 3 )
Căutare exhaustivă
Pentru problemele discrete în care nu există o soluție eficientă cunoscută, devine necesară testarea fiecărei soluții posibile într-o manieră secvențială.
Căutarea exhaustivă este o activitate pentru a afla toate soluțiile posibile la o problemă într-o manieră sistematică.
Să încercăm să rezolvăm Problema de vânzător de călători (TSP) folosind un algoritm de căutare exhaustivă Brute.
Declarație de problemă: Există n oras pe care vânzătorul trebuie să călătorească, el vrea să afle cea mai scurtă rută care acoperă toate orașele.
Avem în vedere Hamilton Circuit pentru a rezolva această problemă. Dacă există un circuit, atunci orice punct poate porni vârfuri și vârfuri. Odată ce vertexurile de început sunt selectate, atunci avem nevoie doar de ordinea pentru resturile de adâncime, adică n-1
Atunci ar mai fi (n-1)! Combinațiile posibile și costul total pentru calcularea căii ar fi O (n). astfel complexitatea totală a timpului ar fi O (n!).
Concluzie
Acum că am ajuns la sfârșitul acestui tutorial, sper că voi aveți acum o idee corectă despre ce este Forța Brută. Am văzut, de asemenea, diversul algoritm Brute force pe care îl puteți aplica în aplicația dvs.
Articole recomandate
Acesta a fost un ghid pentru algoritmul Forței Brute. Aici am discutat conceptele de bază ale algoritmului Brute Force. Puteți parcurge și alte articole sugerate pentru a afla mai multe -
- Ce este un algoritm?
- Întrebări la interviu Algoritm
- Introducere în Algoritm
- Algoritmul în programare