es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Rastrear nodos hasta el destino desde el origen.

17 Jul, 2023 Programación

Hice este algoritmo de búsqueda en anchura en Scala, y me preguntaba si alguien podría ayudarme a identificar lo que necesito para que rastree la ruta más corta desde el nodo de inicio hasta el nodo final en lugar de solo la distancia. Comienza creando un gráfico con índices que son enteros para cada punto de la cuadrícula, y las ubicaciones de la cuadrícula son solo coordenadas x e y. ¡Gracias! Quiero que genere una lista enlazada o una lista regular.

def bfsDistance(gameState: AIGameState, start: GridLocation, end: GridLocation): Int = {
    val maze: Graph[GridLocation] = gameState.levelAsGraph()
    val startNodeIndex = maze.nodes.filter(<em>.</em>2 == start).keys.head
    val endNodeIndex = maze.nodes.filter(<em>.</em>2 == end).keys.head

    var distMap = Map(startNodeIndex -> 0)
    var visited = Set(startNodeIndex)
    val queue = new mutable.Queue[(Int, Int)]
    queue.enqueue((startNodeIndex, 0))

    while (!queue.isEmpty) {
        val (nodeIndex, nodeDist) = queue.dequeue()
        if (nodeIndex == endNodeIndex) {
            return distMap(nodeIndex)
        } else {
            for (neighbor <- maze.adjacencyList(nodeIndex)) {
                if (!visited.contains(neighbor)) { 
                    queue.enqueue((neighbor, nodeDist + 1)) 
                    distMap += neighbor -> (nodeDist + 1)
                    visited = visited + neighbor 
                }
            }
        }
    }
    distMap(endNodeIndex)
}
Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para modificar el algoritmo BFS existente para rastrear la ruta más corta en lugar de solo la distancia, necesitas llevar un registro del predecesor de cada nodo visitado durante la búsqueda. Esto se puede hacer con un mapa adicional que mapea cada nodo con su predecesor.

    Aquí tienes una versión actualizada del algoritmo que almacena la información del predecesor en un Map llamado “predMap”. El predecesor del nodo de inicio se establece en -1, lo que indica que no tiene predecesor.

    def bfsShortestPath(gameState: AIGameState, start: GridLocation, end: GridLocation): List[GridLocation] = {
  val maze: Graph[GridLocation] = gameState.levelAsGraph()
  val startNodeIndex = maze.nodes.filter(_._2 == start).keys.head
  val endNodeIndex = maze.nodes.filter(_._2 == end).keys.head

  var visited = Set(startNodeIndex)
  val queue = new mutable.Queue[Int]
  queue.enqueue(startNodeIndex)

  val predMap = collection.mutable.Map[Int, Int]()
  predMap(startNodeIndex) = -1

  while (!queue.isEmpty) {
    val nodeIndex = queue.dequeue()
    if (nodeIndex == endNodeIndex) {
      // Se ha encontrado el nodo final
      return constructPath(predMap, endNodeIndex)
    } else {
      // Visitar cada vecino no visitado del nodo actual
      for (neighbor <- maze.adjacencyList(nodeIndex)) {
        if (!visited.contains(neighbor)) {
          queue.enqueue(neighbor)
          visited = visited + neighbor
          predMap(neighbor) = nodeIndex
        }
      }
    }
  }

  // No se encontró ninguna ruta
  List[GridLocation]()
}

// Construye la ruta desde el nodo de inicio hasta el nodo final basándose en el mapa de predecesores
def constructPath(predMap: collection.mutable.Map[Int, Int], endNodeIndex: Int): List[GridLocation] = {
  var path = List(endNodeIndex)
  var currentNode = endNodeIndex
  while (predMap(currentNode) != -1) {
    currentNode = predMap(currentNode)
    path = currentNode :: path
  }
  path.map(index => predMap(index)).map(maze.nodes(_)).reverse
}

    El método bfsShortestPath ahora devuelve una lista de GridLocations que representa la ruta más corta desde el nodo de inicio hasta el nodo final. El método constructPath toma el mapa de predecesores y el índice del nodo final y construye la ruta en orden inverso siguiendo los enlaces de predecesor desde el nodo final hasta el nodo de inicio. Finalmente, devuelve la ruta en el orden correcto mapeando los índices en orden inverso a sus correspondientes GridLocations.

Comments are closed.