In der Informatik erzeugen Suche der rohen Gewalt oder erschöpfende Suche, auch bekannt als und prüfen, ist eine triviale, aber sehr allgemeine problemlösende Technik, die daraus besteht, systematisch alle möglichen Kandidaten für die Lösung aufzuzählen und zu überprüfen, ob jeder Kandidat die Behauptung des Problems befriedigt. Zum Beispiel soll ein Algorithmus der rohen Gewalt, um die Teiler einer natürlichen Zahl n zu finden, alle ganzen Zahlen von 1 bis die Quadratwurzel von n aufzählen und überprüfen, ob jeder von ihnen n ohne Rest teilt. Für ein anderes Beispiel, denken Sie, dass die populären acht Königinnen verwirrt sind, der bittet, acht Königinnen auf einem Standardschachbrett zu legen, so dass keine Königin irgendwelchen anderer angreift. Eine Annäherung der rohen Gewalt würde alle möglichen Maßnahmen von 8 Stücken in den 64 Quadraten, und für jede Einordnung untersuchen, überprüf, ob eine Königin irgendwelchen anderer angreift.

Suche der rohen Gewalt ist einfach durchzuführen, und wird immer eine Lösung finden, wenn sie besteht. Jedoch sind seine Kosten zur Zahl von Kandidat-Lösungen proportional, die, in vielen praktischen Problemen, dazu neigt, sehr schnell als die Größe der Problem-Zunahmen zu wachsen. Deshalb wird Suche der rohen Gewalt normalerweise verwendet, wenn die Problem-Größe beschränkt wird, oder wenn es mit dem Problem spezifische Heuristik gibt, die verwendet werden kann, um den Satz von Kandidat-Lösungen einer lenksamen Größe zu reduzieren. Die Methode wird auch verwendet, wenn die Einfachheit der Durchführung wichtiger ist als Geschwindigkeit.

Das ist zum Beispiel in kritischen Anwendungen der Fall, wo irgendwelche Fehler im Algorithmus sehr ernste Folgen haben würden; oder wenn man einen Computer verwendet, um einen mathematischen Lehrsatz zu beweisen. Suche der rohen Gewalt ist auch als "Grundlinie"-Methode nützlich, wenn sie andere Algorithmen oder metaheuristics bewertet. Tatsächlich kann Suche der rohen Gewalt als der einfachste metaheuristic angesehen werden. Suche der rohen Gewalt sollte mit dem Zurückverfolgen nicht verwirrt sein, wo große Sätze von Lösungen verworfen werden können, ohne (als in der Lehrbuch-Computerlösung des acht Königin-Problems oben) ausführlich aufgezählt zu werden. Die Methode der rohen Gewalt, für einen Artikel in einem Tisch — nämlich zu finden, überprüfen Sie, dass alle Einträge der Letzteren, folgend — geradlinige Suche genannt wird.

Das Einführen der Suche der rohen Gewalt

Grundlegender Algorithmus

Um Suche der rohen Gewalt auf eine spezifische Klasse von Problemen anzuwenden, muss man vier Verfahren, erstens, folgend, gültig, und Produktion einsetzen. Diese Verfahren sollten als ein Parameter die Daten P für das besondere Beispiel des Problems nehmen, das gelöst werden soll, und den folgenden tun sollte:

1. erst (P): Erzeugen Sie eine erste Kandidat-Lösung für P.
2. als nächstes (P, c): Erzeugen Sie den folgenden Kandidaten für P nach dem aktuellen c.
3. gültig (P, c): Überprüfen Sie, ob Kandidat c eine Lösung für P ist.
4. Produktion (P, c): Verwenden Sie die Lösung c von P als passend zur Anwendung.

Das folgende Verfahren muss auch erzählen, wenn es keine Kandidaten mehr für das Beispiel P, nach dem aktuellen c gibt. Eine günstige Weise zu tun, der ist, einen "ungültigen Kandidaten", einige herkömmliche Daten zurückzugeben, schätzt Λ, der von jedem echten Kandidaten verschieden ist. Ebenfalls sollte das erste Verfahren Λ zurückgeben, wenn es keine Kandidaten überhaupt für das Beispiel P gibt. Die Methode der rohen Gewalt wird dann durch den Algorithmus ausgedrückt

c erst (P)

während c Λ' wenn' gültig (P, c) dann Produktion (P, c) c als nächstes (P, c) tun

Zum Beispiel, wenn sie nach den Teilern einer ganzen Zahl n suchen, sind die Beispiel-Daten P die Nummer n. Der Anruf erst (n) sollte die ganze Zahl 1 wenn n 1, oder Λ sonst zurückgeben; der Anruf als nächstes (n, c) sollte c + 1 wenn c zurückgeben

Kombinatorische Explosion

Der Hauptnachteil der Methode der rohen Gewalt ist, dass, für viele wirkliche Probleme, die Zahl von natürlichen Kandidaten untersagend groß ist. Zum Beispiel, wenn wir nach den Teilern einer Zahl, wie beschrieben, oben suchen, wird die Zahl von geprüften Kandidaten die gegebene Nummer n sein. So, wenn n sechzehn dezimale Ziffern, sagen wir, hat, wird die Suche Durchführung von mindestens 10 Computerinstruktionen verlangen, die mehrere Tage auf einem typischen PC nehmen werden. Wenn n eine zufällige natürliche 64-Bit-Zahl ist, die ungefähr 19 dezimale Ziffern im Durchschnitt hat, wird die Suche ungefähr 10 Jahre nehmen. Dieses steile Wachstum in der Zahl von Kandidaten, als die Größe der Datenzunahmen, kommt in allen Sorten von Problemen vor. Zum Beispiel, wenn wir eine besondere Neuordnung von 10 Briefen suchen, dann haben wir 10! = 3,628,800 Kandidaten, um in Betracht zu ziehen, den ein typischer PC erzeugen und in weniger als einer Sekunde prüfen kann. Jedoch wird das Hinzufügen eines mehr Briefs — der nur eine 10-%-Zunahme in der Datengröße ist — die Zahl von Kandidaten um 11 — eine 1000-%-Zunahme multiplizieren. Für 20 Briefe ist die Zahl von Kandidaten 20 Jahre alt!, der über 2.4×10 oder 2.4 quintillion ist; und die Suche wird ungefähr 10,000 Jahre nehmen. Dieses unwillkommene Phänomen wird die kombinatorische Explosion allgemein genannt.

Suchen der rohen Gewalt beschleunigend

Eine Weise, einen Algorithmus der rohen Gewalt zu beschleunigen, soll den Suchraum, d. h. den Satz von Kandidat-Lösungen, durch das Verwenden der zur Problem-Klasse spezifischen Heuristik reduzieren.

Denken Sie zum Beispiel das populäre acht Königin-Problem, das bittet, acht Königinnen auf einem Standardschachbrett zu legen, so dass keine Königin irgendwelchen anderer angreift. Da jede Königin in einige der 64 Quadrate gelegt werden kann, im Prinzip gibt es 64 = 281,474,976,710,656 (mehr als 281 Trillionen) Möglichkeiten in Betracht zu ziehen. Jedoch, wenn wir bemerken, dass die Königinnen alle ähnlich sind, und dass keine zwei Königinnen auf demselben Quadrat gelegt werden können, beschließen wir, dass die Kandidaten alle möglichen Weisen sind, eine Reihe 8 Quadrate vom Satz alle 64 Quadrate zu wählen; was 64 bedeutet, wählen 8 = 64!/56! 8! = 4,426,165,368 Kandidat-Lösungen — über 1/60,000 der vorherigen Schätzung. Wirklich ist es leicht zu sehen, dass keine Einordnung mit zwei Königinnen auf derselben Reihe oder derselben Säule eine Lösung sein kann. Deshalb können wir weiter den Satz von Kandidaten zu jenen Maßnahmen einschränken, wo Königin 1 in der Reihe 1 ist, ist Königin 2 in der Reihe 2 und so weiter; alle in verschiedenen Säulen. Wir können solch eine Einordnung durch eine Reihe von acht Zahlen c [1] durch c [8], jeder von ihnen zwischen 1 und 8 beschreiben, wo c [1] die Säule der Königin 1 ist, c [2] ist die Säule der Königin 2, und so weiter. Da diese Zahlen alles verschieden sein müssen, ist die Zahl von Kandidaten, um zu suchen, die Zahl von Versetzungen der ganzen Zahlen 1 bis 8, nämlich 8! = 40,320 — über 1/100,000 der vorherigen Schätzung und 1/7,000,000,000 des ersten. Da sich dieses Beispiel zeigt, ein kleines bisschen der Analyse wird häufig zu den dramatischen Verminderungen der Zahl von Kandidat-Lösungen führen, und kann ein unnachgiebiges Problem in ein triviales verwandeln. Dieses Beispiel zeigt auch, dass die Kandidat-Enumerationsverfahren (zuerst und als nächstes) für den eingeschränkten Satz von Kandidaten genauso einfach sein können wie diejenigen des ursprünglichen Satzes, oder noch einfacher. In einigen Fällen kann die Analyse die Kandidaten auf den Satz aller gültigen Lösungen reduzieren; d. h. es kann einen Algorithmus nachgeben, der direkt alle gewünschten Lösungen aufzählt (oder eine Lösung, als passend findet), ohne mit Tests und der Generation von ungültigen Kandidaten Zeit zu verschwenden. Denken Sie zum Beispiel das Problem, alle ganzen Zahlen zwischen 1 und 1,000,000 zu finden, die durch 417 gleichmäßig teilbar sind. Eine naive Lösung der rohen Gewalt würde alle ganzen Zahlen in der Reihe erzeugen, jeden von ihnen für die Teilbarkeit prüfend. Jedoch kann dieses Problem viel effizienter durch das Starten mit 417 und wiederholt das Hinzufügen 417 behoben werden, bis die Zahl 1,000,000 zu weit geht — der nur 2398 (= 1,000,000 ÷ 417) Schritte und keine Tests nimmt.

Umstellung der Suchraum

In Anwendungen, die nur eine Lösung, aber nicht alle Lösungen verlangen, wird die erwartete Laufzeit einer Suche der rohen Gewalt häufig von der Ordnung abhängen, in der die Kandidaten geprüft werden. Als eine allgemeine Regel sollte man die viel versprechendsten Kandidaten zuerst prüfen. Zum Beispiel, wenn man nach einem richtigen Teiler einer Zufallszahl n sucht, ist es besser, die Kandidat-Teiler in der zunehmenden Ordnung, von 2 bis n - 1 aufzuzählen, als der andere Weg ringsherum — weil die Wahrscheinlichkeit, dass n durch c teilbar ist, 1/c ist. Außerdem wird die Wahrscheinlichkeit eines Kandidaten, der gültig ist, häufig durch die vorherigen erfolglosen Proben betroffen. Denken Sie zum Beispiel das Problem zu finden, dass ein 1 Bit in gegebenen 1000 Bit P spannt. In diesem Fall sind die Kandidat-Lösungen die Indizes 1 bis 1000, und ein Kandidat c ist wenn P [c] = 1 gültig. Nehmen Sie jetzt an, dass das erste Bit von P ebenso wahrscheinlich 0 oder 1 sein wird, aber jedes Bit ist danach dem vorherigen mit 90-%-Wahrscheinlichkeit gleich. Wenn die Kandidaten in der zunehmenden Ordnung, 1 bis 1000, die Nummer t von untersuchten Kandidaten aufgezählt werden, bevor Erfolg ungefähr 6 im Durchschnitt sein wird. Andererseits, wenn die Kandidaten im Auftrag 1,11,21,31... 991,2,12,22,32 usw. aufgezählt werden, wird der erwartete Wert von t nur wenig mehr als 2 sein. Mehr allgemein sollte der Suchraum auf solche Art und Weise aufgezählt werden, dass der folgende Kandidat höchstwahrscheinlich gültig sein wird, vorausgesetzt, dass die vorherigen Proben nicht waren. So, wenn die gültigen Lösungen wahrscheinlich in einem Sinn "gebündelt" werden, dann sollte jeder neue Kandidat so weit möglich von den vorherigen in diesem demselben Sinn sein. Das gegenteilige hält natürlich, wenn die Lösungen wahrscheinlich gleichförmiger ausgedehnt werden als erwartet zufällig.

Alternativen zur Suche der rohen Gewalt

Es gibt viele andere Suchmethoden oder metaheuristics, die entworfen werden, um verschiedene Arten von teilweisen Kenntnissen auszunutzen, die man über die Lösung haben kann. Heuristik kann auch verwendet werden, um eine frühe Abkürzung von Teilen der Suche zu machen. Ein Beispiel davon ist der minimax Grundsatz, um Spielbäume zu suchen, der viele Subbäume in einer frühen Bühne in der Suche beseitigt. In bestimmten Feldern, wie Sprachsyntaxanalyse, können Techniken wie Karte-Syntaxanalyse Einschränkungen im Problem ausnutzen, ein Exponentialkompliziertheitsproblem in ein polynomisches Kompliziertheitsproblem zu reduzieren. In vielen Fällen, solcher als in Einschränkungsbefriedigungsproblemen, kann man den Suchraum mittels der Einschränkungsfortpflanzung drastisch reduzieren, die auf Einschränkungsprogrammiersprachen effizient durchgeführt wird. Der Suchraum für Probleme kann auch durch das Ersetzen des vollen Problems mit einer vereinfachten Version reduziert werden. Zum Beispiel, im Computerschach, anstatt den vollen minimax Baum aller möglichen Bewegungen für den Rest des Spiels zu schätzen, wird ein mehr beschränkter Baum von minimax Möglichkeiten mit dem Baum geschätzt, der an einer bestimmten Anzahl von Bewegungen und dem Rest des Baums wird beschneidet, der durch eine statische Einschätzungsfunktion näher wird kommt.

In der Geheimschrift

In der Geheimschrift ist ein Angriff der rohen Gewalt mit systematisch Überprüfung aller möglichen Schlüssel verbunden, bis der richtige Schlüssel gefunden wird. Diese Strategie kann in der Theorie, gegen irgendwelche encrypted Daten von einem Angreifer verwendet werden, der unfähig ist, jede Schwäche in einem Verschlüsselungssystem auszunutzen, das seine Aufgabe leichter sonst machen würde.

Die in der Verschlüsselung verwendete Schlüssellänge bestimmt die praktische Durchführbarkeit, einen Angriff der rohen Gewalt mit längeren Schlüsseln durchzuführen, die exponential schwieriger sind zu krachen als kürzere. Angriffe der rohen Gewalt können weniger wirksam durch das Verfinstern der Daten gemacht werden, die, etwas zu verschlüsseln sind, was es schwieriger für einen Angreifer macht zu erkennen, als er den Code geknackt hat. Eine der Maßnahmen der Kraft eines Verschlüsselungssystems ist, wie lange es einen Angreifer theoretisch bringen würde, um einen erfolgreichen Angriff der rohen Gewalt dagegen zu organisieren.

Siehe auch

• Angriff der rohen Gewalt
• Große O Notation