typescript - Implementación de búsqueda en anchura atascada en un bucle infinito

Estoy intentando implementar una búsqueda en anchura para resolver un laberinto, pero sigo quedándome atrapado en un bucle infinito y no tengo idea de por qué está sucediendo esto. Filas y columnas son el número de filas y columnas de mi laberinto/rejilla. Estoy empezando desde la celda superior izquierda y comprobando si un vecino está dentro de la rejilla antes de agregarlo a la cola.

export function elementInGrid<T>(neighbour: number[], rows: number, columns: number): boolean{
    const [i, j] = neighbour;
    return (0 <= i && i <= rows - 1) && (0 <= j && j <= columns - 1);
}

function arrayEquality<T>(a: T[], b: T[]): boolean{
    return a.sort().toString() === b.sort().toString()
}

export const breadthFirstSearch = (rows: number, columns: number) => {
    const startPoint = [0, 0];
    const endPoint = [rows - 1, columns - 1];
    const queue = [startPoint];
    while (queue.length > 0){
        const [i, j] = queue.shift()!;
        if (arrayEquality([i, j], endPoint)){
            break
        }
        const neighbours = [[i - 1, j], [i, j + 1], [i + 1, j], [i, j - 1]]
        neighbours.forEach(neighbour => {
            if (elementInGrid(neighbour, rows, columns)){
                queue.push(neighbour);
            }
        })     
    }
}

Respuesta #1

Tu algoritmo asume que no hay ciclos en el grafo, lo cual no parece ser el caso dado tu lista de vecinos. El algoritmo se mueve de la celda 0, 0 a 0, 1, que tiene a 0, 0 como vecino y se encola. Luego, 0, 0 tiene a 0, 1 como vecino, que a su vez tiene a 0, 0 como vecino....

Es inusual que estés ignorando el orden de las coordenadas al verificar si alcanzaste el destino, pero eso no tiene relación con el bucle infinito (arrayEquality tiene un nombre engañoso: solo verifica los primitivos de manera confiable debido a la serialización en cadena y ignora el orden).

Desde el punto de vista del diseño, no codificaría de manera fija los puntos de inicio y fin en la cuadrícula. Tampoco estoy seguro de que tenga mucho sentido que cada celda esté conectada en la cuadrícula, así que probablemente querrías pasar un grafo con paredes (es decir, los vecinos son específicos de cada celda, asumiendo que esto es realmente un laberinto).

Además, el algoritmo no hace nada cuando encuentra un camino a través de la cuadrícula. Me he tomado la libertad de ajustar algunas de estas cosas para que el ejemplo sea un poco más significativo, omitiendo los vecinos del laberinto. También estoy usando JS para que puedas ejecutarlo en un fragmento de pila.

const inGrid = (x, y, rows, cols) => 
  x >= 0 && y >= 0 && x < cols && y < rows
;

const shortestPath = (rows, cols, src, dst) => {
  const queue = [[src, []]];
  
  for (const visited = new Set(); queue.length;) {
    const [[x, y], path] = queue.shift();
    const key = "" + [x, y];
    
    if (visited.has(key)) continue;
    
    visited.add(key);
    path.push([x, y]);

    if (key === "" + dst) return path;

    [[x-1, y], [x, y+1], [x+1, y], [x, y-1]].forEach(e => {
      if (inGrid(...e, rows, cols)) {
        queue.push([e, path.slice()]);
      }
    });
  }
};

console.log(JSON.stringify(shortestPath(5, 5, [0, 0], [4, 4])));

Aquí hay un ejemplo de un laberinto bastante artificial con muros:

const shortestPath = (maze, src, dst) => {
  const queue = [[src, []]];
  
  for (const visited = new Set(); queue.length;) {
    const [[x, y], path] = queue.shift();
    const key = "" + [x, y];
    
    if (visited.has(key)) continue;
    
    visited.add(key);
    path.push([x, y]);

    if (key === "" + dst) return path;

    queue.push(...maze[key].map(e => [e, path.slice()]));
  }
};

const maze = {
  "0,0": [[0, 1], [1, 0]],
  "0,1": [[0, 0], [0, 2]],
  "0,2": [[0, 1], [1, 2]],
  "1,0": [[0, 0], [1, 1]],
  "1,1": [[1, 0]],
  "1,2": [[0, 2]]
};
/*
.--------.
         |
|  --.   |
|    |     
`--------`
*/
console.log(JSON.stringify(shortestPath(maze, [0, 0], [1, 2])));

Respuesta #2

Este algoritmo BFS entra en un bucle infinito porque la lista de celdas visitadas no se guarda en ningún lugar. Por lo tanto, el algoritmo no tiene idea de si una celda ha sido explorada antes o no, lo que es la razón por la que las mismas celdas del laberinto se visitan repetidamente.
Para evitar tal escenario, podemos tener el propio laberinto en la función y cada vez que visitamos una celda, debemos marcarla como visitada en el laberinto, de modo que la próxima vez que la encontremos en el bucle no se vuelva a seleccionar, y así nos ayudará a evitar el bucle infinito. Crearemos un laberinto con todos los elementos establecidos en 0 (marcas de no visitado) y luego, cuando visitemos cualquier celda, vamos a establecer el valor de esa celda en 1. Entonces, la próxima vez aseguraremos que solo seleccionemos aquellas celdas que sean válidas y que no se hayan visitado antes. El siguiente es el código correcto:

    function elementInGrid(neighbour: number[], rows: number, columns: number): boolean{
        const [i, j] = neighbour;
        return (0 (a: T[], b: T[]): boolean{
        return a.sort().toString() === b.sort().toString()
    }

    const breadthFirstSearch = (rows: number, columns: number, maze: number[][]) => {
        const startPoint = [0, 0];
        const endPoint = [rows - 1, columns - 1];
        const queue = [startPoint];
        while (queue.length > 0){
            const [i, j] = queue.shift()!;
            maze[i][j] = 1
            if (arrayEquality([i, j], endPoint)){
                console.log("Reached target")
                break
            }
            const neighbours = [[i - 1, j], [i, j + 1], [i + 1, j], [i, j - 1]]
            neighbours.forEach(neighbour => {
                if (elementInGrid(neighbour, rows, columns) && (maze[neighbour[0]][neighbour[1]] == 0)){
                    console.log(neighbour)
                    queue.push(neighbour);
                    maze[neighbour[0]][neighbour[1]] = 1
                }
            })     
        }
    }
    var maze = [[0,0,0],[0,0,0],[0,0,0]]
    breadthFirstSearch(3,3,maze)

¡Espero que eso ayude!