In der Informatik und künstlichen Intelligenz studiert kombinatorische Suche Suchalgorithmen, um Beispiele von Problemen zu lösen, die, wie man glaubt, im Allgemeinen, durch das effiziente Erforschen des gewöhnlich großen Lösungsraums dieser Beispiele hart sind. Kombinatorische Suchalgorithmen erreichen diese Leistungsfähigkeit durch das Reduzieren der wirksamen Größe des Suchraums oder die Beschäftigung der Heuristik. Wie man versichert, finden einige Algorithmen die optimale Lösung, während andere nur die beste Lösung zurückgeben können, die im Teil des Zustandraums gefunden ist, der erforscht wurde.

Klassische kombinatorische Suchprobleme schließen das Lösen des acht Königin-Rätsels oder Auswerten von Bewegungen in Spielen mit einem großen Spielbaum, wie reversi oder Schach ein.

Eine Studie der rechenbetonten Kompliziertheitstheorie hilft, kombinatorische Suche zu motivieren. Kombinatorische Suchalgorithmen sind normalerweise mit Problemen beschäftigt, die NP-hard sind. Wie man glaubt, sind solche Probleme im Allgemeinen nicht effizient lösbar. Jedoch weisen die verschiedenen Annäherungen der Kompliziertheitstheorie darauf hin, dass einige Beispiele (z.B "kleine" Beispiele) dieser Probleme effizient gelöst werden konnten. Das ist tatsächlich der Fall, und solche Beispiele haben häufig wichtige praktische Implikationen.

Kombinatorische Suchalgorithmen werden normalerweise auf einer effizienten befehlenden Programmiersprache, auf einer ausdrucksvollen Aussageprogrammiersprache wie Einleitung oder etwas Kompromiss, vielleicht eine funktionelle Programmiersprache wie Haskell oder eine Mehrparadigma-Sprache wie LISPELN durchgeführt.

Beispiele

Allgemeine Algorithmen, um kombinatorische Suchprobleme zu beheben, schließen ein:

• A* Suchalgorithmus
• Alpha-Beta, das beschneidet
• Branch-bound
• Minimax

Lookahead

Lookahead ist ein wichtiger Bestandteil der kombinatorischen Suche, die grob angibt, wie tief der Graph, der das Problem vertritt, erforscht wird. Das Bedürfnis nach einer spezifischen Grenze auf lookahead kommt aus den großen Problem-Graphen in vielen Anwendungen, wie Computerschach und Computer Gehen. Eine naive Breitensuche dieser Graphen würde das ganze Gedächtnis jedes modernen Computers schnell verbrauchen. Durch das Festlegen einer spezifischen lookahead Grenze kann die Zeit des Algorithmus sorgfältig kontrolliert werden; seine Zeit nimmt exponential als die Lookahead-Grenze-Zunahmen zu.

Hoch entwickeltere Suchtechniken wie Beschneidung des Alpha-Betas sind im Stande, komplette Subbäume des Suchbaums von der Rücksicht zu beseitigen. Wenn diese Techniken verwendet werden, ist lookahead nicht eine genau definierte Menge, aber stattdessen entweder die maximale Tiefe gesucht oder ein Typ des Durchschnitts.

Siehe auch

• Suche der rohen Gewalt
• Kombinatorische Explosion
• Kombinatorische Optimierung
• Suchen Sie Algorithmus
• Staatsraum sucht
• Russell und Norvig. Künstliche Intelligenz: Eine moderne Annäherung.