Johdatus raa'an voiman algoritmiin

"Data on uusi öljy", tämä on uusi mantra, joka hallitsee maailmantaloutta. Elämme digitaalimaailmassa, ja jokainen yritys pyörii datan ympärillä, joka tuottaa voittoa ja auttaa toimialoja pysymään kilpailunsa edessä. Nopean digitalisoinnin, sovelluspohjaisen liiketoimintamallin eksponentiaalisen kasvun myötä verkkorikot ovat jatkuva uhka. Yksi tällainen yleinen toiminta, jonka hakkerit suorittavat, on raa'at voimat.

Brute Force on kokeilu- ja virhemenetelmä, jossa hyökkääjät käyttävät ohjelmia kokeillakseen erilaisia ​​yhdistelmiä murtautuaksesi mille tahansa verkkosivustolle tai järjestelmään. He käyttävät automaattista ohjelmistoa generoimaan toistuvasti käyttäjätunnuksen ja salasanan yhdistelmät, kunnes lopulta se tuottaa oikean yhdistelmän.

Brute-Force-haku

Brute Force -haku on yleisin hakualgoritmi, koska se ei vaadi mitään verkkotunnuksen tuntemusta, kaikki mitä tarvitaan, on tilakuvaus, lailliset toimijat, alkutila ja tavoitetilan kuvaus. Se ei paranna suorituskykyä ja luottaa täysin laskentatehoon kokeillaan mahdollisia yhdistelmiä.

Raakavoima-algoritmi etsii kaikki tekstin paikat välillä 0 - nm, alkaako kuvion esiintyminen siellä vai ei. Jokaisen yrityksen jälkeen se siirtää kuvion oikealle tarkalleen yhden asennon. Tämän algoritmin aikakompleksi on O (m * n). joten jos etsimme n merkkiä m merkkijonosta, niin kestää n * m yritystä.

Katsotaanpa klassinen esimerkki matkustavasta myyjästä ymmärtämään algoritmi helposti.

Oletetaan, että myyjän on matkustettava 10 eri kaupungissa eri maissa ja hän haluaa määrittää mahdollisimman lyhyet reitit kaikista mahdollisista yhdistelmistä. Tässä raa'an voiman algoritmi yksinkertaisesti laskee etäisyyden kaikkien kaupunkien välillä ja valitsee lyhyimmän.

Toinen esimerkki on yrittää rikkoa 5-numeroinen salasana, jolloin raa'alla voimalla voi kestää jopa 10 5 yritystä murtaa koodi.

Brute Force lajittelu

Raakavoimalajittelumenetelmässä datalista skannataan useita kertoja luettelon pienimmän elementin löytämiseksi. Jokaisen luettelon iteraation jälkeen se korvaa pienimmän elementin pinon yläosaan ja aloittaa seuraavan iteraation luettelon toisesta pienimmästä tiedosta.

Yllä oleva lausunto voidaan kirjoittaa näennäiskoodina seuraavasti.

Tässä ongelman koko on 'n' ja perusoperaatio on 'if' -testi, jossa tietoalkioita verrataan jokaisessa iteraatiossa. Tahdolla ei ole eroa pahimman ja parhaan mahdollisen tapauksen välillä, koska vaihtosuunnan arvo on aina n-1.

Brute Force kielijono

Jos kaikki kuvion merkit ovat ainutlaatuisia, niin Brute Force -merkkijonoa voidaan käyttää Big O: n (n) monimutkaisuuden kanssa. missä n on merkkijonon pituus. Brutaatiovoima Stringsovitus vertaa kuviota tekstimerkin osajonoon merkin perusteella, kunnes se saa väärän merkin. Heti kun yhteensopimattomuus löytyy, alijonojen jäljellä oleva merkki pudotetaan ja algoritmi siirtyy seuraavaan osajonoon.

Alla olevat pseudokoodit selittävät merkkijonoa vastaavan logiikan. Tässä algoritmi yrittää etsiä P (0… m-1) -mallia tekstistä T (0… .n-1).

tässä pahin tapaus olisi, kun siirtyminen toiseen osajonoon tapahtuu vasta M Th -vertailussa.

Lähin pari

Tilanne: Selvitetään kaksi lähintä pistettä n-pistejoukosta kaksiulotteisessa suorakulmaisessa tasossa. Tämän ongelman esiintymisessä on n useita skenaarioita. Todellinen esimerkki elämästä olisi lennonjohtojärjestelmä, jossa sinun on tarkkailtava lähellä toisiaan lentäviä lentokoneita ja selvitettävä turvallisin vähimmäisetäisyys, jonka näiden koneiden tulisi pitää.

Lähde: Wikipedia

Brute force algoritmi laskee etäisyyden jokaisen erillisen pistejoukon välillä ja palauttaa sen pisteen indeksit, jonka etäisyys on pienin.

Brutaalivoima ratkaisee tämän ongelman ajan monimutkaisuudella (O (n2)), missä n on pisteiden lukumäärä.

Pseudokoodin alapuolella käytetään raa'an voiman algoritmia lähimmän pisteen löytämiseen.

Kupera runko

Ongelma : Kupera runko on pienin monikulmio, joka sisältää kaikki kohdat. Pistejoukon kupera runko on pienin kupera monikulmio, joka sisältää s.

Tämän pistejoukon kupera runko on kupera monikulmio, jonka kärkipisteet ovat pisteissä P1, P5, P6, P7, P3

N-pistejoukon linjasegmentit P1 ja Pn ovat osa kuperia runkoa vain silloin, kun ryhmän kaikki muut kohdat sijaitsevat linjasegmentin muodostaman monikulmion rajan sisällä.

Liitetään se kuminauhaan,

Piste (x1, y1), (x2, y2) tekevät linjan ax + by = c

Kun a = y2-y1, b = x2-x1 ja c = x1 * y2 - x2 * y1 ja jakaa tason axilla + by-c 0

Joten meidän on tarkistettava ax + by-c muiden pisteiden suhteen.

Brute force ratkaisee tämän ongelman ajan monimutkaisella O (n 3 )

Kattava haku

Erillisissä ongelmissa, joissa ei ole tunnettua tehokasta ratkaisua, tulee välttämättömäksi testata jokainen mahdollinen ratkaisu peräkkäin.

Kattava haku on toimintaa, jolla selvitetään järjestelmällisesti kaikki mahdolliset ratkaisut ongelmaan.

Yritetään ratkaista matkustava myyntimies (TSP) Bruten tyhjentävän hakualgoritmin avulla.

Ongelma: Ei n kaupunkia, jotka myyjän täytyy matkustaa, hän haluaa selvittää lyhin reitti, joka kattaa kaikki kaupungit.

Harkitsemme Hamilton-piiriä tämän ongelman ratkaisemiseksi. Jos piiri on olemassa, mikä tahansa piste voi aloittaa huiput ja päätepisteet. Kun aloituspisteet on valittu, tarvitsemme tilauksen vain jäljelle jääville kärkipisteille eli n-1

Sitten olisi (n-1)! Mahdolliset yhdistelmät ja polun laskemisen kokonaiskustannukset olisivat O (n). täten kokonaiskeskeisyys olisi O (n!).

johtopäätös

Nyt kun olemme päässeet tämän oppaan loppuun, toivottavasti teillä on nyt hyvä käsitys siitä, mikä Brute Force on. Olemme myös nähneet erilaisia ​​Brute Force -algoritmeja, joita voit käyttää sovelluksessasi.

Suositellut artikkelit

Tämä on opas Brute Force -algoritmiin. Tässä keskustelimme raa'an voiman algoritmin peruskäsitteistä. Voit myös käydä läpi muiden ehdotettujen artikkeleidemme saadaksesi lisätietoja -

  1. Mikä on algoritmi?
  2. Algoritmihaastattelukysymykset
  3. Johdanto algoritmiin
  4. Algoritmi ohjelmoinnissa

Luokka:

Ohjelmistokehitys