如何使用 FP 在 Scala 中实现广度优先搜索

Question

我想知道如何使用函数式编程在 Scala 中实现 Breadth-first search。

这是我的第一个不纯的代码：

  def bfs[S](init: S, f: S => Seq[S], finalS: S => Boolean): Option[S] = {
    val queue = collection.mutable.Queue[S]()

    queue += init
    var found: Option[S] = None

    while (!queue.isEmpty && found.isEmpty) {
      val next = queue.dequeue()
      if (finalS(next)) {
        found = Some(next)
      } else {
        f(next).foreach { s => queue += s }
      }
    }
    found
  }

虽然我只使用局部可变性（一个 var 和一个可变的 Queue），但它不是纯粹的函数。

我想出了另一个版本：

  case class State[S](q: Queue[S], cur: S)

  def update[S](f: S => Seq[S])(s: State[S]) : State[S] = {
    val (i, q2) = s.q.dequeue
    val q3 = f(i).foldLeft(q2) { case (acc, i) => acc.enqueue(i)}
    State(q3, i)
  }

  def bfs2[S](init: S, f: S => Seq[S], finalS: S => Boolean): Option[S] = {
    val s = loop(State[S](Queue[S]().enqueue(init), init), update(f) _, (s: State[S]) => s.q.isEmpty || finalS(s.cur))
    Some(s.cur)
  }

  def loop[A](a: A, f: A => A, cond: A => Boolean) : A =
    if (cond(a)) a else loop(f(a), f, cond)

这两种解决方案是否有更好的方法？是否可以使用 cats/scalaz 删除一些样板文件？

Answer 1

这是未经测试的，但我认为可行：

  def bfs[S](init: S, f: S => Seq[S], finalS: S => Boolean): Option[S] = {
    def bfshelper(q: Seq[S], f: S => Seq[S], finalS: S => Boolean): Option[S] = q match {
      case Seq()               => None
      case h +: t if finalS(h) => Some(h)
      case h +: t              => bfshelper(t ++ f(h), f, finalS)
    }
    bfshelper(Seq(init), f, finalS)
  }

诀窍是保留要检查的内容的 Seq，并且，如果当前元素不匹配，则用我们必须检查的内容的剩余部分调用我们自己，并附加此节点的子节点

Answer 2

函数式编程的一个好处是您可以利用惰性将数据结构的遍历与搜索部分分开。这使得可重复使用的单一责任代码成为可能：

import scala.collection.immutable.Queue

def breadth_first_traverse[Node](node: Node, f: Node => Queue[Node]): Stream[Node] = {
  def recurse(q: Queue[Node]): Stream[Node] = {
    if (q.isEmpty) {
      Stream.Empty
    } else {
      val (node, tail) = q.dequeue
      node #:: recurse(tail ++ f(node))
    }
  }

  node #:: recurse(Queue.empty ++ f(node))
}

现在您可以通过 breadth_first_traverse(root, f) find (_ == 16) 执行 BFS 或使用 Stream class 中的任何其他函数在惰性广度优先上执行有用的临时 "queries"压扁了你的树 Stream。

Answer 3

基于 Karl Bielefeldt 给出的答案，这是另一个解决方案（不涉及任何队列，仅使用流）。

def bfs[T](s: Stream[T], f: T => Stream[T]): Stream[T] = {
    if (s.isEmpty) s
    else s.head #:: bfs(s.tail append f(s.head), f)
}

Answer 4

广度优先搜索不可避免地取决于正在搜索的数据类型。根据 WikiPedia 的说法，经典的解决方案包括跟踪已经搜索过的内容，这样您就不会陷入无限循环。

Scala增加了一个要求，就是迭代的主要工具是递归函数，最好是尾递归函数。

因此，这里有一个使用上述方法的解决方案。

首先有一个 Map，其中人名作为字符串，值是一组其他字符串，代表与第一人称有联系的其他人。

因此，如果“Fred”认识“Mary”，而“Mary”认识“John”，您会期望“Mary”出现在“Fred”的姓名列表中，而“John”出现在“Mary”的姓名列表中列表。

考虑到这一点，这是一个经过全面测试的实现（由 RockTheJvm 提供）

  def socialConnection(network: Map[String, Set[String]],
                       a: String, b: String): Boolean = {
    @tailrec
    def bfs(target: String,
            consideredPeople: Set[String],
            discoveredPeople: Set[String]): Boolean = {
      if (discoveredPeople.isEmpty) false
      else {
        val person = discoveredPeople.head
        if (person == target) true
        else if(consideredPeople.contains(person))
          bfs(target, consideredPeople, discoveredPeople.tail)
        else bfs(target, consideredPeople + person,
          discoveredPeople.tail ++ network(person))
      }
    }
    bfs(b, Set(), network(a) + a)
  }

如何使用 FP 在 Scala 中实现广度优先搜索

How to implement breadth first search in Scala with FP

scala

functional-programming

breadth-first-search