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.

Utilizando una matriz bidimensional para BFS

02 Aug, 2023 Programación

Tengo una cuadrícula en la que mantengo celdas con valores 1 y 0 (se generan aleatoriamente). Una celda con valor 1 significa que es una celda vacía y puedo moverme hacia esa celda, y con 0 significa que esta celda está bloqueada. Quiero ser capaz de determinar, para cada posición (x, y), si hay un camino disponible hacia un punto (x’, y’) moviéndome en las 4 direcciones pero no diagonalmente.

De acuerdo con una investigación, el algoritmo BFS es una solución a mi problema, pero tengo dificultades para entender cómo transformar esa matriz en un grafo y cómo mantener la información de las celdas bloqueadas.

Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Solución utilizando el algoritmo BFS

    El algoritmo BFS (Búsqueda en anchura) se utiliza para recorrer un grafo en forma de anchura. En otras palabras, comienza buscando desde el nodo raíz y explora todos los nodos vecinos en la profundidad actual antes de pasar a explorar la siguiente profundidad.

    En este caso, podemos representar la cuadrícula como un grafo, donde cada posición en la cuadrícula representa un nodo en el grafo. Las aristas que conectan estos nodos representan los caminos que podemos seguir para movernos de una posición a otra.

    Para transformar la cuadrícula en un grafo, podemos crear un diccionario donde cada clave sea una posición en la cuadrícula y el valor correspondiente sea una lista de posiciones adyacentes a las que se puede llegar moviéndose en una de las cuatro direcciones (arriba, abajo, izquierda, derecha). Solo agregamos posiciones adyacentes que no estén bloqueadas (es decir, que tengan un valor de 1).

    Por ejemplo, consideremos la siguiente cuadrícula:

    0 1 0
1 1 1
0 1 0

    Podemos representarla como un diccionario de la siguiente manera:

    {
  (0, 1): [(1, 1)],
  (1, 0): [(0, 0), (2, 0), (1, 1)],
  (1, 1): [(0, 1), (1, 0), (1, 2), (2, 1)],
  (1, 2): [(0, 2), (1, 1), (2, 2)],
  (2, 1): [(1, 1), (2, 0), (2, 2)]
}

    En este ejemplo, la posición (1,1) tiene como vecinos (0,1), (1,0), (1,2) y (2,1), porque estas celdas no están bloqueadas.

    Para determinar si hay un camino desde la posición (x,y) hasta (x',y'), podemos utilizar el algoritmo BFS. Comenzamos agregando la posición inicial (x,y) a una cola y la marcamos como visitada. Luego desencolamos la primera posición de la cola y agregamos todos sus vecinos no visitados a la cola. Marcamos estos vecinos como visitados y continuamos este proceso hasta encontrar la posición objetivo (x',y') o hasta que la cola quede vacía (en cuyo caso, no hay un camino).

    Para llevar un seguimiento de las celdas bloqueadas en el algoritmo BFS, simplemente las saltamos al agregar los vecinos a la cola. De esta manera, las celdas bloqueadas no se tendrán en cuenta durante la búsqueda.

    En general, la complejidad del algoritmo BFS es O(V+E), donde V es el número de nodos (posiciones) en el grafo y E es el número de aristas (posibles caminos entre nodos). En nuestro caso, la complejidad temporal será proporcional al número de celdas en la cuadrícula, ya que tenemos que crear un diccionario con listas de adyacencia para cada celda.

Comments are closed.