Gibt es eine Möglichkeit, unnötige Rekursion zu vermeiden?

Question

Ich habe diese Frage gestellt over at CodeReview, aber ich kam zu der Erkenntnis, dass es nicht so sehr eine Haskell-Frage ist, als es eine Algorithmusfrage ist.

Der Haskell-Code kann on my github repo gefunden werden, aber ich denke, der Code ist nicht so wichtig wie das allgemeine Konzept.

Grundsätzlich ermittelt das Programm die optimale erste Reihe von Zügen in einem Spiel Kalaha (die schwedische Variante). Es wird nur der erste "Zug" betrachtet, also gehen wir davon aus, dass Sie anfangen zu beginnen und dass alles vom Punkt des Gegners, der sich bewegt, nicht berechnet wird.

Kalaha board http://www.graf-web.at/mwm/kalaha.jpg

Die Platte beginnt mit leeren Speicher und einer gleichen Menge von Murmeln in jeden Topf aus.

Sie beginnen Ihren Zug, indem Sie einen nicht leeren Topf auf Ihrer Seite wählen, alle Murmeln aus diesem Topf nehmen und sich dann um das Brett bewegen, indem Sie einen Marmor fallen lassen, wenn Sie einen Topf passieren. Wenn dein letzter Marmor im Laden landet, kommst du noch einmal dran. Wenn Sie in einem nicht leeren, nicht im Laden befindlichen Topf landen, nehmen Sie den gesamten Inhalt dieses Topfes auf und fahren fort. Wenn Sie schließlich in einem leeren Pot landen, wird die Runde an den Gegner weitergegeben.

Bis jetzt habe ich das gelöst, indem ich alle möglichen Wege ausgewählt habe und sie dann nach der Menge an Murmeln sortiert habe, die im Laden am Ende sind. Ein Pfad würde bedeuten, von einem Ihrer Töpfe aus zu starten, alle notwendigen Auf- und Abbewegungen durchzuführen und zu sehen, ob Sie entweder in einem Geschäft oder in einem leeren Topf landen. Wenn Sie im Geschäft landen, können Sie fortfahren, und jetzt gibt es so viele neue Zweige, wie es nicht leere Töpfe auf Ihrer Seite gibt.

Das Problem liegt in der Tatsache, dass, wenn Sie mit fünf Murmeln in den Töpfen beginnen, es schon einige Wege gibt. Sprung bis zu sechs und Ghci hat keinen Speicher mehr.

Der Grund, warum ich nicht herausfinden kann, wie man das billiger macht, ist, weil ich denke, dass jeder Pfad während der Berechnung notwendig ist. Während ich aus den Tausenden (oder Millionen), die generiert werden, nur höchstens drei Pfade (die besten) benötigen, muss der Rest durchlaufen werden, um zu sehen, ob sie tatsächlich besser sind als die vorherigen.
Wenn man länger ist (im Allgemeinen besser), dann ist das gut, aber teuer. Wenn es kürzer als jeder vorherige Pfad ist, musste das Programm diesen Pfad noch berechnen, um das herauszufinden.

Gibt es eine Möglichkeit, oder ist die Berechnung aller Pfade per Definition erforderlich?

Answer 1

Versuchen Sie einfach, sie alle aus um, Ihre Sequenzen von Bewegungen als Folgen von Zahlen 1 bis 6 der Aufnahme (die den Topf, dass Sie die Murmeln von Pick), jedes Mal die gesamte Sequenz von Anfang an Wiedergabe. Behalte und aktualisiere nur die drei Gewinner, plus die allerletzte Reihenfolge der Züge, damit du weißt, was du als nächstes versuchen musst. Wenn es keine nächsten legalen Schritte gibt, gehen Sie eine Stufe zurück.

Es wird vielleicht prohibitiv langsam, aber wird sehr wenig Speicher verwenden. Sie speichern nicht die resultierenden Positionen, sondern nur die Anzahl der ausgewählten Pots und wiederholen die Sequenz jedes Mal von der Startposition aus, indem Sie den allerletzten Zug ändern (statt 2, nächsten Versuch 3, 4 usw.; wenn keine legalen Züge mehr stattfinden) , Backtrack eine Ebene). Oder vielleicht speichern Sie Positionen nur für die allerletzte Sequenz von Moves, die ausprobiert wurden, um das Backtracking zu erleichtern.

Es ist ein typischer Platz für Geschwindigkeit Trade-of dann.

Answer 2

Sie könnten versuchen, diese parallele Version der Karte parallellizing mit:

parMap :: (a -> b) -> [a] -> Eval [b] 
parMap f xs = map f xs `using` parList rseq 

Dann werden Sie einen neuen Thread für jede Wahl in Ihrer Branche auslösen.

Wenn Sie als parMap pathFunction kalahaPots als Ihre Rekursion verwenden, wird es viele Threads funken, aber es könnte schneller sein, Sie könnten es chunk, aber ich bin nicht so gut von einem Parallell Haskeller.