vorige nächste Programm

Die Zahl der Möglichkeiten


Berechnen wir einmal die Zahl der möglichen Belegungen, die bei einer vollständigen Suche identisch wäre mit der Zahl der untersuchten Möglichkeiten:

Bei der ersten Damen haben wir 8 × 8 = 64 Möglichkeiten, bei der zweiten wieder usw. Das führt auf die Zahl von 648 Möglichkeiten, das sind etwa 2,8 × 1014 Möglichkeiten. Eine kleine Abschätzung der Rechenzeit erklärt unser Warten auf eine Lösung!

Nun kann man den Ansatz etwas verbessern, wenn man

Man wählt auf dieser Basis eine "verbesserte" Nachfolgerfunktion, die sich leicht formulieren lässt:

;;; ===== Nachfolger ========================================
; Die Nachfolgerfunktion liefert hier einfach alle nachfolgenden Felder im Spielfeld.
; Zum Begriff Suchraum siehe Kommentar.
(define
  (Nachfolger Feld Suchraum)
  (cdr (member Feld Suchraum)))

Zusätzlich muss im Programm an der entsprechenden Stelle der Aufruf dieser Funktion eingebaut werden. In den Zeilen

      ((t-s                                      ; einfache Suche
        Suchraum                                 ; siehe Text
        (cons (car Alternativen) besucht)))

muss statt Suchraum daher eingefügt werden:

  (Nachfolger (car Alternativen) Suchraum)   ; statt Suchraum

Das Ergebnis ist aber immer noch unbefriedigend. Warum das so ist, zeigt die Berechnung aller Möglichkeiten: Es sind 64 über 8, also immer noch 4,4 × 109.

Warum nicht mit Breitensuche ?

Bei dem hier untersuchten Problem ist der Suchhorizont von vorn herein eingeschränkt auf eine Tiefe von 8, es ist sogar zwingend, diese Tiefe auch zu erreichen. Bei einer vollständigen Suche unterscheidet sich bei beiden Verfahren zwar nicht die Zahl der untersuchten Möglichkeiten, die Breitensuche müsste aber wegen der großen Zahl von Verzweigungen eine sehr umfangreiche Datenmenge verwalten. Daher ist die gewählte Tiefensuche mit backtracking angemessener.

Wie kann man dies verbessern ?

Eine wichtige Verbesserung der uninformierten Suchverfahren erhält man, wenn man Heuristiken in die Lösung integriert. Wir haben in diesem Fall einiges an elementarem Wissen über die Art der Lösungen:

Dies führt zu einer naheliegenden Änderung bei der verwendeten Datenstruktur. Wir verwenden nun eine Liste von Spaltenpositionen, in der die Positionen in dieser Liste selbst für die Zeilen stehen. Die Liste

[1    3    5    8    4    7    2    6 ]

hat also denselben Informationsgehalt wie die o.a. Liste

[ (1 . 1)    (2 . 3)    (3 . 5)    (4 . 8)    (5 . 4)    (6 . 7)    (7 . 2)    (8 . 6) ] .

Wenn die Zeilenpositionen sich nicht wiederholen können und sich von 1..8 abzählen lassen, dann brauchen wir sie nicht gesondert zu speichern. Das Testen auf gleiche Spaltenpositionen wird so auch erheblich vereinfacht, member erledigt die Frage.

Wir haben nun eine erste starke Verbesserung im Sinne des hierarchischen Generate and Test erreicht, da jetzt nur noch solche Nachfolger generiert werden, die prinzipiell erfolgversprechend sind, in diesem Fall also solche, die verschiedene Zeilenindizes und verschiedene Spaltenindizes haben.
Dabei ist fast belanglos, ob zunächst auch alle Möglichkeiten von Spaltenindizes erzeugt werden und dann die heraus gefiltert werden, die unzulässig sind, oder ob das schon in der Nachfolgerfunktion gewährleistet wird.
Filtert man nun auch noch die heraus, welche die Diagonalenbedingungen verletzen, dann hat man das vorgegebene Suchverfahren im Sinne des hierarchischen Generate and Test optimiert. Eine Lösung dafür zeigt der folgende Abschnitt aus dem Programm.

Das war’s !