Ширина сначала неэффективность поиска

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
}

Я считаю, что методы enqueue и dequeue в изменяемой очереди имели постоянное время и для каждого реализованы эффективно. Методы isGoal и наследники, которых я знаю, настолько эффективны, насколько они могут быть. Я не понимаю, как я могу исчерпать память так быстро. Есть ли какие-то недостатки в этом коде, которые мне не хватает?

Answer 1

У вас есть код 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

и проверить, сможете ли вы go не хватает памяти, и, как вы, вероятно, покажете, это покажет вам, почему вы должны использовать tailre c.

Answer 2

Я думаю, что комментарий c0der прибил его: возможно, вы попали в бесконечное число l oop перепроверок узлов, которые вы уже посетили. Рассмотрите следующие изменения:

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