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

Question

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

scalafunctional-programmingbreadth-first-search

12

我想知道如何用函数式编程在Scala中实现广度优先搜索。以下是我的第一份不纯净的代码：

  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来减少一些样板代码？

- Yann Moisan

不要使用Queue，而是使用（不可变的）List。并且去掉State - 因为cur总是位于队列的顶部 - 只需在向下遍历树时将工作List传递即可。 - Dima

1

“List” 不是栈而是队列吗？ - Jasper-M

嗯，这取决于你从哪一端提取数据。你可以使用一个不可变的Queue，它更高效一些，但也是基于列表的。或者使用IndexedSeq之类的东西来实现对最后一个元素的常数时间访问。 - Dima

我错了还是你只专注于树的算法？对于一般图（带有环）来说，你的示例代码将无限循环，并且对于DAG而言并不是最优的。 - Juh_

4个回答

7

在Karl Bielefeldt提供的答案基础上，这里有另一个解决方案（不涉及任何队列，只使用Streams）。

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

- Angad Singh

将“queue”直接传递到递归调用本身中，我认为会得到更清晰的解决方案。这比上面Karl的解决方案更易于阅读和理解它在做什么。我会将s重命名为nodes，但这只是小问题。 - Cory Klein

2

这个还没有经过测试，但我认为它可以工作：

  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，如果当前元素不匹配，则使用此节点的子项附加我们需要检查的剩余内容来调用自身。

- The Archetypal Paul

0

广度优先搜索不可避免地取决于正在搜索的数据类型。根据维基百科，经典解决方案涉及跟踪已经搜索过的内容，以便您不会陷入无限循环。

Scala 强制要求另外一个要求，即迭代的主要工具是递归函数，最好是尾递归函数。

因此，这里提供了一种使用上述方法的解决方案。

首先有一个 Map，其中人名为字符串，值是表示与第一个人有联系的其他人的字符串集合。

因此，如果 "Fred" 认识 "Mary"，而 "Mary" 认识 "John"，则您期望在 "Fred" 的名称列表中出现 "Mary"，并且在 "Mary" 的列表中出现 "John"。

考虑到这一点，这里提供了一个完全测试过的实现（由 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)
  }

- Sam Smith

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Karl Bielefeldt · Accepted Answer

函数式编程的一个好处是，你可以利用惰性来将数据结构的遍历与搜索部分分开。这使得代码非常可重用，每个部分只负责一项职责：

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类中的任何其他函数，在惰性广度优先平坦化的Stream上执行有用的“查询”。