Uvod u algoritam brute force
"Podaci su novo ulje" ovo je nova mantra koja vlada globalnom ekonomijom. Živimo u digitalnom svijetu i svaki se posao vrti oko podataka koji pretvaraju u profit i pomažu industrijama da ostanu ispred konkurencije. Brzom digitalizacijom, eksponencijalnim porastom poslovnog modela temeljenog na aplikacijama, cyber-zločini predstavljaju stalnu prijetnju. Jedna od takvih uobičajenih aktivnosti koju hakeri obavljaju je Brute force.
Brute Force je pristup pokušaju i pogreške gdje napadači koriste programe kako bi isprobali različite kombinacije da bi provalili u bilo koju web stranicu ili sustav. Oni koriste automatizirani softver za ponavljajuće generacije kombinacija User ID-a i lozinki dok na kraju ne generiraju pravu kombinaciju.
Brute-Force Search
Bruce force pretraga je najčešći algoritam pretraživanja jer ne zahtijeva znanje o domeni, a sve što je potrebno jest opis stanja, legalni operatori, početno stanje i opis ciljanog stanja. To ne poboljšava performanse i potpuno se oslanja na računalnu snagu kako bi isprobao moguće kombinacije.
Algoritam brutalne sile pretražuje sve položaje u tekstu između 0 i nm, bez obzira na to počinje li uzorak ili ne. Nakon svakog pokušaja pomakne uzorak udesno za točno 1 položaj. Vremenska složenost ovog algoritma je O (m * n). pa ako tražimo n znakova u nizu od m znakova, trebat će n * m pokušaja.
Pogledajmo klasičan primjer putujućeg prodavača kako bi algoritam razumio na jednostavan način.
Pretpostavimo da prodavač mora proći 10 različitih gradova u nekoj zemlji i želi odrediti najkraće moguće rute iz svih mogućih kombinacija. Ovdje algoritam brutalne sile jednostavno izračunava udaljenost između svih gradova i odabire najkraći.
Drugi primjer je pokušaj probijanja petznamenkaste zaporke, a tada velika sila može potrajati i do 10 pokušaja probijanja koda.
Brute Force Sort
U tehnici sortiranja grubom silom, popis podataka se skenira više puta kako bi se pronašao najmanji element na popisu. Nakon svake iteracije po popisu, zamjenjuje najmanji element na vrhu snopa i započinje sljedeću iteraciju iz drugog najmanjeg podatka na popisu.
Gore navedena izjava može se pseudo-kodom napisati na sljedeći način.
Ovdje je problem u veličini 'n', a osnovna operacija je 'ako' test gdje se podaci uspoređuju u svakoj iteraciji. Neće biti razlike između najgoreg i najboljeg slučaja, jer no swap je uvijek n-1.
Odgovarajuće nizove grube sile
Ako su svi znakovi u obrascu jedinstveni, tada se može primijeniti podudaranje nizova Brute sile složenosti Big O (n). gdje je n duljina niza. Sporna sila podudaranja niza uspoređuje uzorak s podstrezom teksta u znaku dok ne dobije znak koji se podudara. Čim se utvrdi neusklađenost, preostali karakter podstranu pada, a algoritam prelazi na sljedeću podstinu.
Ispod pseudo kodovi objašnjavaju logiku podudaranja niza. Ovdje algoritam pokušava tražiti uzorak P (0… m-1) u tekstu T (0… .n-1).
ovdje bi najgori slučaj bio kad se prelazak na drugu podstranu ne napravi sve dok M Th usporedba.
Najbliži par
Izjava problema: Da biste pronašli dvije najbliže točke u skupu od n točaka u dvodimenzionalnoj kartezijanskoj ravnini. Nema ovog broja scenarija gdje se ovaj problem pojavljuje. Primjer iz stvarnog života bi bio u sustavu kontrole zračnog prometa u kojem morate pratiti zrakoplove koji lete blizu jedan drugom i morate otkriti najsigurniju minimalnu udaljenost koju ti zrakoplovi trebaju održavati.
Izvor: Wikipedia
Algoritam brute sile izračunava udaljenost između svakog različitog skupa točaka i vraća indekse točke za koju je udaljenost najmanja.
Skrutna sila rješava ovaj problem s vremenskom složenošću (O (n2)) gdje je n broj točaka.
Ispod pseudo-koda koristi algoritam brutalne sile da pronađe najbližu točku.
Konveksni trup
Izjava problema : Konveksni trup najmanji je poligon koji sadrži sve točke. Konveksni trup skupa s točke najmanji je konveksni mnogokut koji sadrži s.
Konveksni trup za ovaj skup točaka je konveksni mnogokut s vrhovima na P1, P5, P6, P7, P3
Ravni segmenti P1 i Pn skupa od n točaka dio su konveksnog trupa ako i samo ako su sve ostale točke skupa smještene unutar granice poligona koju tvori segmentni pravac.
Povezajmo to gumenom vrpcom,
Točke (x1, y1), (x2, y2) čine linija ax + po = c
Kada su a = y2-y1, b = x2-x1 i c = x1 * y2 - x2 * y1, a ravninu dijeli s osovinom + za-c 0
Stoga moramo provjeriti ax + by-c za ostale točke.
Grube sile rješavaju taj problem s vremenskom složenošću O (n 3 )
Iscrpna pretraga
Za diskretne probleme u kojima nije poznato učinkovito rješenje, postaje nužno testirati svako moguće rješenje na način koji slijedi.
Iscrpna potraga je aktivnost za sustavno pronalaženje svih mogućih rješenja problema.
Pokušajmo riješiti problem Putničkog prodavača (TSP) koristeći Bruteov iscrpni algoritam pretraživanja.
Izjava problema: Postoji n gradova u koje prodavač treba putovati, a on želi otkriti najkraću rutu koja pokriva sve gradove.
Razmišljamo o Hamiltonovom krugu da riješi ovaj problem. Ako postoji krug, bilo koja točka može započeti vrhove i završiti vrhove. Nakon odabira početnih vrhova, potreban nam je samo redoslijed za preostale vrhove tj. N-1
Tada bi bilo (n-1)! Moguće kombinacije i ukupni trošak za izračunavanje puta bi bili O (n). stoga bi ukupna vremenska složenost bila O (n!).
Zaključak
Sada kada smo stigli do kraja ovog vodiča, nadam se da ste sada dobili korektnu predstavu o tome što je Brute Force. Vidjeli smo i razne algoritme Brute force koji možete primijeniti u svojoj prijavi.
Preporučeni članci
Ovo je vodič za algoritam Brute Force-a. Ovdje smo razgovarali o osnovnim konceptima algoritma Brute Force. Možete i proći naše druge predložene članke da biste saznali više -
- Što je algoritam?
- Pitanja o intervjuu za algoritam
- Uvod u algoritam
- Algoritam u programiranju