Introduktion til Brute Force Algoritme
“Data er den nye olie”, dette er den nye mantra, der er verdensherredømme. Vi lever i den digitale verden, og enhver virksomhed drejer sig om data, der omsættes til overskud og hjælper industrierne med at holde sig foran deres konkurrence. Med den hurtige digitalisering, en eksponentiel stigning i den appbaserede forretningsmodel, er cyber-forbrydelser en konstant trussel. En sådan almindelig aktivitet, som hackere udfører, er Brute-styrken.
Brute Force er en prøve- og fejltilgang, hvor angribere bruger programmer til at prøve forskellige kombinationer for at bryde ind på ethvert websted eller system. De bruger automatiseret software til gentagne gange at generere bruger-id og adgangskodekombinationer, indtil den til sidst genererer den rigtige kombination.
Brute-Force Search
Brute force search er den mest almindelige søgealgoritme, da den ikke kræver nogen domæneviden, alt, hvad der kræves, er en tilstandsbeskrivelse, juridiske operatører, den oprindelige tilstand og beskrivelsen af en måltilstand. Det forbedrer ikke ydelsen og er helt afhængig af computerkraften til at afprøve mulige kombinationer.
Brute-kraftalgoritmen søger alle positionerne i teksten mellem 0 og nm, uanset om forekomsten af mønster starter der eller ej. Efter hvert forsøg flytter det mønsteret til højre med nøjagtigt 1 position. Tidskompleksiteten af denne algoritme er O (m * n). så hvis vi søger efter n tegn i en streng med m tegn, vil det tage n * m forsøg.
Lad os se et klassisk eksempel på en rejsende sælger for at forstå algoritmen på en nem måde.
Antag, at en sælger skal rejse 10 forskellige byer i et land, og han ønsker at bestemme de kortest mulige ruter ud af alle mulige kombinationer. Her beregner brute force-algoritmen blot afstanden mellem alle byer og vælger den korteste.
Et andet eksempel er at gøre et forsøg på at bryde det 5-cifrede kodeord, da kan brute force tage op til 10 5 forsøg på at knække koden.
Brute Force Sort
I sorteringsteknikken for brute force scannes listen med data flere gange for at finde det mindste element på listen. Efter hver iteration over listen erstatter det det mindste element øverst i stakken og starter den næste iteration fra de anden mindste data på listen.
Ovenstående udsagn kan skrives i pseudokode som følger.
Her er problemet af størrelse 'n', og den grundlæggende operation er 'hvis' -test, hvor dataelementerne sammenlignes i hver iteration. Det vil ikke være nogen forskel mellem det værste og bedste tilfælde, da antallet af swap altid er n-1.
Brute Force String Matching
Hvis alle tegnene i mønsteret er unikke, kan Brute Force-streng matching tilpasses med kompleksiteten af Big O (n). hvor n er længden på strengen. Brute force String matching sammenligner mønsteret med substring af en tekstkarakter efter karakter, indtil den får et uoverensstemmende tegn. Så snart der er fundet en uoverensstemmelse, falder den resterende karakter af undertrækket, og algoritmen flytter til den næste substring.
Nedenstående pseudokoder forklarer strengets matchende logik. Her forsøger algoritmen at søge efter et mønster af P (0… m-1) i teksten T (0… .n-1).
her ville det værste tilfælde være, når der ikke foretages en skift til en anden substring, før M Th sammenligning.
Tættest par
Problemerklæring: At finde ud af de to nærmeste punkter i et sæt n punkter i det todimensionelle kartesiske plan. Der er et antal scenarier, hvor dette problem opstår. Et ægte eksempel kunne være i et lufttrafikstyringssystem, hvor du er nødt til at overvåge flyene, der flyver tæt på hinanden, og du er nødt til at finde ud af den sikreste minimale afstand, som disse fly skal have.
Kilde: Wikipedia
Brute-kraftalgoritme beregner afstanden mellem hvert tydeligt sæt punkter og returnerer indekserne for det punkt, som afstanden er den mindste for.
Brute force løser dette problem med tidskompleksiteten til (O (n2)), hvor n er antallet af punkter.
Nedenfor bruger pseudokoden brute force-algoritmen til at finde det nærmeste punkt.
Konveks skrog
Problemerklæring : Et konvekst skrog er den mindste polygon, der indeholder alle punkter. Det konvekse skrog i et sæt af punktet er den mindste konvekse polygon, der indeholder s.
Det konvekse skrog for dette sæt af punkter er den konvekse polygon med hjørner ved P1, P5, P6, P7, P3
Et linjesegment P1 og Pn i et sæt n punkter er en del af det konvekse skrog, hvis og kun hvis alle de andre punkter i sættet ligger inden for polygongrænsen dannet af linjesegmentet.
Lad os fortælle det med gummibåndet,
Punkt (x1, y1), (x2, y2) foretager linjen aks + med = c
Når a = y2-y1, b = x2-x1 og c = x1 * y2 - x2 * y1 og deler planet med øks + by-c 0
Så vi er nødt til at tjekke øks + by-c for de andre punkter.
Brute force løser dette problem med tidskompleksiteten af O (n 3 )
Udtømmende søgning
For diskrete problemer, hvor der ikke er nogen kendt effektiv løsning, bliver det en nødvendighed at teste hver eneste mulige løsning på en rækkefølge.
Udtømmende søgning er en aktivitet for at finde ud af alle mulige løsninger på et problem på en systematisk måde.
Lad os prøve at løse det rejsende sælgerproblem (TSP) ved hjælp af Brute udtømmende søgealgoritme.
Problemerklæring: Der er n byer, som sælgeren har brug for at rejse, han ønsker at finde ud af den korteste rute, der dækker alle byer.
Vi overvejer Hamilton Circuit for at løse dette problem. Hvis der findes et kredsløb, kan et hvilket som helst punkt starte knudepunkter og endehøjder. Når først starthøjdepunkter er valgt, har vi kun brug for rækkefølgen for de resterende hjørner, dvs. n-1
Så ville der være (n-1)! Eventuelle kombinationer og de samlede omkostninger til beregning af stien ville være O (n). således ville den totale tidskompleksitet være O (n!).
Konklusion
Nu hvor vi er nået til slutningen af denne tutorial, håber jeg, at I nu har fået en god idé om, hvad Brute Force er. Vi har også set de forskellige Brute Force-algoritmer, som du kan anvende i din applikation.
Anbefalede artikler
Dette har været en guide til Brute Force Algorithm. Her diskuterede vi de grundlæggende koncepter for Brute Force-algoritmen. Du kan også gennemgå vores andre foreslåede artikler for at lære mere -
- Hvad er en algoritme?
- Spørgsmål til algoritmeintervju
- Introduktion til algoritme
- Algoritme i programmering