Psychologie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

Autor/Titel Begriff Zusammenfassung Metadaten

Peter Norvig über Probleme – Lexikon der Argumente

Norvig I 108
Probleme/Künstliche Intelligenz/Russell/Norvig: Ein Problem besteht aus fünf Teilen: dem Ausgangszustand, einem Satz von Handlungen, einem Übergangsmodell, das die Ergebnisse dieser Handlungen beschreibt, einer Zieltestfunktion und einer Pfadkostenfunktion. Die Umgebung des Problems wird durch einen Zustandsraum repräsentiert. Ein Pfad durch den Zustandsraum vom Ausgangszustand zu einem Zielzustand ist eine Lösung. >Belief-state.
Norvig I 222
(...) der einzige Weg, wie wir mit der realen Welt umgehen können, ist, sie in viele [unabhängige] Teilprobleme zu zerlegen. (>Constraint-Satisfaction-Probleme/CSP/Norvig.)
Unabhängigkeit: Unabhängigkeit: Die Unabhängigkeit kann einfach ermittelt werden, indem man die verbundenen Komponenten des Constraint-Graphen findet. Jede Komponente entspricht einem Teilproblem CSPi. Wenn die Zuordnung Si eine Lösung von CSPi ist, dann ist Ui Si eine Lösung von Ui CSPi. Warum ist das wichtig? Betrachten Sie Folgendes: Angenommen, jeder CSPi hat c Variablen aus der Gesamtsumme von n Variablen, wobei c eine Konstante ist. Dann gibt es n/c Teilprobleme, von denen jedes höchstens dc Arbeit erfordert, um sie zu lösen,
Norvig I 223
wobei d die Größe der Domäne ist. Daher ist die Gesamtarbeit O(dcn/c), die in n linear ist; ohne die Zerlegung ist die Gesamtarbeit O(dn), welche in n exponentiell ist. Machen wir es konkreter: Die Aufteilung eines Booleschen CSP mit 80 Variablen in vier Teilprobleme reduziert die schlechtmöglichste Lösungszeit von der Lebensdauer des Universums auf weniger als eine Sekunde. Völlig unabhängige Teilprobleme sind dann köstlich, aber selten. Glücklicherweise sind auch einige andere Diagrammstrukturen leicht zu lösen. Beispielsweise ist ein Constraint-Graph ein Baum, wenn zwei beliebige Variablen durch nur einen Pfad verbunden sind.


_____________
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

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

Send Link
> Gegenargumente gegen Norvig

Autoren A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   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