Реализация первого поиска в ширину застряла в бесконечном цикле

Question

Я пытаюсь реализовать поиск в ширину, чтобы решить лабиринт, но я все время застреваю в бесконечном l oop, и я понятия не имею, почему это происходит. Строки и столбцы - это количество строк и столбцов для моего лабиринта / сетки. Я начинаю с верхней левой ячейки и проверяю, находится ли сосед в сетке, прежде чем добавлять их в очередь.

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

Answer 1

Ваш алгоритм предполагает, что на графике нет циклов, что не похоже на случай, если у вас есть список соседей. Алгоритм переходит от ячейки 0, 0 к 0, 1, которая имеет 0, 0 в качестве соседа, и ставится в очередь. Затем 0, 0 имеет 0, 1 в качестве соседа, который имеет 0, 0 в качестве соседа ....

Это необычно, что вы игнорируете порядок координат при проверке, достигли ли вы места назначения, но это не связано с бесконечный l oop (arrayEquality ошибочно назван - он надежно проверяет только примитивы из-за строкового преобразования и игнорирует порядок).

С точки зрения дизайна, я бы не стал жестко закодировать начальную и конечную точки в сетка. Я не уверен, что имеет смысл соединять каждую ячейку в сетке, поэтому, вероятно, вы захотите передать граф со стенами (т.е. соседи указаны c для каждой ячейки, если это действительно лабиринт).

Кроме того, алгоритм ничего не делает, когда находит путь через сетку. Я взял на себя смелость скорректировать некоторые из этих вещей, чтобы сделать пример более целенаправленным, опуская соседний лабиринт. Я также использую JS, чтобы вы могли запустить его в фрагменте стека.

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

Вот пример довольно надуманного лабиринта со стенами:

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

Answer 2

Этот BFS al go переходит в бесконечное l oop, потому что список посещенных ячеек нигде не сохраняется. Итак, al go не знает, была ли ячейка исследована ранее или нет, поэтому одни и те же ячейки лабиринта посещаются повторно. Чтобы избежать такого сценария, мы можем включить в функцию сам лабиринт, и каждый раз, когда мы посещаем ячейку, мы должны отмечать ее как посещенную в лабиринте, чтобы в следующий раз, если мы встретим ее в l oop, она больше не будет выбрана и таким образом, это поможет нам избежать бесконечного l oop. Мы создадим лабиринт со всеми элементами, установленными на 0 (отметки не посещены), а затем, когда мы посетим любую ячейку, мы установим значение этой ячейки на 1. Итак, в следующий раз мы гарантируем, что выберем только те ячейки, которые являются действительный и ранее не посещенный. Вот правильный код:

    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)

Надеюсь, что это поможет !!