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

Question

我在CodeReview上发布了这个问题,但我开始意识到这不是一个Haskell问题,因为它是一个算法问题.

Haskell代码可以在我的github repo上找到,但我认为代码并不像一般概念那么重要.

基本上该程序计算出卡拉哈(瑞典变体)游戏中最佳的第一组动作.只考虑第一个"转弯",所以我们假设你开始并且没有计算从对手开始移动的任何东西.

Kalaha董事会http://www.graf-web.at/mwm/kalaha.jpg

董事会从空店开始,每个锅中都有相同数量的弹珠.

你开始轮到你选择一个非空的锅,从锅中取出所有的大理石,然后在通过锅时丢下一块大理石在板上移动.如果你的最后一块大理石落在商店里,你会再转一圈.如果你降落在一个非空的非商店锅里,你就拿起那个锅的所有内容然后继续.最后,如果你落在一个空锅中,转弯将传递给对手.

到目前为止,我已经通过挑选所有可能的路径解决了这个问题,然后根据商店中大理石的数量对它们进行排序.一条路径意味着从你的一个花盆开始,做所有必要的拾取和移动,看看你是在商店里还是在空锅里.如果你在商店降落,你可以继续,现在有很多新的分支,因为你身边有非空的花盆.

问题在于,如果你从花盆中的五个大理石开始,它已经是相当多的路径.跳到六,ghci内存耗尽.

我无法弄清楚如何降低成本的原因是因为我认为在计算过程中每条路径都是必需的.虽然我在生成的数千(或数百万)中只需要最多三条路径(最好的路径),但其余路径需要通过检查它们是否实际上比以前更好.
如果一个更长(通常更好)那么这是好的,但成本高.如果它比任何先前的路径短,那么程序仍然必须计算该路径才能找到它.

有没有办法解决这个问题,还是计算定义所需的所有路径？

Answer 1

只需按顺序尝试所有这些，将您的移动序列记录为数字 1 到 6 的序列（代表您从中挑选弹珠的罐子），每次从头开始重播整个序列。仅保留并更新三个获胜者以及最后的动作序列，以便您知道下一步要尝试什么。如果没有下一步的合法举措，则后退一步。

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

这是一个典型的速度权衡空间。