Problemlösen durch heuristische Suche in der Artificial Intelligence

ISBN-13: 9783211820797 / Niemiecki / Miękka / 1988 / 231 str.

Hermann Kaindl

Opis

Die Zielsetzung der Artificial Intelligence (AI) ist es, Maschinen, zu erzeugen, die "intelligentes" Verhalten zeigen. Dabei spielt in vielerlei Hinsicht das Problemlosen eine zentrale Rolle. Die in diesem Buch behandelten Ansatze basieren auf heuristischer Suche. Das Buch bietet eine umfassende Behandlung des "State-of-the-art" dieses Teilbereichs der AI und zeigt fundamentale Zusammenhange verschiedenster Problemstellungen und ihrer Losungen auf. Bei der Darstellung steht die intuitive Vermittlung von Ideen im Vordergrund (unterstutzt durch leicht verstandliche Beispiele). Wo es die Thematik erfordert, kommt jedoch auch mathematische Notation zum Einsatz, und es werden exakte Beweise angegeben. Die derzeit bekannten Such-Verfahren werden hier in einem einheitlichen Formalismus prasentiert, um eine Gegenuberstellung zu ermoglichen. Die Begriffswelt dieses Teilbereiches der AI wird unter Zuhilfenahme von (grossteils informalen) Definitionen umfassend erlautert, um eine klare Darstellung der Materie zu erreichen. Ausserdem soll dem Leser dieses Buches ein guter Einstieg in die einschlagigge (grosstenteils englischsprachige) Fachliteratur ermoglicht werden."

Spis treści

1 Problemdarstellung.- 1.1 Produktionssysteme.- 1.1.1 Beispiele für Produktionssysteme.- 1.1.2 „Constraint Satisfaction“ Probleme.- 1.1.3 Produktionssysteme „im engeren Sinn“.- 1.1.4 Kommutative Produktionssysteme.- 1.2 Graphen.- 1.2.1 Begriffliche Übersicht.- 1.2.2 Darstellung des Vorgehens eines Produktionssystems.- 1.3 Zerlegbare Produktionssysteme.- 1.3.1 UND/ODER-Graphen.- 1.3.2 Spielbäume.- 1.4 Beziehungen zwischen verschiedenen Begriffen und Formalismen.- 1.4.1 Richtung des Vorgehens.- 1.4.2 Beziehungen zwischen kommutativen und zerlegbaren Produktionssystemen.- 1.4.3 Begriffliche Zusammenhänge.- 2 Problemlösen mittels Suche.- 2.1 Allgemeines.- 2.1.1 Ein allgemeines Schema für Such-Verfahren.- 2.1.2 Ein Graph-Such-Verfahren.- 2.1.3 Suche in UND/ODER-Graphen.- 2.2 „Irrevocable Control“.- 2.2.1 Kommutativität.- 2.2.2 „Hill-Climbing“.- 2.3 „Breadth-First Search“.- 2.3.1 Vorgangsweise.- 2.3.2 Komplexität.- 2.3.3 „Uniform-Cost Search“.- 2.4 „Depth-First Search“.- 2.4.1 Vorgangsweise.- 2.4.2 „Backtracking“.- 2.4.3 Komplexität.- 2.5 „Best-First Search“.- 2.5.1 Bewertungsfunktion von A*.- 2.5.2 Die heuristische Komponente: Ermittlung und Anwendung.- 2.5.3 Zulässigkeit.- 2.5.4 Geometrische Darstellung.- 2.5.5 Gewichtete Bewertungsfunktionen.- 2.5.6 Vergleich von Bewertungsfunktionen für A*.- 2.5.7 Konsistente (monotone) heuristische Funktionen.- 2.5.8 Konsistenz und vereinfachte Modelle.- 2.5.9 Nicht-konsistente Funktionen und Modifikationen von A*.- 2.5.10 Komplexität von A*.- 2.5.11 Bewertungsfunktionen ohne Garantie für optimale Lösungen.- 2.5.12 Allgemeine Funktionen für Kosten und Bewertungen.- 2.5.13 Ist A* optimal?.- 2.5.14 „Best-First Search“ in UND/ODER-Graphen.- 2.6 „Depth-First Iterative-Deepening“.- 2.6.1 DFID.- 2.6.2 IDA*.- 2.6.3 PIDA* — Eine parallele Version von IDA*.- 2.7 „Bidirectional Search“.- 2.7.1 „Blinde“ Suche in beide Richtungen.- 2.7.2 Suche in beide Richtungen mit Heuristik.- 2.8 „Conflict Resolution“.- 3 Begrenzte Suche zum Fällen von Entscheidungen.- 3.1 Allgemeines.- 3.1.1 Entscheidungen bei Problemen.- 3.1.2 Lösen von Spielbäumen.- 3.1.3 Bewerten von Spielbäumen.- 3.1.4 „Minimaxing“.- 3.1.5 Modifikationen und Alternativen bezüglich „Minimaxing“.- 3.2 „Depth-First Search“.- 3.2.1 Suche zur Berechnung des Minimax-Werts.- 3.2.2 Das ?-?-Verfahren.- 3.2.3 Die Verwendung eines „Fensters“.- 3.2.4 PAB und SCOUT.- 3.3 „Depth-First Iterative-Deepening“.- 3.4 „Best-First Search“.- 3.4.1 SSS* und DUAL*.- 3.4.2 B* und PB*.- 3.5 Die Effizienz der Minimax-Verfahren im Vergleich.- 3.5.1 Ungünstigste und günstigste Bedingungen.- 3.5.2 Der „durchschnittliche“ Fall.- 3.6 Zusätzliche Aspekte und Heuristika.- 3.6.1 Erreichen einer „guten“ Anordnung der Nachfolger.- 3.6.2 Statische Bewertungsfunktionen.- 3.6.3 „Quiescence“ und der Horizont-Effekt.- 3.6.4 Variable Such-Tiefe.- 3.7 Die Qualität der Entscheidungen.- Epilog.- Literatur.- Notation.