广度优先搜索效率低下

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
}

我相信可变队列上的入队和出队方法是恒定的，并且每个方法都得到了有效的实现。我所知道的isGoal和后继者的方法都是非常高效的。我不明白我怎么这么快就把内存用完了。这段代码中是否有我遗漏的低效之处？

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，要跟踪您在将节点出队后对哪些节点进行了to.
2. Immediately，请检查您以前是否访问过它。如果没有，请继续检查此节点。否则，请忽略它。
3. 请确保将此节点添加到visited集合中，以便以后不会再次选中它。

希望这能有所帮助:D

Answer 2

这里有一些Java代码，而不是Scala代码。对于Scala，vars和while是您根本不应该使用的东西。这是我的建议，你可以如何解决这个问题。

 class State(val neighbours: List[State]) // I am not sure how your State class looks like, but it could look something like this

  val goal = new State(List())

  def breathFirst(start: State): Option[State] = {

    @scala.annotation.tailrec
    def recursiveFunction(visited: List[State], toVisit: List[State]): Option[State] = { // So we will create recursive function with visited nodes and nodes that we should visit
      if (toVisit.isEmpty) return None // If toVisit is empty that means that there is no path from start to goal, return none
      else {
        val visiting = toVisit.head // Else we should take first node from toVisit
        val visitingNeighbours = visiting.neighbours // Take all neighbours from node that we are visiting
        val visitingNeighboursNotYetVisited = visitingNeighbours.filter(x => !visited.contains(x)) //Filter all neighbours that are not visited
        if (visitingNeighboursNotYetVisited.contains(goal)) { //if we found goal, return it
          return Some(goal)
        } else {
          return recursiveFunction(visited :+ visiting, toVisit.tail ++ visitingNeighboursNotYetVisited) // Otherwise add node that we visited in this iteration to list of visited nodes that does not have visited node - it was head so we take toVisit.tail
          // and also we will take all neighbours that are not visited and add them to toVisit list for next iteration
        }
      }
    }

    if (start == goal) { // If goal is start, return start
      Some(start)
    } else { // else call our recursive function with empty visited list and with toVisit list that has start node
      recursiveFunction(List(), List(start))
    }
  }

注意:您可以更改：

val visitingNeighboursNotYetVisited = visitingNeighbours.filter(x => !visited.contains(x)) //Filter all neighbours that are not visited

使用

val visitingNeighboursNotYetVisited = visitingNeighbours

并且检查你是否会耗尽内存，并且，你可能不会，它会告诉你为什么你应该使用tailrec。