Backtracking

Eine der Stärken von Scala ist, dass man recht einfach Algorithmen auf sehr abstraktem Niveau definieren kann. Nehmen wir zum Beispiel allgemeines Backtracking, eine beliebte Strategie zur Lösungssuche. Fast 1:1 aus Wikipedia übernommen ist dieses trait, das das Problem und seinen Lösungsbaum beschreibt:

trait Backtrackable[S] {
    def root:S  //die Teillösung, mit der gestartet werden soll
    def reject(s:S):Boolean //Ist diese Teilösung ungültig?
    def accept(s:S):Boolean //Ist das eine gültige (fertige) Lösung?
    def first(s:S):Option[S] //Gib mir das erste "Kind" der Teillösung
    def sibling(s:S):Option[S] //Gib mir die nächste "parallele" Teillösung
}

Die Methoden root, first und sibling dienen dazu, den zu untersuchenden „Lösungsbaum“ zu definieren: root ist der Startpunkt, first geht eine „Ebene“ tiefer und sibling geht dann alle weiteren Teillösungen „neben“ der ersten durch. reject und accept regeln den „Verkehr“ in diesem Lösungsbaum: Wo ist gesperrt, wann haben wir eine gültige Lösung gefunden.

Nun kann man – ganz abstrakt – dafür einen „Löser“ schreiben. Die geeignete Datenstrukturen sind hier aber keine Listen (bei denen man ja unbedingt alles berechnen muss), sondern Streams, von denen ich im letzten Post geschrieben habe: Der Kopf steht sofort zur Verfügung, der Rest ist wieder ein Stream, der aber erst ausgerechnet wird, wenn er wirklich gebraucht wird. Wir produzieren sozusagen „just in time“.

Die Verwendung der apply-Methode ist übrigens ein wenig syntaktischer Zucker, denn statt foo.apply(bar) darf man einfach schreiben foo(bar). Ansonsten verhält sie sich wie eine normale Methode.

object Backtracker {
    def apply[S](bt:Backtrackable[S]):Stream[S] = {
        def getStream(path:List[S]):Stream[S] = path match {
            case head :: _ =>
                def backtrack(path:List[S]):List[S] = path match {
                    case head :: tail => bt.sibling(head) match {
                            case None => backtrack(tail)
                            case Some(sib) => sib :: tail
                        }
                    case Nil => Nil
                }

                val rejected = bt.reject(head)
                if(!rejected && bt.accept(head)) {
                    Stream.cons(head, getStream(backtrack(path)))
                } else getStream {
                    if (rejected) {
                        backtrack(path)
                    } else bt.first(head) match {
                        case None => backtrack(path)
                        case Some(f) =>  f :: path
                    }
                }
            case Nil => Stream.empty
        }
        getStream(List(bt.root))
    }
}

Keine Angst, das muss man nicht unbedingt verstehen. Am Ende kommt ein Stream raus, und der liefert auf Nachfrage Ergebnis für Ergebnis – und das ist alles, was man wissen muss. Trotzdem ein kleiner Erklärungsversuch: apply ruft getStream mit der Anfangslösung auf. path ist dabei Pfad vom aktuellen „Lösungsbaumknoten“ bis zur Wurzel. Wenn der pfad leer ist, gibt es keine weiteren Lösungen. Ansonsten schauen wir, ob unsere aktuelle Lösung (der Knoten, wo wir gerade sind) zurückgewiesen wird. Dann gehen wir wieder zurück (mit backtrack) und suchen andere Lösungen. Ist unsere Teillösung gültig, schauen wir, ob es eine fertige Lösung ist. Wenn ja, packen wir diese Lösung in einen Stream, dessen Rest ein Stream ist, der schon die nächste Lösung sucht (mit backtrack). Wenn nein, schauen wir, ob wir mit first tiefer in den Baum hineinsteigen können, ansonsten backtracken wir auch hier. Am besten malt man sich das ganze Verfahren einmal auf, denn eigentlich ist es nicht so kompliziert, wie es klingen mag …

Probieren wir dieses seltsame Gerät einmal am allseits beliebten Acht-Damen-Problem aus. Unsere Lösung ist dabei eine Liste von Zahlen, die die Positionen der Damen in den einzelnen Reihen angeben:

object Queens extends Backtrackable[List[Int]] {
    def root:List[Int] = List()
    def reject(list:List[Int]):Boolean = list match {
        case Nil => false
        case head :: tail => tail.zip(tail.indices).exists{
                case (pos, index) => pos == head ||
                    Math.abs(pos - head) == index + 1 }
    }
    def accept(list:List[Int]):Boolean = list.length == 8
    def first(list:List[Int]):Option[List[Int]] = Some(1 :: list)
    def sibling(list:List[Int]):Option[List[Int]] = list match {
        case head :: tail if head < 8 => Some((head + 1) :: tail)
        case _ => None
    }
}

//und starten
Backtracker(Queens).foreach(println)

Als Ausgabe bekommen wir alle 92 Lösungen:

List(4, 2, 7, 3, 6, 8, 5, 1)
List(5, 2, 4, 7, 3, 8, 6, 1)
List(3, 5, 2, 8, 6, 4, 7, 1)
List(3, 6, 4, 2, 8, 5, 7, 1)
usw…

Natürlich hätten wir auch vorher abbrechen können, nach bestimmten Kriterien filtern oder ähnliches. Gerade bei Backtracking ist es wichtig, dass man nicht einfach stur alle Lösungen ausrechnet, was sehr lange dauern kann, sondern dem Nutzer die Freiheit gibt, einzugreifen. Die Klasse Stream besitzt durch ihre „Faulheit“ (siehe z.B. lazy evaluation) die dazu nötige Flexibilität.

Wer zuviel Zeit hat, kann ja mal versuchen, das hier in Java nachzubasteln, aber mich graust es schon, wenn ich nur daran denke…