Uvod v algoritem Brute Force
"Podatki so nova nafta", to je nova mantra, ki vlada globalnemu gospodarstvu. Živimo v digitalnem svetu in vsako podjetje se vrti okoli podatkov, ki pomenijo dobiček in pomagajo industrijam, da ostajajo pred konkurenco. S hitro digitalizacijo, eksponentnim povečanjem poslovnega modela, ki temelji na aplikacijah, kibernetska kazniva dejanja predstavljajo stalno grožnjo. Ena izmed pogostih dejavnosti, ki jo izvajajo hekerji, je sila Brute.
Brute Force je pristop poskusov in napak, kjer napadalci uporabljajo programe za preizkušanje različnih kombinacij za preboj na katero koli spletno mesto ali sistem. Za avtomatizirano programsko opremo ponavljajoče ustvarjajo kombinacije ID-ja uporabnika in gesel, dokler na koncu ne ustvarijo prave kombinacije.
Brute-Force iskanje
Brute force iskanje je najpogostejši iskalni algoritem, saj ne zahteva nobenega domenskega znanja, potreben je le opis države, pravni operaterji, začetno stanje in opis ciljnega stanja. Ne izboljša zmogljivosti in se povsem preizkusi v računalniški moči, da preizkusi možne kombinacije.
Algoritem brutalne sile išče vse položaje v besedilu med 0 in nm, ne glede na to, ali se pojav vzorca začne tam ali ne. Po vsakem poskusu premakne vzorec v desno za natančno 1 položaj. Časovna zapletenost tega algoritma je O (m * n). Torej če iščemo n znakov v nizu m znakov, bo potrebnih n * m poskusov.
Oglejmo si klasičen primer potujočega prodajalca, s katerim lahko algoritem razumemo na enostaven način.
Recimo, da mora prodajalec potovati v 10 različnih mestih v državi in želi iz vseh možnih kombinacij določiti najkrajše poti. Tu algoritem brute force preprosto izračuna razdaljo med vsemi mesti in izbere najkrajšo.
Drug primer je poskus, da bi zlomili petmestno geslo, potem lahko velika sila zahteva do 10 pet poskusov, da koda pokvari.
Brute Force Sort
V tehniki razvrščanja brutalne sile se seznam podatkov večkrat skenira, da bi našli najmanjši element na seznamu. Po vsaki ponovitvi seznama nadomešča najmanjši element na vrhu zložbe in začne naslednjo iteracijo iz drugega najmanjšega podatka na seznamu.
Zgornjo izjavo lahko v psevdo kodo zapišemo na naslednji način.
Tu je težava velikost 'n', osnovna operacija pa je 'if' preizkus, kjer se podatki podatkov primerjajo v vsaki ponovitvi. Nič ne bo razlike med najslabšim in najboljšim primerom, saj je no swap vedno n-1.
Ujemanje vrvi silovite sile
Če so vsi znaki v vzorcu edinstveni, potem lahko uporabite kompleksnost nizov Brute force s kompleksnostjo Big O (n). kjer je n dolžina niza. Brute force Ujemanje niza primerja vzorec s podstrezom besedilnega znaka po znaku, dokler ne dobi neusklajenega znaka. Takoj, ko se ugotovi neskladje, se preostali znak podvrsti spusti in algoritem preide na naslednjo podvrsto.
Spodnje psevdo kode pojasnjujejo logiko ujemanja nizov. Tu algoritem poskuša iskati vzorec P (0… m-1) v besedilu T (0… .n-1).
tu bi bil najslabši primer, če se premik na drugo podvrsto ne izvede do primerjave M Th .
Najbližji par
Izjava problema: Če želite najti dve najbližji točki v množici n točk v dvodimenzionalni kartezijanski ravnini. Ob tej težavi je n številnih scenarijev. Primer iz resničnega življenja bi bil v sistemu za nadzor zračnega prometa, kjer morate nadzorovati letala, ki letijo blizu drug drugemu in ugotoviti morate najvarnejšo minimalno razdaljo, ki bi jo morala ta letala vzdrževati.
Vir: Wikipedia
Algoritem brute sile izračuna razdaljo med posameznimi različnimi točkami in vrne indekse točke, za katero je razdalja najmanjša.
Bruta sila reši ta problem s časovno zapletenostjo (O (n2)), kjer je n število točk.
Spodaj pseudo-koda uporablja algoritem brute force, da najde najbližjo točko.
Konveksni trup
Izjava problema : Konveksni trup je najmanjši poligon, ki vsebuje vse točke. Konveksni trup niza s točke je najmanjši konveksni mnogokotnik, ki vsebuje s.
Konveksni trup za ta niz točk je konveksni mnogokotnik z vrhovi na P1, P5, P6, P7, P3
Linijski odsek P1 in Pn niza n točk je del izbočenega trupa, če in samo, če vse druge točke niza ležijo znotraj meje poligona, ki jo tvori odsek črte.
Povezajmo ga z gumijastim trakom,
Točka (x1, y1), (x2, y2) naredi črto ax + za = c
Kadar je a = y2-y1, b = x2-x1 in c = x1 * y2 - x2 * y1 in ravnino deli s sekiro + za-c 0
Torej moramo za druge točke preveriti ax + by-c.
Skrbna sila reši ta problem s časovno zapletenostjo O (n 3 )
Izčrpno iskanje
Za diskretne težave, pri katerih ni znane učinkovite rešitve, je treba vsako preizkusiti vsako možno rešitev na zaporedni način.
Izčrpno iskanje je dejavnost za sistematično iskanje vseh možnih rešitev problema.
Poskusimo rešiti težavo potovalnega prodajalca (TSP) z izčrpnim algoritmom iskanja Brute.
Izjava problema: Obstaja n mest, po katerih mora prodajalec potovati, on želi najti najkrajšo pot, ki pokriva vsa mesta.
Razmišljamo o Hamiltonovem vezju za rešitev te težave. Če vezje obstaja, lahko katera koli točka začne točke in konča. Ko izberemo začetne točke, potrebujemo le vrstni red za preostala točila, tj n-1
Potem bi bilo (n-1)! Možne kombinacije in skupni stroški za izračun poti bi bili O (n). tako bi skupna časovna zahtevnost znašala O (n!).
Zaključek
Zdaj, ko smo prišli do konca te vadnice, upam, da ste zdaj dobili pošteno predstavo o tem, kaj je Brute Force. Videli smo tudi različne algoritme Brute force, ki jih lahko uporabite v svoji prijavi.
Priporočeni članki
To je vodnik po algoritmu Brute Force. Tu smo razpravljali o osnovnih pojmih algoritma Brute Force. Če želite izvedeti več, lahko preberete tudi druge naše predlagane članke -
- Kaj je algoritem?
- Vprašanja o intervjuju z algoritmom
- Uvod v algoritem
- Algoritem v programiranju