Das bisher betrachtete Problem der acht Damen kann beispielhaft für Anwendungen der einfachen Suchverfahren stehen und zwar einerseits beispielhaft für die in einfachen Beispielen sehr einfache Umsetzung und andererseits für die Probleme mit der Ordnung dieser Verfahren. Es lohnt sich durchaus dies an mehreren Übungsbeispielen zu untersuchen, so dass verständlich wird, dass bei kleinen Lösungsräumen mit diesen einfachen Verfahren Lösungen zu erzielen sind, bei großen Problemen aber selbst bei den hier vorgegebenen Verbesserungen die Probleme nicht grundsätzlich lösbar sind.
Wir sind beim Beispiel des Problems der acht Damen so vorgegangen, dass wir zunächst ganz blind Belegungen für die Werte der Positionen der Damen erzeugt haben und erst bei einer kompletten Belegung geprüft haben, ob diese zulässig ist. Ein solches Vorgehen bezeichnet man als Generate and Test. Man erzeugt (generate) eine Lösung und testet sie erst dann.
Das Abbild des Erzeugungsverfahrens stellt einen Baum dar, bei dem der erste Knoten den Zustand ohne Belegung einer Position darstellt, die Nachfolgenden die Belegung der Position für die erste Dame und das sind schlimmstenfalls eben 64! Zur zweiten Dame gehört nun an jeden Ast wieder eine Verzweigung mit 64 usw.
Nun erkennt man beim Problem der acht Damen recht schnell, wie ineffektiv ein so blindes Verhalten ist. Im Gegenteil: Ich behaupte, niemand wird sich so blind verhalten und statt dessen von vornherein sinnvolle einschränkende Bedingungen (Constraints) beim Erzeugen der nachfolgenden Belegungen einhalten. Man wird keine Position wiederholen, keine Zeile wiederholen usw.
Auf diesem Wege nutzt man das Verfahren des Hierarchisches Generate and Test, bei dem solche Zweige des Baumes nicht weiter verfolgt werden, bei denen schon jetzt erkennbar ist, dass die belegten Werte gegen die -sonst am Schluss geprüften- Bedingungen verstoßen.
Prinzip des Hierarchischen Generate and Test |
---|
Teste alle Belegungen so früh wie möglich auf ihre Zulässigkeit hin, um die Zahl der Äste im Generierungsbaum so klein wie möglich zu halten. |
Beachten Sie aber: Auch diese Strategien nutzen keine zusätzlichen Informationen, sondern nur die Informationen, die im schon erzeugten Teilbaum stecken. Die Suche bleibt daher blind.