Introduksjon til Brute Force Algorithm
“Data er den nye oljen”. Dette er den nye mantraen som styrer verdensøkonomien. Vi lever i den digitale verdenen og hver virksomhet dreier seg om data som kan oversettes til overskudd og hjelpe industriene til å ligge foran konkurransen. Med den raske digitaliseringen, en eksponentiell økning i den appbaserte forretningsmodellen, er nettkriminalitet en konstant trussel. En slik vanlig aktivitet som hackere utfører er Brute-styrken.
Brute Force er en prøve- og feiltilnærming der angripere bruker programmer for å prøve ut forskjellige kombinasjoner for å bryte inn på nettsteder eller systemer. De bruker automatisert programvare for repeterende å generere bruker-ID og passordkombinasjoner til den til slutt genererer riktig kombinasjon.
Brute-Force Search
Brute force search er den vanligste søkealgoritmen ettersom den ikke krever noen domenekunnskap, alt som kreves er en tilstandsbeskrivelse, juridiske operatører, den opprinnelige tilstanden og beskrivelsen av en måltilstand. Det forbedrer ikke ytelsen og er helt avhengig av datakraften for å prøve ut mulige kombinasjoner.
Brute force-algoritmen søker i alle posisjonene i teksten mellom 0 og nm om forekomsten av mønsteret starter der eller ikke. Etter hvert forsøk forskyver det mønsteret til høyre med nøyaktig en stilling. Tidskompleksiteten til denne algoritmen er O (m * n). så hvis vi søker etter n tegn i en streng med m tegn, vil det ta n * m forsøk.
La oss se et klassisk eksempel på en omreisende selger for å forstå algoritmen på en enkel måte.
Anta at en selger trenger å reise 10 forskjellige byer i et land, og han vil bestemme de kortest mulige rutene ut av alle mulige kombinasjoner. Her beregner brute force-algoritmen ganske enkelt avstanden mellom alle byene og velger den korteste.
Et annet eksempel er å gjøre et forsøk på å bryte det 5-sifrede passordet, da kan brute force ta opptil 10 5 forsøk på å knekke koden.
Brute Force Sort
I sorteringsteknikken for brute force blir listen over data skannet flere ganger for å finne det minste elementet i listen. Etter hver iterasjon over listen erstatter den det minste elementet øverst i bunken og starter den neste iterasjonen fra den nest minste dataen i listen.
Ovennevnte utsagn kan skrives i pseudokode som følger.
Her er problemet størrelse 'n' og den grunnleggende operasjonen er 'hvis' test der dataelementene blir sammenlignet i hver iterasjon. Det vil ikke være noen forskjell mellom det verste og beste tilfellet, ettersom byttenummeret alltid er n-1.
Brute Force String Matching
Hvis alle tegnene i mønsteret er unike, kan Brute force string matching tilpasses med kompleksiteten til Big O (n). hvor n er lengden på strengen. Brute force String matching sammenligner mønsteret med erstatningen av en tekstkarakter etter karakter til den får et feilaktig samsvarende tegn. Så snart det oppdages et misforhold, faller den gjenværende karakteren til understrengen bort og algoritmen flytter til neste understreng.
Pseudokodene nedenfor forklarer loggen for samsvarende streng. Her prøver algoritmen å søke etter et mønster av P (0 … m-1) i teksten T (0 … .n-1).
her vil det verste tilfelle være når det ikke blir skiftet til en annen substring før M Th- sammenligning.
Nærmeste par
Problemstilling: Å finne ut de to nærmeste punktene i et sett med n punkter i det todimensjonale kartesiske planet. Det er et antall scenarier der dette problemet oppstår. Et ekte eksempel kan være i et lufttrafikkstyringssystem der du må overvåke flyene som flyr nær hverandre og du må finne ut den tryggeste minimumsavstand disse flyene skal opprettholde.
Kilde: Wikipedia
Brute force-algoritmen beregner avstanden mellom hvert forskjellige sett med punkter og returnerer indeksene til punktet som avstanden er den minste for.
Brute force løser dette problemet med tidskompleksiteten til (O (n2)) der n er antall poeng.
Under pseudokoden bruker brute force-algoritmen for å finne det nærmeste punktet.
Konveks skrog
Problemerklæring : Et konvekst skrog er den minste polygon som inneholder alle punktene. Det konvekse skroget til et sett av punktet er den minste konvekse polygon som inneholder s.
Det konvekse skroget for dette settet av punkter er den konvekse polygon med toppunkt på P1, P5, P6, P7, P3
Et linjesegment P1 og Pn til et sett med n punkter er en del av det konvekse skroget, hvis og bare hvis alle de andre punktene i settet ligger innenfor polygongrensen dannet av linjesegmentet.
La oss forholde det til gummibåndet,
Punkt (x1, y1), (x2, y2) gjør linjen øks + 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 må sjekke øksa + by-c for de andre punktene.
Brute force løser dette problemet med tidskompleksiteten til O (n 3 )
Uttømmende søk
For diskrete problemer der det ikke er kjent effektiv løsning, blir det en nødvendighet å teste hver eneste mulige løsning på en sekvensiell måte.
Uttømmende søk er en aktivitet for å finne ut alle mulige løsninger på et problem på en systematisk måte.
La oss prøve å løse reisende selgerproblem (TSP) ved hjelp av Brute uttømmende søkealgoritme.
Problemerklæring: Det er n byer som selger trenger å reise, han ønsker å finne ut den korteste ruten som dekker alle byene.
Vi vurderer Hamilton Circuit for å løse dette problemet. Hvis en krets eksisterer, kan et hvilket som helst punkt starte hjørnepunktene og sluttpunktene. Når startpunktene er valgt, trenger vi bare rekkefølgen for de resterende toppunktene, dvs. n-1
Da ville det være (n-1)! Mulige kombinasjoner og den totale kostnaden for å beregne banen vil være O (n). dermed ville den totale tidskompleksiteten være O (n!).
Konklusjon
Nå som vi har kommet til slutten av denne opplæringen, håper jeg dere nå har fått en god ide om hva Brute Force er. Vi har også sett den forskjellige Brute force-algoritmen som du kan bruke i applikasjonen din.
Anbefalte artikler
Dette har vært en guide til Brute Force Algorithm. Her diskuterte vi de grunnleggende konseptene for Brute Force Algorithm. Du kan også gå gjennom andre foreslåtte artikler for å lære mer -
- Hva er en algoritme?
- Spørsmål om algoritmeintervju
- Introduksjon til algoritme
- Algoritme i programmering