Repräsentation des Suchraums
Inhaltsverzeichnis
Repräsentation des Suchraum
Im Allgemeinen werden 2 Arten von Suchräumen unterschieden, der Lösungsraum und der Problemraum
Lösungsraum
Ein Lösungsraum bezeichnet die Gesamtheit aller Problemlösungen, d.h. es ist eine Menge die alle möglichen Lösungen für ein Problem enthält. Um in einer solchen Menge zu suchen wird auf eine bereits gefundene Lösung eine Transition ausgeführt welche die bereits bekannte Lösung in eine noch unbekannt aber benachbarten Lösung im Lösungsraum überführt. Um zu bestimmen ob eine Lösung besser ist als die vorhergehende wird mit Hilfe einer Zielfunktion f eine Rangfolge über die Lösungen erstellt um damit die beste Lösung zu finden.
Um einen solchen Lösungsraum darzustellen greift man auf die Graphentheorie zurück. Hierbei werden dann die Lösungen als Knoten repräsentiert und die Transitionen als Kanten.
Beispiel
Für ein Travelling Salesman Problem mit 5 Zielen könnte der Lösungsraum folgendermaßen aussehen.
Problemraum
Für die Suche in einem Problemraum wird ein Problem in kleinere (Unter-)Probleme zerlegt, bis diese einfach zu lösen sind.
Um einen solchen Problemraum darzustellen wird er als Baum dargestellt. Die Wurzel des Baumes ist hierbei das Anfangsproblem, die inneren Konten repräsentieren die einfacheren Unterprobleme und die Blätter. Die Kanten repräsentieren die Zerlegung der Probleme.
Beispiel
Für ein Travelling Salesman Problem mit 5 Zielen könnte der Problemraum folgendermaßen aussehen.
