广度优先搜索效率低

Question

我正在写一个简单的广度优先搜索算法是Scala，我觉得它应该非常有效。但是，当我运行此问题时，我遇到了一些相对较小的问题，导致内存不足。

def search(start: State): Option[State] = {
    val queue: mutable.Queue[State] = mutable.Queue[State]()
    queue.enqueue( start )
    while( queue.nonEmpty ){
      val node = queue.dequeue()
      if( self.isGoal(node) )
        return Some(node)
      self.successors(node).foreach( queue.enqueue )
    }
    None
}

我相信可变队列上的入队和出队方法是固定时间的，并且每种方法都可以有效实施。方法是目标，我知道后继者会尽可能地高效。我不明白我怎么会这么快用尽内存。我缺少该代码中的任何低效率吗？

Answer 1

[我认为c0der的注释已将其钉牢：您可能会陷入无限循环，从而重新检查已访问的节点。考虑以下更改：

def search(start: State): Option[State] = {
    var visited: Set[State] = Set() // change #1
    val queue: mutable.Queue[State] = mutable.Queue[State]()
    queue.enqueue( start )
    while( queue.nonEmpty ){
      val node = queue.dequeue()
      if (!visited.contains(node)) { // change #2
        visited += node // change #3
        if( self.isGoal(node) )
          return Some(node)
        self.successors(node).foreach( queue.enqueue )
      }
    }
    None
}

1. 初始化一个新集合visited，以跟踪您去过的节点。
2. 将节点出队后，请立即检查您是否曾经访问过它。如果不是，请继续检查该节点。否则，请忽略它。
3. 请确保将此节点添加到visited集中，以便以后不再进行检查。

希望有帮助的人：D