next up previous contents index
Next: Spiele spielen Up: Die künstliche Intelligenz Previous: Die künstliche Intelligenz

   
Suchen und Problemlösen

Unter diesem Punkt werden in der KI Suchprobleme subsumiert. Das sind Probleme, deren Lösung aus einer meist sehr großen Zahl von potentiellen Lösungen bestimmt werden muß. Als Beispiel sei das 15-Puzzle genannt, bei dem in einem 4x4 Felderquadrat 15 durchnumerierte oder durchbuchstabierte verschiebbare Plättchen angeordnet sind. Siehe hierzu Abbildung 2.1.
  
Abbildung 2.1: Das 15-Puzzle. Ein Standardbeispiel für ein schwieriges Suchproblem der künstlichen Intelligenz.
\begin{figure}\centerline{\psfig{figure=figures/15-Puzzle.ps,height=4cm}}
\end{figure}

Ein Plättchen kann nur in das (einzige) leere Feld des 4x4 Quadrats entweder vertikal oder horizontal verschoben werden. Aus einer beliebigen Anfangsanordnung der Plättchen ist durch geeignetes Verschieben der Plättchen in das jeweils leere Feld eine vorgegebene Plättchenanordnung zu erzielen (z.B. in alphabetischer Reihenfolge geordnet). Bei einem solchen Problem gibt es allein mehr als 10 000 000 000 000 verschiedene Anordnungen der Plättchen. Daraus resultieren noch wesentlich mehr verschiedene Möglichkeiten, Plättchen aus einer gegebenen Anfangssituation heraus zu verschieben. Die Aufgabe nun, für eine Anfangssituation eine Verschiebestrategie zu bestimmen, die durch möglichst wenig Verschiebungen die vorgegebene Zielkonstellation erzeugt, erfordert - von einem Menschen durchgeführt - sicherlich Intelligenz.

Aber auch für heutige Computer ist die Zahl der verschiedenen Schiebestrategien viel zu groß, um sie alle nacheinander zu prüfen und festzustellen, ob es sich jeweils um eine mögliche Lösung handelt. Solche als kombinatorische Probleme bezeichneten Aufgaben tauchen in vielerlei Gestalt auf. Beispielsweise tritt ein solches kombinatorisches Problem auch bei dem automatischen Beweisen von mathematischen Sätzen auf. Hier ist die Frage zu lösen, welche logischen Ableitungsregeln in welcher Reihenfolge auf welche Formeln angewendet werden müssen, um überhaupt eine - oder besser noch eine einigermaßen kurze - Ableitungskette zu erhalten.

Obwohl ein Computer sicherlich wesentlich schneller verschiedene Ableitungsmöglichkeiten bzw. Verschiebungsmöglichkeiten bei dem 15-Puzzle untersuchen kann, ist die menschliche Intelligenz dem Computer auf sehr vielen Gebieten - zumindest bis heute noch - weit überlegen. Der Grund hierfür ist darin zu sehen, daß die menschliche Intelligenz nicht primär die verschiedenen Möglichkeiten `blind' durchspielt, sondern vielmehr von vornherein eher `strategisch geeignete' Entscheidungen trifft, in welcher Richtung die Suche nach einer Lösung unter den vielen potentiellen Lösungen fortgesetzt werden soll. Dieses selektive Suchen nach einer Lösung, wodurch bei weitem nicht mehr alle Möglichkeiten, sondern nur noch ein kleiner Bruchteil durchgespielt werden muß, versucht man auch auf Computer zu übertragen. Nichtsdestotrotz ist dies, wie oben erwähnt, bislang nicht in ausreichendem Maße gelungen. Dies ist ein Punkt, an dem Kritiker der KI wie Dreyfus einhaken und argumentieren, daß Computer nie in der Lage sein werden, eine letztlich so effektive Lösungssuche durchzuführen, wie es von Menschen getan wird.


next up previous contents index
Next: Spiele spielen Up: Die künstliche Intelligenz Previous: Die künstliche Intelligenz
Achim Hoffmann
2002-07-12