Philosophie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

 
Suchalgorithmen: Ein Suchalgorithmus ist ein schrittweises Verfahren zum Auffinden einer bestimmten Information in einer Datenmenge. Arten der Suche sind die lineare Suche, die binäre Suche und Hash-Tabellen. Suchalgorithmen werden normalerweise geheim gehalten, da sie sonst zu leicht manipuliert werden können. Siehe auch Suchmaschinen, Internet, Google, Soziale Medien, Fehlinformationen.

_____________
Anmerkung: Die obigen Begriffscharakterisierungen verstehen sich weder als Definitionen noch als erschöpfende Problemdarstellungen. Sie sollen lediglich den Zugang zu den unten angefügten Quellen erleichtern. - Lexikon der Argumente.

 
Autor Begriff Zusammenfassung/Zitate Quellen

Peter Norvig über Suchalgorithmen – Lexikon der Argumente

Norvig I 64
Suchalgorithmen/Russell/Norvig: Uninformierte Suchalgorithmen [sind] Algorithmen, die außer seiner Definition keine Informationen über das Problem erhalten. Obwohl einige dieser Algorithmen jedes lösbare Problem lösen können, kann keiner von ihnen dies effizient tun.
Informierte Suchalgorithmen hingegen können, wenn sie etwas Anleitung erhalten, wo nach Lösungen zu suchen ist, recht gut abschneiden.
A. Uninformierte Suche.
Norvig I 81
Die Breitensuche (breadth-first search) ist eine einfache Strategie, bei der zuerst der Wurzelknoten expandiert wird, dann werden alle Nachfolger des Wurzelknotens als nächstes expandiert, dann ihre Nachfolger usw. Im Allgemeinen werden alle Knoten in einer bestimmten Tiefe im Suchbaum expandiert, bevor alle Knoten der nächsten Ebene expandiert werden.
Norvig I 83
Der Speicherbedarf ist für die Breitensuche ein größeres Problem als die Ausführungszeit.
(...) Suchprobleme mit exponentieller Komplexität können mit uninformierten Methoden für keine außer den kleinsten Instanzen gelöst werden.
Norvig I 85
Die Tiefensuche (depth-first search) erweitert immer den tiefsten Knoten innerhalb der aktuellen Grenze des Suchbaums. Beide Versionen sind nicht optimal.
Norvig I 87
Backtracking-Suche: Benötigt weniger Speicherplatz. (...) Es wird jeweils nur ein Nachfolger und nicht alle Nachfolger zeitgleich generiert; jeder teilweise expandierte Knoten merkt sich, welcher Nachfolger als nächstes generiert werden soll. Auf diese Weise wird nur O(m) Speicherplatz und nicht O(bm) benötigt (wobei m die maximale Knotentiefe ist). Die Backtracking-Suche ermöglicht einen weiteren speichersparenden (und zeitsparenden) Trick: die Idee, einen Nachfolger zu generieren, indem man die aktuelle Zustandsbeschreibung direkt ändert, anstatt sie zuerst zu kopieren. Dies reduziert den Speicherbedarf auf nur eine Zustandsbeschreibung und O(m) Handlungen. Damit dies funktioniert, müssen wir in der Lage sein, jede Änderung rückgängig zu machen, wenn wir zurückkehren, um den nächsten Nachfolger zu generieren.
B. Informierte (heuristische) Suche.
Norvig I 92
Die Bestensuche (best-first search) ist eine Instanz des allgemeinen Baum- oder Graphen-Suchalgorithmus, bei dem ein Knoten basierend auf einer Auswertungsfunktion, f(n), zur Expansion ausgewählt wird. Die Evaluierungsfunktion wird als Kostenschätzung ausgelegt, sodass zunächst der Knoten mit der niedrigsten Bewertung erweitert wird.
Gierige Bestensuche (greedy best-first search) versucht, den dem Ziel am nächsten liegenden Knoten zu erweitern, mit der Begründung, dass dies wahrscheinlich schnell zu einer Lösung führen wird. So bewertet sie Knoten, indem sie nur die heuristische Funktion verwendet, d.h. f(n) = h(n).
Norvig I 108
Ein allgemeiner Baum-Suchalgorithmus berücksichtigt alle möglichen Pfade, um eine Lösung zu finden, während ein Grafik-Suchalgorithmus die Berücksichtigung redundanter Pfade vermeidet.
Norvig I 120
Onlinesuche: Hier steht der Agent vor einem Zustandsraum, der zunächst unbekannt ist und erforscht werden muss.
Norvig I 121
Lokale Suchalgorithmen: Wenn der Pfad zum Ziel egal ist, könnten wir eine andere Klasse von Algorithmen in Betracht ziehen, nämlich diejenigen, die sich überhaupt keine Sorgen um Pfade machen. Lokale Suchalgorithmen arbeiten mit einem einzigen aktuellen Knoten (und nicht mit mehreren Pfaden) und bewegen sich im Allgemeinen nur zu den Nachbarn dieses Knotens. Diese Algorithmen haben zwei wesentliche Vorteile: (1) sie verbrauchen sehr wenig Speicherplatz - meist eine konstante Menge; und (2) sie können oft vernünftige Lösungen in großen oder unendlichen (kontinuierlichen) Zustandsräumen finden, für die systematische Algorithmen ungeeignet sind.((s) Für Probleme: vgl. >Lokales Minimum
(lokales Maximum; für eine Lösung: >Simulated annealing).
Norvig I 125
Lokale Strahlensuche (beam search): (Die Strahlensuche ist ein pfadbasierter Algorithmus). Der lokale Strahlensuchalgorithmus verfolgt eher k Zustände als
Norvig I 126
nur einen. Es beginnt mit k zufällig generierten Zuständen. Bei jedem Schritt werden alle Nachfolger aller k Zustände erzeugt. Wenn einer davon ein Ziel ist, stoppt der Algorithmus. Andernfalls wählt es die k besten Nachfolger aus der Gesamtliste aus und wiederholt den Vorgang.
Und-Oder-Suchproblem: siehe >Terminologie/Norvig.
>Genetische Algorithmen.
Norvig I 147
Onlinesuche:
>Onlinesuche/Norvig.
Norvig I 154
Literatur für lokale Suche (local search): (Newton, 1671(1); Raphson, 1690(2)) kann als eine sehr effiziente Methode der lokalen Suche für kontinuierliche Räume angesehen werden, in denen Gradienteninformationen verfügbar sind. Brent (1973)(3) ist eine klassische Referenz für Optimierungsalgorithmen, die solche Informationen nicht benötigen.
Die Strahlensuche, die wir als Algorithmus der lokalen Suche vorgestellt haben, entstand als eine Variante der dynamischen Programmierung zur Spracherkennung im HARPY-System (Lowerre, 1976)(4). Ein verwandter Algorithmus wird von Pearl (1984(5), Kap. 5) eingehend analysiert.
Das Thema der lokalen Suche wurde Anfang der 90er Jahre durch überraschend gute Ergebnisse bei großen Constraint-Satisfaction-Problemen wie n-queens (Minton et al., 1992)(6) und logischem Denken (Selman et al., 1992)(7) und durch die Einbeziehung von Zufälligkeit, mehreren gleichzeitigen Suchen und anderen Verbesserungen neu belebt.
Tabu-Suche: Eine Variante des Bergsteigens (hill climbing) namens Tabu-Suche hat an Popularität zugenommen (Glover und Laguna, 1997)(8). Dieser Algorithmus führt eine Tabuliste mit k zuvor besuchten Zuständen, die nicht erneut besucht werden können; diese Liste verbessert nicht nur die Effizienz bei der Suche nach Graphen, sondern kann es dem Algorithmus auch ermöglichen, aus einigen lokalen Minima zu entkommen.
Stufenalgorithmus: Eine weitere nützliche Verbesserung beim Bergsteigen ist der Stufenalgorithmus (Boyan und Moore, 1998)(9). Die Idee ist, die lokalen Maxima des zufälligen wiedergestarteten Bergsteigens zu nutzen, um eine Vorstellung von der Gesamtform der Landschaft zu bekommen. >Constraint-Satisfaction-Probleme/Norvig.
Norvig I 227
Constraint-Satisfaction-Probleme (CSPs) stellen einen Zustand mit einem Satz von Variablen/Wertpaaren dar und stellen die Bedingungen für eine Lösung durch einen Satz von Beschränkungen (constraints) für die Variablen dar. Viele wichtige Probleme aus der realen Welt können als CSPs bezeichnet werden.
Eine Reihe von Inferenztechniken nutzt die Einschränkungen, um daraus abzuleiten, welche Variablen/Wertpaare konsistent sind und welche nicht. Dazu gehören Knoten, Kante, Pfad und k-Konsistenz.
Die Backtracking-Suche, eine Form der Tiefensuche, wird häufig zur Lösung von CSPs eingesetzt.
Inferenz kann mit der Suche verwoben werden.
Die minimum-remaining-values und degree heuristics sind domänenunabhängige Methoden, um zu entscheiden, welche Variable als nächstes in einer Backtracking-Suche ausgewählt werden soll. Die Heuristik mit dem geringsten Restriktionswert hilft bei der Entscheidung, welchen Wert man zuerst für eine gegebene Variable ausprobieren soll. Backtracking tritt auf, wenn für eine Variable keine rechtliche Zuordnung gefunden werden kann. Konfliktgesteuertes backjumping führt direkt zur Ursache des Problems zurück.
Lokale Suche, welche die Heuristik der Min-Konflikte nutzt, wurde auch mit großem Erfolg auf Constraint-Satisfaction-Probleme angewendet.
Für Vorwärtsverkettung, Rückwärtsverkettung: siehe >Agenten/Norvig.



1. Newton, I. (1664–1671). Methodus fluxionum et serierum infinitarum. Unpublished notes
2. Raphson, J. (1690). Analysis aequationum universalis. Apud Abelem Swalle, London.
3. Brent, R. P. (1973). Algorithms for minimization without derivatives. Prentice-Hall
4. Lowerre, B. T. (1976). The HARPY Speech Recognition System. Ph.D. thesis, Computer Science Department, Carnegie-Mellon University.
5. Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-
Wesley.
6. Minton, S., Johnston, M. D., Philips, A. B., and Laird, P. (1992). Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. AIJ, 58(1–3), 161–205.
7. Selman, B., Levesque, H. J., and Mitchell, D. (1992). A new method for solving hard satisfiability problems. In AAAI-92, pp. 440–446.
8. Glover, F. and Laguna, M. (Eds.). (1997). Tabu search. Kluwer
9. Boyan, J. A. and Moore, A. W. (1998). Learning evaluation functions for global optimization and Boolean satisfiability. In AAAI-98

_____________
Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders. Übersetzungen: Lexikon der Argumente
Der Hinweis [Begriff/Autor], [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] bzw. "Problem:"/"Lösung", "alt:"/"neu:" und "These:" ist eine Hinzufügung des Lexikons der Argumente.

Norvig I
Peter Norvig
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010

Send Link

Autoren A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Y   Z  


Begriffe A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z