Einführung in den Brute-Force-Algorithmus
"Daten sind das neue Öl" - das ist das neue Mantra, das die Weltwirtschaft regiert. Wir leben in der digitalen Welt und jedes Unternehmen dreht sich um Daten, die sich in Gewinnen niederschlagen und den Branchen helfen, sich von der Konkurrenz abzuheben. Mit der schnellen Digitalisierung, einer exponentiellen Zunahme des App-basierten Geschäftsmodells, sind Cyber-Verbrechen eine ständige Bedrohung. Eine solche übliche Aktivität, die Hacker ausführen, ist die Brute Force.
Brute Force ist ein Versuch-und-Irrtum-Ansatz, bei dem Angreifer mithilfe von Programmen verschiedene Kombinationen ausprobieren, um in Websites oder Systeme einzudringen. Sie verwenden automatisierte Software, um wiederholt die Benutzer-ID- und Kennwortkombinationen zu generieren, bis schließlich die richtige Kombination generiert wird.
Brute-Force-Suche
Die Brute-Force-Suche ist der gebräuchlichste Suchalgorithmus, da keine Domänenkenntnisse erforderlich sind. Es sind lediglich eine Zustandsbeschreibung, rechtliche Operatoren, der Anfangszustand und die Beschreibung eines Zielzustands erforderlich. Es verbessert die Leistung nicht und verlässt sich vollständig auf die Rechenleistung, um mögliche Kombinationen auszuprobieren.
Der Brute-Force-Algorithmus durchsucht alle Positionen im Text zwischen 0 und nm, ob das Auftreten des Musters dort beginnt oder nicht. Nach jedem Versuch wird das Muster um genau 1 Position nach rechts verschoben. Die zeitliche Komplexität dieses Algorithmus ist O (m * n). Wenn wir also nach n Zeichen in einer Folge von m Zeichen suchen, werden n * m Versuche benötigt.
Sehen wir uns ein klassisches Beispiel eines reisenden Verkäufers an, um den Algorithmus auf einfache Weise zu verstehen.
Angenommen, ein Verkäufer muss 10 verschiedene Städte in einem Land bereisen und möchte aus allen möglichen Kombinationen die kürzestmöglichen Routen ermitteln. Hier berechnet der Brute-Force-Algorithmus einfach die Entfernung zwischen allen Städten und wählt die kürzeste aus.
Ein anderes Beispiel ist der Versuch, das 5-stellige Passwort zu knacken. Dann kann Brute Force bis zu 10 5 Versuche unternehmen, den Code zu knacken.
Brute Force Sort
Bei der Brute-Force-Sortiertechnik wird die Datenliste mehrmals durchsucht, um das kleinste Element in der Liste zu finden. Nach jeder Iteration über der Liste wird das kleinste Element an die Spitze des Stapels gesetzt und die nächste Iteration ab den zweitkleinsten Daten in der Liste gestartet.
Die obige Anweisung kann wie folgt in Pseudocode geschrieben werden.
Hier liegt das Problem in der Größe 'n' und die Grundoperation ist ein 'if'-Test, bei dem die Datenelemente in jeder Iteration verglichen werden. Das wird kein Unterschied zwischen dem schlechtesten und dem besten Fall sein, da die Anzahl der Tauschvorgänge immer n-1 ist.
Brute-Force-String-Matching
Wenn alle Zeichen im Muster eindeutig sind, kann der Brute-Force-String-Abgleich mit der Komplexität von Big O (n) angewendet werden. Dabei ist n die Länge der Zeichenfolge. Brute Force String Matching vergleicht das Muster mit der Teilzeichenfolge eines Textes zeichenweise, bis es ein nicht übereinstimmendes Zeichen erhält. Sobald eine Nichtübereinstimmung gefunden wird, wird das verbleibende Zeichen der Teilzeichenfolge gelöscht und der Algorithmus wechselt zur nächsten Teilzeichenfolge.
Die folgenden Pseudocodes erläutern die String-Matching-Logik. Hier versucht der Algorithmus nach einem Muster von P (0… m-1) im Text T (0… n-1) zu suchen.
Hier wäre der schlimmste Fall, wenn eine Verschiebung zu einem anderen Teilstring erst nach dem M Th- Vergleich erfolgt.
Nächstes Paar
Problemstellung: Ermittlung der zwei nächsten Punkte in einer Menge von n Punkten in der zweidimensionalen kartesischen Ebene. Es gibt n Szenarien, in denen dieses Problem auftritt. Ein reales Beispiel wäre ein Flugsicherungssystem, bei dem Sie die Flugzeuge überwachen müssen, die in der Nähe fliegen, und den sichersten Mindestabstand ermitteln müssen, den diese Flugzeuge einhalten sollten.
Quelle: Wikipedia
Der Brute-Force-Algorithmus berechnet den Abstand zwischen den einzelnen Punktmengen und gibt die Indizes des Punkts zurück, für den der Abstand am kleinsten ist.
Brute Force löst dieses Problem mit der zeitlichen Komplexität von (O (n2)), wobei n die Anzahl der Punkte ist.
Unterhalb des Pseudocodes wird mit dem Brute-Force-Algorithmus der nächstgelegene Punkt ermittelt.
Konvexer Rumpf
Problemstellung : Eine konvexe Hülle ist das kleinste Polygon, das alle Punkte enthält. Die konvexe Hülle einer Menge s des Punktes ist das kleinste konvexe Polygon, das s enthält.
Die konvexe Hülle für diesen Satz von Punkten ist das konvexe Polygon mit Eckpunkten bei P1, P5, P6, P7, P3
Ein Liniensegment P1 und Pn einer Menge von n Punkten ist ein Teil der konvexen Hülle, wenn und nur wenn alle anderen Punkte der Menge innerhalb der durch das Liniensegment gebildeten Polygongrenze liegen.
Lassen Sie es uns mit dem Gummiband in Verbindung bringen,
Punkt (x1, y1), (x2, y2) machen die Linie ax + by = c
Wenn a = y2-y1, ist b = x2-x1 und c = x1 * y2 - x2 * y1 und teilt die Ebene durch ax + durch-c0
Wir müssen also ax + by-c auf die anderen Punkte überprüfen.
Brute Force löst dieses Problem mit der Zeitkomplexität von O (n 3 )
Erschöpfende Suche
Bei diskreten Problemen, bei denen keine effiziente Lösung bekannt ist, muss jede mögliche Lösung nacheinander getestet werden.
Eine erschöpfende Suche ist eine Aktivität, um alle möglichen Lösungen für ein Problem auf systematische Weise zu finden.
Versuchen wir, das Travelling Salesman Problem (TSP) mithilfe eines umfassenden Suchalgorithmus zu lösen.
Problemstellung: Es gibt n Städte, die der Verkäufer bereisen muss. Er möchte die kürzeste Route ermitteln, die alle Städte abdeckt.
Wir ziehen Hamilton Circuit in Betracht, um dieses Problem zu lösen. Wenn ein Kreis existiert, kann jeder Punkt Eckpunkte beginnen und Eckpunkte beenden. Sobald die Startscheitelpunkte ausgewählt sind, benötigen wir nur die Reihenfolge für die verbleibenden Scheitelpunkte, dh n-1
Dann wäre da (n-1)! Mögliche Kombinationen und die Gesamtkosten für die Berechnung des Pfades wären O (n). somit wäre die Gesamtzeitkomplexität O (n!).
Fazit
Nachdem wir das Ende dieses Tutorials erreicht haben, hoffe ich, dass ihr jetzt eine gute Vorstellung davon habt, was Brute Force ist. Wir haben auch die verschiedenen Brute-Force-Algorithmen gesehen, die Sie in Ihrer Anwendung anwenden können.
Empfohlene Artikel
Dies war eine Anleitung zum Brute-Force-Algorithmus. Hier haben wir die grundlegenden Konzepte des Brute-Force-Algorithmus diskutiert. Sie können auch unsere anderen Artikelvorschläge durchgehen, um mehr zu erfahren -
- Was ist ein Algorithmus?
- Algorithmus Interview Fragen
- Einführung in den Algorithmus
- Algorithmus in der Programmierung