6. Suchen, Spielen und Probleme lösen

Der Fachtext behandelt die Herausforderungen der Suche, des Spielens und des Problemlösens in Inferenzsystemen. Bei fast allen Inferenzsystemen stellt die Suche nach einer Lösung aufgrund der extrem großen Suchbäume ein Problem dar. Der Text führt ein Beispiel mit dem 8-Puzzle ein, bei dem der Suchbaum selbst bei einer Tiefe von 14 abgeschnitten werden muss, um darstellbar zu bleiben. Bei realistischen Problemen können Verzweigungsfaktor und Tiefe der ersten Lösung deutlich größer werden. Der Verzweigungsfaktor von 30 und die erste Lösung in Tiefe 50 führen zu einem Suchbaum mit einer enormen Anzahl von Blattknoten. Der Text zeigt, dass die Suche nach einer Lösung mit den auf der Erde verfügbaren Mitteln nicht möglich ist. Angenommen, der Verzweigungsfaktor ist konstant gleich 30 und die erste Lösung liegt in Tiefe 50, besitzt der Suchbaum Blattknoten. Die Zahl der Inferenzschritte ist dabei noch größer, denn nicht nur jeder Blattknoten, sondern auch jeder innere Knoten des Baumes entspricht einem Inferenzschritt. Der Text diskutiert verschiedene Suchalgorithmen wie Breitensuche, Tiefensuche, Iterative Deepening und heuristische Suche. Besonders hervorgehoben wird der A*-Algorithmus, der vollständig und optimal ist und oft deutlich schneller als uninformierte Suche ist. Der Text endet mit einem Ausblick auf die Zukunft der heuristischen Suche und die Bedeutung von maschinellen Lernverfahren zur Optimierung von Heuristiken.