6

我刚刚克服了弄清楚如何使用 List monad 进行非确定性计算的困难。但是，我相信我的算法将受益于广度优先搜索，而不是从 List monad 获得的深度优先搜索。

这是一段摘录，展示了我的算法中有趣的部分。它是逻辑谜题 Akari 的求解器。

solve :: Game -> [Game]
solve game = do
        let ruleBasedSolverResult = applyRuleBasedSolversUntilSteady game
        guard $ consistant ruleBasedSolverResult
        if solved ruleBasedSolverResult
                then return ruleBasedSolverResult
                else speculate ruleBasedSolverResult

speculate :: Game -> [Game]
speculate game = do
        coord <- coords game
        guard $ lightableUnlit game coord
        let solutions = solve $ light game coord
        if null solutions
                then solve $ exclude game coord
                else solutions

基本上它应用一些基本的确定性规则来查看是否可以解决它。如果不是，它会尝试在不同的地方放灯。如果灯光在递归解决后使谜题不一致，则会在灯光所在和继续进行的位置放置一个排除标记。如果它在放置灯时找到了解决方案，那么它将这些解决方案添加到解决方案列表中。

这工作正常，但速度很慢，因为通常有一个明显的选择来推测哪个坐标会很快导致不一致的谜题，并让您放置一个只有一个（或两个）搜索级别的 x，但如果它没有直到搜索到一半才选择该坐标，然后它会首先咀嚼一堆无趣的东西。因此，广度优先搜索的想法。

我用谷歌搜索了诸如“广度优先非确定性单子”之类的东西，得到了一些我难以理解的结果，例如：

  • Control.Monad.Omega这对我需要的东西来说似乎有点矫枉过正，因为它似乎可以防止无限发散的确定性，这对我来说不是这样，而且我并不完全理解它。

  • Control.Monad.WeightedSearch Control.Monad.Omega 的文档建议在将其用作 Monad 时使用它，但我认为加权对于我的需求来说也有点矫枉过正。我可能只有 2 个权重，一个用于有解决方案的东西，一个用于没有解决方案的东西。

  • Control.Monad.Level我不相信这会为我想要的，因为只有树的叶子有值。

  • Data.Tree我认为这可能是我想要使用的，但我不确定如何将我的 List monadic 代码转换为使用它，尽管我觉得有一种很好的方式。

我的下一个问题是关于如何并行化它:)

4

1 回答 1

6

我相信Kiselyov、Shan 和 Friedman 的“Backtracking, Interleaving, and Terminating Monad Transformers”（功能明珠）概述了一个解决方案。

免责声明：我不是这项工作的专家！

基本上，您必须使用不同的 monad。由于ListTmonad 转换器做深度优先，他们想出了一个新的 monad 转换LogicT器，它做广度优先。（如果你对 monad 转换器不感兴趣，你可以应用一个转换器Id来取回一个普通的 monad）。

首先，他们认识到其他方法的缺陷：

MonadPlus 的大多数实现执行的直接深度优先搜索是不公平的：两个备选方案之间的非确定性选择先尝试第一个备选方案的每个解决方案，然后再尝试第二个备选方案的任何解决方案。当第一个选项提供无限数量的解决方案时，第二个选项永远不会尝试，从而使搜索不完整。事实上，正如我们在第 3 节中的示例所示，公平回溯有助于更多的逻辑程序终止。

[...]

许多现有回溯单子的第二个缺陷是采用 Prolog 的切割，它将否定与修剪混淆。从理论上讲，否定和剪枝中的每一个都独立地使逻辑编程语言更具表现力

[...]

第三个实际缺陷是经常被遗忘的顶级接口：如何运行可能返回无限数量答案的计算并与之交互？最常见的解决方案是提供一个可以根据需要在顶层消费或处理的流。但是在 monad 转换器的情况下，这个解决方案只有在基本 monad 是非严格的（例如 Haskell 的惰性列表 monad 和 LazyST）时才有效。在基本单子严格的情况下，即使我们只需要一个答案，通过强制对整个流进行评估，评估也可能会发生分歧。

然后他们提出了一个基于LogicTmonad 转换器和msplit函数的解决方案。尽管代码的链接已损坏，但我搜索了 HoogleLogicT并找到了这个.

我希望阅读这篇论文能给你一个很好的主题背景知识，并帮助你理解如何使用你已经找到的项目。

如果你觉得这篇论文有用，别忘了查看它的参考文献和引用它的其他论文！

于 2014-03-11T19:08:32.777 回答