typescript - Implementering av breadth first search fastnar i en oändlig loop

Jag försöker implementera en breddförstsökning för att lösa en labyrint, men jag fastnar hela tiden i en oändlig loop och jag har ingen aning om varför detta händer. Rader och kolumner är antalet rader och kolumner för min labyrint/grid. Jag börjar från den övre vänstra cellen och kontrollerar om en granne är inom gridet innan jag lägger till dem i köen.

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);
            }
        })     
    }
}

Svar #1

Din algoritm antar att det inte finns några cykler i grafen, vilket inte verkar vara fallet med tanke på din grannlista. Algoritmen flyttar från cell 0, 0 till 0, 1 som har 0, 0 som granne och blir köad. Sedan har 0, 0 0, 1 som granne som har 0, 0 som granne....

Det är ovanligt att du ignorerar koordinatordningen när du kontrollerar om du har nått destinationen, men det är orelaterat till den oändliga loopen (arrayEquality är vilseledande namngiven-den kontrollerar bara primitiva värden på ett pålitligt sätt på grund av strängifiering och ignorerar ordningen).

Ur ett designperspektiv skulle jag inte hårdkoda start- och slutpunkterna i rutnätet. Jag är inte säker på att det är särskilt meningsfullt att varje cell i rutnätet är ansluten, så troligtvis vill du skicka in en graf med väggar (dvs. grannar är specifika för varje cell, förutsatt att detta verkligen är en labyrint).

Dessutom gör algoritmen ingenting när den hittar en väg genom rutnätet. Jag har tagit mig friheten att justera några av dessa saker för att göra exemplet lite mer meningsfullt, och utelämnar labyrintgrannskapet. Jag använder också JS så att du kan köra det i ett stackexempel.

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])));

Här är ett exempel på en ganska påhittad labyrint med väggar:

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])));

Svar #2

Denna BFS-algoritm går in i en oändlig loop eftersom listan över besökta celler inte sparas någonstans. Så algoritmen har ingen aning om en cell har utforskats tidigare eller inte, vilket är anledningen till att samma celler i labyrinten besöks upprepade gånger.
För att undvika ett sådant scenario kan vi ha labyrinten själv i funktionen och varje gång vi besöker en cell måste vi markera den som besökt i labyrinten, så att nästa gång vi stöter på den i loopen plockas den inte igen och på så sätt hjälper det oss att undvika den oändliga loopen. Vi kommer att skapa en labyrint med alla element satta till 0 (markerar ej besökt) och sedan, när vi besöker någon cell, ska vi sätta cellens värde till 1. Så nästa gång säkerställer vi att vi endast plockar de celler som är giltiga och inte besökta tidigare. Följande är den korrekta koden:

    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)

Hoppas det hjälper!!