Introduktion till Brute Force Algoritm
"Data är den nya oljan", det här är den nya mantraen som styr den globala ekonomin. Vi lever i den digitala världen och varje företag kretsar kring data som översätter till vinster och hjälper branscherna att ligga före sin konkurrens. Med den snabba digitaliseringen, en exponentiell ökning av den appbaserade affärsmodellen, är cyberbrott ett konstant hot. En sådan vanlig aktivitet som hackare utför är Brute-kraften.
Brute Force är en prövnings- och felmetod där angripare använder program för att prova olika kombinationer för att bryta sig in på webbplatser eller system. De använder automatiserad programvara för att repetitivt generera användar-ID och lösenordskombinationer tills den så småningom genererar rätt kombination.
Brute-Force Search
Brute Force-sökning är den vanligaste sökalgoritmen eftersom den inte kräver någon domänkunskap, allt som krävs är en tillståndsbeskrivning, juridiska operatörer, det initiala tillståndet och en beskrivning av en måltillstånd. Det förbättrar inte prestandan och förlitar sig helt på datorkraften för att testa möjliga kombinationer.
Brutkraftalgoritmen söker efter alla positioner i texten mellan 0 och nm oavsett om förekomsten av mönstret börjar där eller inte. Efter varje försök flyttar det mönstret åt höger med exakt en position. Tidskomplexiteten för denna algoritm är O (m * n). så om vi söker efter n tecken i en sträng med m tecken så kommer det att ta n * m försök.
Låt oss se ett klassiskt exempel på en resande säljare för att förstå algoritmen på ett enkelt sätt.
Anta att en säljare måste resa 10 olika städer i ett land och han vill bestämma kortast möjliga rutter av alla möjliga kombinationer. Här beräknar brute force-algoritmen helt enkelt avståndet mellan alla städer och väljer den kortaste.
Ett annat exempel är att göra ett försök att bryta det 5-siffriga lösenordet då brute force kan ta upp till 10 5 försök att knäcka koden.
Brute Force Sort
I sorteringstekniken brute force skannas listan med data flera gånger för att hitta det minsta elementet i listan. Efter varje iteration över listan ersätter det det minsta elementet upptill i bunten och startar nästa iteration från den andra minsta informationen i listan.
Ovanstående uttalande kan skrivas i pseudokod enligt följande.
Här är problemet av storlek 'n' och den grundläggande åtgärden är 'if' -test där dataelementen jämförs i varje iteration. Det kommer inte att vara någon skillnad mellan det värsta och bästa fallet eftersom no-byte alltid är n-1.
Brute Force String Matching
Om alla tecken i mönstret är unika kan Brutkraftssträngsmatchning tillämpas med komplexiteten för Big O (n). där n är längden på strängen. Brute force String matchning jämför mönstret med substring av en texttecken efter tecken tills den får ett ojämförligt tecken. Så snart ett missförhållande hittas, tappas den återstående karaktären i substringsträngen och algoritmen flyttar till nästa substring.
Nedanstående pseudokoder förklarar strängmatchningslogiken. Här försöker algoritmen söka efter ett mönster av P (0 … m-1) i texten T (0 … .n-1).
här skulle det värsta fallet vara när en övergång till en annan substring inte görs förrän M Th jämförelse.
Närmaste par
Problemmeddelande: Att ta reda på de två närmaste punkterna i en uppsättning av n-punkter i det tvådimensionella kartesiska planet. Det finns ett antal scenarier där problemet uppstår. Ett verkligt exempel skulle vara i ett lufttrafikstyrningssystem där du måste övervaka de flygplan som flyger nära varandra och du måste ta reda på det säkraste minsta avstånd som dessa flygplan borde ha.
Källa: Wikipedia
Brute-kraftalgoritmen beräknar avståndet mellan varje tydlig uppsättning punkter och returnerar indexen för den punkt för vilken avståndet är det minsta.
Brutkraft löser detta problem med tidskomplexiteten för (O (n2)) där n är antalet punkter.
Under pseudokoden använder brute force-algoritmen för att hitta den närmaste punkten.
Konvex skrov
Problemdeklaration : Ett konvext skrov är den minsta polygonen som innehåller alla punkter. Det konvexa skrovet i en uppsättning av punkten är den minsta konvexa polygonen som innehåller s.
Det konvexa skrovet för denna uppsättning punkter är den konvexa polygonen med toppar vid P1, P5, P6, P7, P3
Ett linjesegment P1 och Pn hos en uppsättning av n-punkter är en del av det konvexa skrovet om och bara om alla andra punkter i uppsättningen ligger inom polygongränsen som bildas av linjesegmentet.
Låt oss relatera det till gummibandet,
Punkt (x1, y1), (x2, y2) gör linjen axel + med = c
När a = y2-y1, b = x2-x1 och c = x1 * y2 - x2 * y1 och delar planet med axel + by-c 0
Så vi måste kontrollera ax + by-c för de andra punkterna.
Brute force löser detta problem med tidskomplexiteten hos O (n 3 )
Uttömmande sökning
För diskreta problem där det inte finns någon känd effektiv lösning blir det en nödvändighet att testa varje möjlig lösning på ett sekventiellt sätt.
Uttömmande sökning är en aktivitet för att ta reda på alla möjliga lösningar på ett problem på ett systematiskt sätt.
Låt oss försöka lösa den resande säljaren Problemet (TSP) med Brute uttömmande sökalgoritm.
Problemdeklaration: Det finns n städer som säljaren behöver resa, han vill ta reda på den kortaste vägen som täcker alla städer.
Vi överväger Hamilton Circuit för att lösa detta problem. Om det finns en krets kan någon punkt starta vertikaler och slutkoder. När startvinklarna har valts behöver vi bara ordningen för de återstående topparna, dvs n-1
Då skulle det finnas (n-1)! Möjliga kombinationer och den totala kostnaden för att beräkna sökvägen skulle vara O (n). alltså skulle den totala tidskomplexiteten vara O (n!).
Slutsats
Nu när vi har kommit till slutet av denna tutorial hoppas jag att ni nu har fått en rättvisande uppfattning om vad Brute Force är. Vi har också sett de olika Brute Force-algoritmerna som du kan använda i din applikation.
Rekommenderade artiklar
Detta har varit en guide till Brute Force Algoritm. Här diskuterade vi de grundläggande koncepten för Brute Force Algoritm. Du kan också gå igenom våra andra föreslagna artiklar för att lära dig mer -
- Vad är en algoritm?
- Algoritmintervjufrågor
- Introduktion till algoritm
- Algoritm i programmering