Zurzeit bereite ich mich auf eine Prüfung vor, in der es unter anderem um Suchverfahren gehen wird. Nachdem ich die verschiedenen Algorithmen gelernt hatte, dachte ich mir, dass es vielleicht interessant wäre, mal einen von ihnen zu kodieren. Und da ich die Programmiersprache Haskell genial finde, aber leider viel zu selten dazu komme sie zu benutzen, habe ich das ganze mit Haskell getan. Das Ergebnis ist ein kleines Programm, welches ein n-Puzzle mithilfe des A*-Algorithmus löst. Als Heuristik benutze ich die Summe aller Manhattan-Abstände der Plättchen zu der Position des jewiligen Plättchens im Zielzustand. Diese Heuristik ist zulässig, das bedeutet sie überschätzt die Restkosten nie. Würde sie das nämlich tun, so könnte es passieren, dass der Algorithmus während des Suchens an der optimalen Lösung vorbeiläuft, da diese scheinbar zu “teuer” ist. Nur wenn die Heuristik zulässig ist, wird auch die optimale Lösung gefunden. In meiner Implementierung sind nur quadratische n-Puzzle erlaubt.
Bei der Auswahl der Start- und Zielzustände ist ein bisschen Vorsicht geboten: Das Programm findet für alle lösbaren Puzzle den kürzesten Weg. Allerdings gibt es Puzzle, die unlösbar sind. Wenn ihr eine Kombination von Start- und Zielzustand wählt, die nicht lösbar ist, so wird das Programm solange laufen, bis es alle möglichen Zustände ausprobiert hat und das kann eine ganze Weile dauern.