lösungsraum

Lösungsraum ist ein Fachbegriff, der in Mathematik, Informatik und verwandten Disziplinen verwendet wird. Er bezeichnet die Menge aller Lösungen eines Problems, also aller Werte oder Belegungen, die die gegebenen Randbedingungen erfüllen. Der Lösungsraum unterscheidet sich von Eingabedaten und von der Aufgabenformulierung, da er die tatsächliche Menge möglicher Lösungen umfasst.

Etwas technischer: Bei linearen Gleichungssystemen ist der Lösungsraum die Menge aller x, die Ax = b erfüllen. Ist das System konsistent, entsteht eine affine Unterraum von R^n; seine Dimension entspricht der Anzahl frei wählbarer Parameter und lässt sich durch Basispunkte und Richtungsvektoren beschreiben. Ist das System inkonsistent, ist der Lösungsraum leer.

Beispiele: In der linearen Algebra beschreibt der Lösungsraum alle Lösungen eines Gleichungssystems. In der Informatik, etwa bei SAT- oder CSP-Problemen, entspricht der Lösungsraum der Menge aller Belegungen, die die Bedingungen erfüllen. In der Optimierung ist der Lösungsraum der zulässige Bereich, innerhalb dessen man den Zielwert minimiert oder maximiert.

Zur Erkundung des Lösungsraums werden verschiedene Verfahren eingesetzt: vollständige Enumeration wird bei großen Problemen meist unpraktisch; stattdessen nutzen man Constraint Propagation, Branch-and-Bound, Relaxationen und heuristische Suchstrategien. Für kontinuierliche Probleme liefert oft die Konvexität Vorteile: bei konvexen zulässigen Bereichen lassen sich Optimallösungen effizient finden, besonders bei linearen oder quadratischen Programmen.

Der Begriff unterstreicht die Struktur des Problems; ein gut definierter Lösungsraum erleichtert Analyse, Abschätzung der Komplexität und Wahl geeigneter Lösungsstrategien.