algorithm - 有没有办法避免不必要的递归？

Question

我发布了这个问题 over at CodeReview ，但我开始意识到，与其说这是一个 Haskell 问题，不如说它是一个算法问题。

可以找到Haskell代码on my github repo但我认为代码不如一般概念重要。

基本上，该程序计算出 Kalaha 游戏(瑞典变体)中的最佳第一组 Action 。仅考虑第一个“回合”，因此我们假设您开始了，并且不计算从对手移动开始的任何事情。

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

棋盘从空商店开始，每个锅中有等量的弹珠。

开始轮到你选择一个非空的 jar ，从那个 jar 里捡起所有的弹珠，然后在经过一个 jar 时丢下一个弹珠来绕着棋盘移动。如果您的最后一颗弹珠落在商店中，您将获得另一个回合。如果你降落在一个非空的、非商店的 jar 里，你会拿起那个 jar 里的所有东西并继续。最后，如果您落在一个空底池中，则转牌交给对手。

到目前为止，我已经通过选择所有可能的路径然后根据商店中弹珠的数量对它们进行排序来解决这个问题。路径意味着从你的一个 jar 开始，进行所有必要的拾取和移动，然后看看你是落在商店里还是落在空 jar 里。如果您登陆商店，您就可以继续，现在新分店的数量与您这边的非空 jar 数量一样多。

问题在于，如果您从花盆中的五颗弹珠开始，那么路径已经相当多了。跳到六，ghci 就会耗尽内存。

我不知道如何降低成本的原因是因为我认为在计算过程中每条路径都是必需的。虽然我只需要生成的数千(或数百万)条路径中的最多三个路径(最好的路径)，但需要运行其余路径以查看它们是否真的比之前的路径更好。
如果一个更长(通常更好)，那很好但很昂贵。如果它比之前的任何路径都短，那么程序仍然必须计算该路径才能找出答案。

有没有什么办法解决这个问题，或者是否根据定义计算所有必要的路径？

Answer 1

只需按顺序全部尝试，将您的移动序列记录为数字 1 到 6 的序列(代表您从中挑选弹珠的 jar )，每次重播整个过程从头开始的顺序。只保留和更新三个获胜者，加上最后的 Action 序列，这样您就知道接下来要尝试什么。如果没有下一步的合法行动，请倒退一个档次。

它可能会非常慢，但会使用很少的内存。您不存储结果位置，只存储从中挑选的 jar 数，并且每次从起始位置重新播放序列，改变最后一步(而不是 2，接下来尝试 3、4 等；如果没有更多合法的移动, 回溯一级)。或者可能只为尝试的最后一系列移动存储位置，以便更容易回溯。

这是当时典型的速度权衡空间。