In der Informatik ist ein Suchalgorithmus ein Algorithmus, für einen Artikel mit angegebenen Eigenschaften unter einer Sammlung von Sachen zu finden. Die Sachen können individuell als Aufzeichnungen in einer Datenbank versorgt werden; oder kann Elemente eines Suchraums sein, der durch eine mathematische Formel oder Verfahren wie die Wurzeln einer Gleichung mit Variablen der ganzen Zahl definiert ist; oder eine Kombination der zwei, wie die Stromkreise von Hamiltonian eines Graphen.

Klassen von Suchalgorithmen

Für virtuelle Suchräume

Algorithmen, um virtuelle Bereiche zu suchen, werden im Einschränkungsbefriedigungsproblem verwendet, wo die Absicht ist, eine Reihe von Wertzuweisungen zu bestimmten Variablen zu finden, die spezifische mathematische Gleichungen und inequations befriedigen werden. Sie werden auch verwendet, wenn die Absicht ist, eine variable Anweisung zu finden, die maximieren oder eine bestimmte Funktion jener Variablen minimieren wird. Algorithmen für diese Probleme schließen die grundlegende Suche der rohen Gewalt ein (auch hat "naive" oder "uninformierte" Suche genannt), und eine Vielfalt der Heuristik, die versuchen, teilweise Kenntnisse über die Struktur des Raums, wie geradlinige Entspannung, Einschränkungsgeneration und Einschränkungsfortpflanzung auszunutzen.

Eine wichtige Unterklasse ist die lokalen Suchmethoden, diese Ansicht die Elemente des Suchraums als die Scheitelpunkte eines Graphen mit Rändern, die durch eine Reihe der auf den Fall anwendbaren Heuristik definiert sind; und scannen Sie den Raum, indem Sie sich vom Artikel bis Artikel entlang den Rändern, zum Beispiel gemäß dem steilsten Abstieg oder am besten dem ersten Kriterium, oder in einer stochastischen Suche bewegen. Diese Kategorie schließt eine große Vielfalt von allgemeinen metaheuristic Methoden, solcher, wie vorgetäuscht, das Ausglühen, die tabu Suche, die A-Mannschaften und die genetische Programmierung, diese Vereinigung willkürliche Heuristik auf spezifische Weisen ein.

Diese Klasse schließt auch verschiedene Baumsuchalgorithmen, diese Ansicht die Elemente als Scheitelpunkte eines Baums ein, und überqueren Sie diesen Baum in einer Sonderbestellung. Beispiele der Letzteren schließen die erschöpfenden Methoden wie Tiefensuche und Breitensuche, sowie verschiedene heuristische Suchbaumbeschneidungsmethoden wie das Zurückverfolgen und der Zweig und gebunden ein. Verschieden von allgemeinem metaheuristics, den bei der besten Arbeit nur in einem probabilistic Sinn, wie man versichert, viele dieser Baumsuche-Methoden die genaue oder optimale Lösung, wenn gegeben, genug Zeit finden.

Eine andere wichtige Unterklasse besteht aus Algorithmen, für den Spielbaum von Spielen des vielfachen Spielers, wie Schach oder backgammon zu erforschen, dessen Knoten aus allen möglichen Spielsituationen bestehen, die sich aus der aktuellen Situation ergeben konnten. Die Absicht in diesen Problemen ist, die Bewegung zu finden, die die beste Chance eines Gewinns zur Verfügung stellt, alle möglichen Bewegungen des Gegners in Betracht ziehend. Ähnliche Probleme kommen vor, wenn Menschen oder Maschinen aufeinander folgende Entscheidungen treffen müssen, deren Ergebnisse nicht völlig unter jemandes Kontrolle, solcher als in der Roboter-Leitung oder im Marketing, finanzieller oder militärischer Strategie-Planung sind. Diese Art des Problems - kombinatorischer Suche - ist im Zusammenhang der künstlichen Intelligenz umfassend studiert worden. Beispiele von Algorithmen für diese Klasse sind der minimax Algorithmus, die Beschneidung des Alpha-Betas und der A* Algorithmus.

Für Unterbauten einer gegebenen Struktur

Kombinatorische Suche des Namens wird allgemein für Algorithmen verwendet, die nach einem spezifischen Unterbau einer gegebenen getrennten Struktur, wie ein Graph, eine Schnur, eine begrenzte Gruppe und so weiter suchen. Kombinatorische Optimierung des Begriffes wird normalerweise verwendet, wenn die Absicht ist, einen Unterbau mit einem Maximum (oder Minimum) Wert eines Parameters zu finden. (Da der Unterbau gewöhnlich im Computer durch eine Reihe von Variablen der ganzen Zahl mit Einschränkungen vertreten wird, können diese Probleme als spezielle Fälle der Einschränkungsbefriedigung oder getrennten Optimierung angesehen werden; aber sie werden gewöhnlich formuliert und in einer abstrakteren Einstellung gelöst, wo die innere Darstellung nicht ausführlich erwähnt wird.)

Eine wichtige und umfassend studierte Unterklasse ist die Graph-Algorithmen in besonderen Graph-Traversal-Algorithmen, um spezifische Unterbauten in einem gegebenen Graphen — wie Subgraphen, Pfade, Stromkreise und so weiter zu finden. Beispiele schließen den Algorithmus von Dijkstra, den Algorithmus von Kruskal, den nächsten Nachbaralgorithmus und den Algorithmus von Prim ein.

Eine andere wichtige Unterklasse dieser Kategorie ist die Schnur-Suche-Algorithmen, diese Suche nach Mustern innerhalb von Schnuren. Zwei berühmte Beispiele sind der Boyer-Moore und die Knuth-Morris-Pratt Algorithmen und mehrere auf der Nachsilbe-Baumdatenstruktur gestützte Algorithmen.

Suchen Sie nach dem Maximum einer Funktion

1953 hat J. Kiefer Suche von Fibonacci ausgedacht, die verwendet werden kann, um das Maximum einer unimodalen Funktion zu finden, und viele andere Anwendungen in der Informatik hat.

Für Quant-Computer

Es gibt auch Suchmethoden, die für Quant-Computer wie der Algorithmus von Grover entworfen sind, die theoretisch schneller sind als geradlinig oder Suche der rohen Gewalt sogar ohne die Hilfe von Datenstrukturen oder Heuristik.

Siehe auch

• Suchen Sie rückwärts
• Solver
• Suchen Sie Spiele
• Systeme von Recommender verwenden auch statistische Methoden sich aufzureihen läuft auf sehr große Dateien hinaus
• Das Sortieren von Algorithmen, die notwendig sind, um bestimmte Suchalgorithmen durchzuführen
• Auswahl-Algorithmus
• Kein freies Mittagessen in der Suche und Optimierung
• Suchen Sie Motor, (rechnend)
• Geradliniges Suchproblem
• Schnur-Suche-Algorithmus
• Donald Knuth. Die Kunst der Computerprogrammierung. Band 3: Das Sortieren und die Suche. Internationale Standardbuchnummer 0-201-89685-0.

Links

• Uninformiertes Suchprojekt an Wikiversity.
• Unsortierte Datensuche mit der abgestimmten Datenbank.