Inleiding tot Brute Force Algorithm
"Data is de nieuwe olie", dit is de nieuwe mantra die de wereldeconomie regeert. We leven in de digitale wereld en elk bedrijf draait om gegevens die zich vertalen in winst en de industrie helpen om hun concurrentie voor te blijven. Met de snelle digitalisering, een exponentiële toename van het app-gebaseerde bedrijfsmodel, vormen cybercriminaliteit een constante bedreiging. Een dergelijke veel voorkomende activiteit die hackers uitvoeren, is de brute kracht.
Brute Force is een trial and error-aanpak waarbij aanvallers programma's gebruiken om verschillende combinaties uit te proberen om in te breken in websites of systemen. Ze gebruiken geautomatiseerde software om herhaaldelijk de combinaties Gebruikers-ID en wachtwoorden te genereren totdat deze uiteindelijk de juiste combinatie genereert.
Brute-Force Search
Brute Force Search is het meest voorkomende zoekalgoritme, omdat geen domeinkennis vereist is. Het enige dat vereist is, is een statusbeschrijving, juridische operatoren, de initiële status en de beschrijving van een doelstatus. Het verbetert de prestaties niet en is volledig afhankelijk van de rekenkracht om mogelijke combinaties uit te proberen.
Het brute force-algoritme doorzoekt alle posities in de tekst tussen 0 en nm of het optreden van het patroon daar begint of niet. Na elke poging schuift het patroon exact 1 positie naar rechts. De tijdcomplexiteit van dit algoritme is O (m * n). dus als we op zoek zijn naar n tekens in een reeks van m tekens, dan zullen n * m pogingen nodig zijn.
Laten we eens kijken naar een klassiek voorbeeld van een reizende verkoper om het algoritme op een eenvoudige manier te begrijpen.
Stel dat een verkoper 10 verschillende steden in een land moet doorkruisen en uit alle mogelijke combinaties de kortst mogelijke routes wil bepalen. Hier berekent brute force-algoritme eenvoudig de afstand tussen alle steden en selecteert de kortste.
Een ander voorbeeld is om een poging te doen om het 5-cijferige wachtwoord te breken, waarna brute kracht tot 105 pogingen kan kosten om de code te kraken.
Brute Force Sort
In de brute force sorteertechniek wordt de lijst met gegevens meerdere keren gescand om het kleinste element in de lijst te vinden. Na elke iteratie over de lijst, vervangt het het kleinste element bovenaan de stapel en start de volgende iteratie vanaf de op een na kleinste gegevens in de lijst.
De bovenstaande verklaring kan als volgt in pseudocode worden geschreven.
Hier is het probleem van grootte 'n' en de basisbewerking is een 'als'-test waarbij de gegevensitems in elke iteratie worden vergeleken. Er is geen verschil tussen het slechtste en het beste geval, omdat het nr van swap altijd n-1 is.
Brute Force String Matching
Als alle tekens in het patroon uniek zijn, kan Brute-force string-matching worden toegepast met de complexiteit van Big O (n). waarbij n de lengte van de string is. Brute force String matching vergelijkt het patroon met de substring van een tekst karakter voor karakter totdat het een niet-overeenkomend karakter krijgt. Zodra een mismatch wordt gevonden, wordt het resterende karakter van de substring weggelaten en gaat het algoritme naar de volgende substring.
De onderstaande pseudocodes verklaren de logica van de stringovereenkomst. Hier probeert het algoritme te zoeken naar een patroon van P (0 … m-1) in de tekst T (0 … .n-1).
hier zou het ergste geval zijn wanneer er pas naar een andere substring wordt overgeschakeld tot de vergelijking van Th .
Dichtstbijzijnde paar
Probleemstelling: de twee dichtstbijzijnde punten in een reeks van n punten in het tweedimensionale cartesische vlak achterhalen. Er is geen aantal scenario's waarin dit probleem zich voordoet. Een echt voorbeeld zou zijn in een luchtverkeersleidingssysteem waar u de vliegtuigen die in de buurt van elkaar vliegen moet volgen en u de veiligste minimale afstand moet vinden die deze vliegtuigen moeten aanhouden.
Bron: Wikipedia
Brute force-algoritme berekent de afstand tussen elke afzonderlijke reeks punten en retourneert de indexen van het punt waarvoor de afstand het kleinst is.
Brute kracht lost dit probleem op met de tijdcomplexiteit van (O (n2)) waarbij n het aantal punten is.
Onder de pseudo-code wordt het brute force-algoritme gebruikt om het dichtstbijzijnde punt te vinden.
Convexe romp
Probleemstelling : een bolle romp is de kleinste veelhoek die alle punten bevat. De convexe romp van een reeks s van het punt is de kleinste convexe polygoon die s bevat.
De convexe romp voor deze reeks punten is de convexe polygoon met hoekpunten op P1, P5, P6, P7, P3
Een lijnsegment P1 en Pn van een set van n-punten is een deel van de convexe romp als en alleen als alle andere punten van de set binnen de veelhoekgrens liggen die wordt gevormd door het lijnsegment.
Laten we het relateren aan het elastiekje,
Punt (x1, y1), (x2, y2) maken de lijn ax + by = c
Wanneer a = y2-y1, b = x2-x1 en c = x1 * y2 - x2 * y1 en het vlak deelt door ax + by-c 0
We moeten dus ax + by-c controleren op de andere punten.
Brute kracht lost dit probleem op met de tijdcomplexiteit van O (n 3 )
Uitgebreid zoeken
Voor afzonderlijke problemen waarbij er geen bekende efficiënte oplossing is, wordt het een noodzaak om elke mogelijke oplossing op een opeenvolgende manier te testen.
Uitgebreid zoeken is een activiteit om systematisch alle mogelijke oplossingen voor een probleem te vinden.
Laten we proberen het probleem van de handelsreiziger (TSP) op te lossen met behulp van het uitgebreide algoritme van Brute Search.
Probleemstelling: er zijn n steden die verkoper moet afleggen, hij wil de kortste route vinden die alle steden omvat.
We overwegen Hamilton Circuit om dit probleem op te lossen. Als er een circuit bestaat, kan elk punt hoekpunten beginnen en eindigen. Nadat de starthoekpunten zijn geselecteerd, hebben we alleen de volgorde voor de resterende hoekpunten nodig, namelijk n-1
Dan zou er (n-1) zijn! Mogelijke combinaties en de totale kosten voor het berekenen van het pad zijn O (n). dus de totale tijdcomplexiteit zou O (n!) zijn.
Conclusie
Nu we het einde van deze tutorial hebben bereikt, hoop ik dat jullie nu een goed idee hebben van wat Brute Force is. We hebben ook het verschillende Brute Force-algoritme gezien dat u in uw toepassing kunt toepassen.
Aanbevolen artikelen
Dit is een gids voor Brute Force Algorithm geweest. Hier hebben we de basisconcepten van het Brute Force-algoritme besproken. U kunt ook onze andere voorgestelde artikelen doornemen voor meer informatie -
- Wat is een algoritme?
- Vragen tijdens solliciteren bij Algorithm
- Inleiding tot algoritme
- Algoritme in programmeren