13

我在 CodeReview 上发布了这个问题，但我意识到这与其说是 Haskell 问题，不如说是算法问题。

Haskell 代码可以在我的 github 存储库中找到，但我认为代码不如一般概念重要。

基本上，该程序会计算出卡拉哈游戏（瑞典变体）中的最佳第一组动作。只考虑第一个“回合”，因此我们假设您开始，并且从对手开始移动的点开始的任何事情都不会被计算。

卡拉哈板 http://www.graf-web.at/mwm/kalaha.jpg

棋盘一开始是空的商店和每个罐子里等量的弹珠。

你开始你的回合，选择你身边的一个非空罐子，从那个罐子里捡起所有的弹珠，然后在经过一个罐子时通过丢下一颗弹珠在棋盘上移动。如果您的最后一块大理石落在商店中，您将获得另一个回合。如果你降落在一个非空的、非商店的罐子里，你拿起罐子里的所有东西并继续。最后，如果你落入一个空底池，转牌就会传给对手。

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

问题在于，如果你从花盆里的五颗弹珠开始，那已经是相当多的路径了。跳转到 6 并且 ghci 内存不足。

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

有什么办法可以解决这个问题，还是根据定义计算所有必要的路径？

4

2 回答 2

2

您可以尝试使用此并行版本的地图进行并行化：

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

然后，您将为分支中的每个选择启动一个新线程。

如果你使用 asparMap pathFunction kalahaPots作为你的递归，它会激发很多线程，但它可能会更快，你可以将它分块，但我不是一个并行的 haskeller 好。

于 2012-07-13T14:42:48.163 回答
2

只需按顺序尝试它们，将您的移动序列记录为数字 1 到 6 的序列（代表您从中挑选弹珠的底池），每次都从头开始重播整个序列。只保留并更新三个获胜者，以及最后的一系列动作，这样您就知道下一步该尝试什么了。如果没有下一个合法的动作，就退回一个档次。

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

这是一个典型的速度交易空间。

于 2012-07-12T20:15:20.090 回答