Scala中如何停止回溯？

Question

假设我正在使用回溯来解决问题（例如 N-Queen）。如果我想找到唯一一个（第一个）解决方案而不是所有解决方案怎么办？

我想我可以强制（例如使用可变的布尔标志）。我想知道如何才能功能性地做到这一点。

Answer 1

虽然 Scala 的 Option 可以在这里工作，正如其他两个答案所指出的那样，更惯用的功能方法是使用“惰性列表” - 或 Stream，在 Scala 中 — 表示解决方案集。

我发现自己编写了这样的代码，例如：

trait Node[A] {
  def children: Stream[A with Node[A]]

  def dfs(f: A => Boolean): Stream[A] = this.children.flatMap {
    child => if (f(child)) Stream(child) else child.dfs(f)
  }
}

现在假设我有一个扩展 Node[Board] 的 Board 类，并且它具有 的实现Children 方法返回所有有效的棋盘以及一个附加棋子。假设它还有一些其他有用的东西，例如 size 方法、带有 empty 的伴生对象等。

然后我可以编写以下代码来获取 Stream解决方案的：

val solutions = Board.empty.dfs(_.size == 8)

Stream 是惰性的，仅评估其头部，因此现在我们仅在树中搜索足够远的距离来找到第一个解决方案。我们可以使用 head 得到这个解决方案：

scala> solutions.head
res1: Board = 
o . . . . . . .
. . . . o . . .
. . . . . . . o
. . . . . o . .
. . o . . . . .
. . . . . . o .
. o . . . . . .
. . . o . . . .

或者其他。但如果我想要的话，我也可以获得其他结果：

scala> solutions(10)
res2: Board = 
. o . . . . . .
. . . . . . o .
. . . . o . . .
. . . . . . . o
o . . . . . . .
. . . o . . . .
. . . . . o . .
. . o . . . . .

这将搜索足够多的树来找到第十个解决方案，然后停止。

与 Option 方法相比，Stream 的一大优点是，如果我需要的话，我可以获得额外的结果，而无需为第一个结果支付更多费用。

Answer 2

这是一个简单的案例，深度优先搜索在找到要查找的内容时停止。正如 Chris K 的回答中提到的，它使用了 Option。

case class Tree[A](v: A, subtrees: Tree[A]*) {
  def dfs(s: A): Option[A] = {
    println("visiting " + v)
    subtrees.foldLeft(if(v == s) Some(v) else None)((r, t) => 
      if(r.isDefined) 
        r 
      else 
        t.dfs(s)
    )
  }
  override def toString() = "Tree(%s%s%s)".format(v, if(subtrees.nonEmpty) ", " else "", subtrees.mkString(", "))
}

用法：

scala> val t = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))
t: Tree[Int] = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))

树 t 看起来像

     1
   /   \
  2     5
 / \   / \
3   4 6   7    

因此我们可以搜索一个元素并跟踪它访问的节点：

scala> t.dfs(6)
visiting 1
visiting 2
visiting 3
visiting 4
visiting 5
visiting 6
res42: Option[Int] = Some(6)

请注意，在找到我们要查找的内容后，我们不再访问任何节点。

Answer 3

假设您正在使用递归搜索函数，您的函数应该返回结果（即皇后的位置）或指示找不到该分支的结果。 Scala 可能有一个选项/也许类型，你可以使用它。这个建议同样适用于任何函数式语言。