Glossar


A

A*-Search: Knoten mit kleinster Summe von aktuellen Kosten und Heuristik (kleinster geschätzter Gesamtweg)
Abstraktion: Vernachlässigung aller für das Problem nicht relevanten Einzelheiten.
Agent: Objekt/Programm, das Ziele formuliert, Lösung sucht und die Lösungssequenz ausführt.
Aktionssequenz: Sequenz von Aktionen, die nacheinander ausgeführt, von einem Zustand zu einem anderen führen.
Arc-Consistency:

B

Backtracking-Search: Bsp: Deep-First
Best-First-Search: Knoten mit geringsten Kosten expandieren, Bsp.: A*- und Greedy-Search
Bidirektional-Search: Es wird gleichzeitig vom Ziel ein Rückweg gesucht.
Blind-Search: -> Uninformed-Search
Breath-First-Search: Es wird zuerst in die Breite gesucht, d.h. Knoten mit geringerer Tiefe werden zuerst expandiert.

C

Close-List: enthält alle schon geöffneten (expandierten) Knoten.
Completeness: Wenn es eine Lösung gibt wird auch eine gefunden, aber nicht unbedingt die beste.
Consistency-Condition: Die Differenz der Heutistik zweier Knoten, ist immer kleiner als ihr wirklicher Abstand.
Constrained-Propagation:
Contingency Problem: Durch Nichtvorhersehbarkeit entsteht statt einer Lösungssequenz ein Lösungsbaum.
CSP: Constraint-Satisfaction-Problem: Problem, bei dem Bedingungen erfüllt werden müssen

Start

D

Deep-First-Search: Es wird zuerst in die Tiefe gegangen, d.h. Knoten mit größerer Tiefe werden zuerst expandiert.
Depth-Limited-Search: In die Tiefe, bis zu einem Maximum
Domain: Wertebereich einer Variablen

E

Epsilon-Addmissible: f+=epsilon
Evaluation-Funktion: Funktion, die angibt, wie wünschenswert es ist einen Knoten zu expandieren.
Expansion: von Knoten: erzeugen der Kind-Knoten der direkt erreichbaren Zustände
Exploration-Problem: Agent weiß nicht wie die Welt funktioniert. Er lernt es durch probieren.

F

Features: Additive Terme einer Evaluation-Funktion, deren Koeefizienten über Lernalgorithmen bestimmt werden können.
Forward-Checking:

Start

G

Greedy-Search: Knoten mit bester Heuristik zuerst expandieren

H

Heuristik: Funktion die eine Abschätzung gibt wie weit ein Zustand vom Ziel ist; mathematisches Abbild menschlicher Intuition
Hill-Climbing: sucht von Random-Position ausgehend lokale Maxima

I

IDA*: -> Iterative-Deepening-A*-Search
Informed Search: Es wird eine Heuristik benutzt um zu entscheiden welchem Kind-Knoten der Vorzug gegeben wird.
Interleaving: Erstellung und Abarbeitung der Lösungssequenz überlappen sich. Bei: -> Contingency Problem
Iterative-Deepening-A*-Search: wie A*, nur mit iterativer Tiefensuche (spart Speicher)
Iterative-Deepening-Search: In die Tiefe, bis zu einem Maximum, das raufgezählt wird
Iterative-Improvements: Ändern der Ausgangskonfiguration um Qualität zu erhöhen

Start

L

Least-Constrained-Value: Prinzip: Wert wird so gewählt, das der Wertebereich möglichst wenig ausgeschöpft wird (Mapcoloring)
Lösung: Aktionssequenz, die vom Ausgangszustand zu einem anderem Zustand führt, der die Zielfunktion erfüllt.

M

Most-Constrained-Variable: Prinzip: Der im Wertebereich eingeschränktesten Variable, wird als nächstes ein Wert zugewiesen (Mapcoloring)
MSP: -> Multiple-State-Problem
Multiple-State-Problem: Zustandsraum ist nicht bekannt. Operationen führen aber zur Lösung.

O

Open-List: enthält alle noch zu öffnenden (expandierenden) Knoten.
Operator: Aktion des Agenten, der von einem Zustand in einen anderen wechselt.
Optimality: Wenn eine Lösung gefunden wird, dann ist es die beste

Start

P

Problem: besteht aus den Zuständen(Start), Operatoren, Zieltestfunktion und Pfadkostenfunktion.

R

Recursive-Best-First-Search:

S

Simplify-Memory-Bounded-A*-Search: Knoten mit hohem f werden zuerst vergessen, Elternknoten merken sich das beste vergessene Kind. Lösung sollte in den Speicher passen.
Simulated-Annealing: Simulierte Abkühlung: wie Hill-Climbing, wobei eine fiktive Temperatur abkühlt, die als Parameter dient wie fehlerhaft die Schritte sind.
Single-State-Problem: Problem, bei dem der Zustandsraum bekannt bzw. definiert ist.
SMA*: -> Simplify-Memory-Bounded-A*-Search
Space-Complexity: Benötigter Speicher
SSP: -> Single-State-Problem
Successor-Funktion: K(Z,n) Gibt den n-ten, vom Zustand Z erreichbaren Knoten zurück.
Suchstrategie: Reihenfolge, in der die Knoten expandiert werden.
Suchstrategie-Arten-uninformed: Breath-First, Uninformed-Cost, Deep-First, Depth-Limited, Iterative-Deepening, Bidirektional
Suchstrategie-Eigenschaften: Completeness, Optimality, Time-Complexity, Space-Complexity

Start

T

Time-Complexity: Zeitlicher Aufwand

U

Uniformed-Cost-Search: In die Breite, Zweige haben Gewichte (Kostenfunktion)
Uninformed-Search: Der Agent weiß nichts über die Lösungseigenschaften, es ist mehr oder weniger Zufall, welchem Kind-Knoten er folgt.

Z

Zustandsraum(State-Space): Alle vom Ausgangszustand erreichbaren Zustaände.

Start