scala - 如何在 Scala 中停止回溯？

Question

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

我想我可以强制执行（例如，使用可变布尔标志）。我想知道如何在功能上做到这一点。

Answer 1

While Scala's Option will work here, as two other answers have pointed out, a more idiomatic functional approach would be to use a "lazy list"—or a Stream, in Scala—to represent the set of solutions.

I've found myself writing code like this, for example:

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)
  }
}

Now suppose I have a Board class that extends Node[Board] and that has an implementation of the children method that returns all valid boards with one additional piece. Suppose it also has some other useful stuff, like a size method, a companion object with an empty, etc.

I can then write the following to get a Stream of solutions:

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

A Stream is lazy and only evaluates its head, so right now we've only searched the tree far enough to find the first solution. We can get this solution using head:

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

Or whatever. But I can also get other results if I want them:

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

This searches just enough more of the tree to find the tenth solution, and then stops.

The big advantage of Stream over the Option approach is that I can get additional results if I need them, without paying more for the first.

Answer 2

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

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 可能有一个选项/也许类型，你可以使用它。这个建议同样适用于任何函数式语言。