从迷宫中找到最短路径（广度优先搜索）

本文介绍了从迷宫中找到最短路径（广度优先搜索）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

晚上好。我有一个以矩阵形式表示的迷宫。有一个起点和一个终点。我写了一个函数，它将所有可以访问的单元格添加到数组中。该函数还会删除所有没有后代的单元格（死锁）。但该功能不会删除导致死胡同的单元格。请帮助完成该功能。

Good evening. I have a labyrinth that is represented in the form of a matrix. There is a start point and an endpoint. I wrote a function that adds to the array all the cells that can be accessed. The function also deletes all cells that do not have descendants (deadlock). But the function does not delete cells that lead to a dead end. Please help to finish the function.

//maze matrix = [ [0, 1, 0, 1, 0], [0, 0, 1, 0, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0], [0, 1, 0, 1, 0] ]; var start = [4, 0]; var end = [3, 4]; function findWay(position, end) { var queue = []; //an array that contains the cells that have already visited var visited = []; //An array that contains cells that can not be entered for this position var invalidCells = []; //mark the current cell with a unit so as not to visit it anymore. matrix[position[0]][position[1]] = 1; //add the current position to the queue queue.push(position); //until the queue is empty while (queue.length > 0) { //get the first element of the queue var pos = queue.shift(); //we clear the array, because for each new position we will have our own array invalidCells.length = 0; //an array of motion directions var direction = [ [pos[0] + 1, pos[1]], [pos[0], pos[1] + 1], [pos[0] - 1, pos[1]], [pos[0], pos[1] - 1] ]; for (var i = 0; i < direction.length; i++) { //do a check for each direction //if at least one cell does at least one of the conditions, the cell is placed in an array of invalid cells //then run a new iteration of the loop if (direction[i][0] < 0 || direction[i][0] >= matrix[0].length || direction[i][1] < 0 || direction[i][1] >= matrix[0].length || matrix[direction[i][0]][direction[i][1]] != 0) { invalidCells.push(direction[i]); continue; } //If this direction turned out to be an end cell //return the array of visited cells if (direction[i][0] == end[0] && direction[i][1] == end[1]) return visited; //if none of the conditions are met, mark this direction with one and add it to the end of the queue matrix[direction[i][0]][direction[i][1]] = 1; queue.push(direction[i]); } //add the current position to the array of visited cells visited.push(pos); //If no iteration of the loop returns anything, then this cell is a dead end if (invalidCells.length == 4) { //remove the deadlock from the array visited.pop(); } } } findWay(start, end);

推荐答案

似乎无需跟踪已访问和 invalidCells ：

• 已访问包含所有访问过的单元格（在所有方向上）。虽然你到达死胡同后试图从中移除细胞，但是没有简单的方法可以回溯并从中移除其他细胞，导致这个死胡同，并且它们不会参与其他可能仍然存在的路径成功。

• visited contains all the visited cells (in all directions). Although you try to remove cells from it once you reach a dead end, there is no easy way to backtrack and remove from it other cells, which lead to this dead end, and which are not involved in other paths that could still be successful.

invalidCells 仅用于检测死胡同，但由于上一点，我会放弃使用。

invalidCells is only used to detect dead ends, but because of the previous point, I would drop its use.

我认为你的目标是达到访问数组，表示结束单元格的最短路径，从中删除所有可能的变体绕道。使用BFS实现这一目标的方法是使用您的队列不仅可以存储位置，还可以使用导致这些位置的最短路径。然后，当您点击结束单元格时，您可以返回该单个路径，忽略可能仍在队列中的所有其他路径。

I assume your goal is to arrive at a visited array that represents the shortest path to the end cell, with all possible variant detours removed from it. The way you can achieve that with BFS is to use your queue not only to store positions, but the shortest paths that led to those positions. Then when you hit the end cell, you can return that single path, ignoring all the other paths that might still be in the queue.

请注意，存在问题你的例子：结束单元格被标记为1，你的代码将不会检测到这样的单元格作为结束单元格，但会绕过它，并且永远不会找到它。要么确保结束单元始终标记为0，要么在进行任何其他检查之前执行结束单元测试。

Note that there is a problem with your example: the end cell is marked as 1, and your code will not detect such a cell as end cell, but will walk around it, and never find it. Either make sure an end cell is always marked 0, or perform the end-cell-test before doing any other check.

以下是对代码所做的更改 - - 查看评论的位置。

Here are the changes to make to your code -- see where the comments are.

var matrix = [ [0, 1, 0, 1, 0], [0, 0, 1, 0, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0], [0, 1, 0, 1, 0] ]; var start = [4, 0]; var end = [3, 4]; function findWay(position, end) { var queue = []; matrix[position[0]][position[1]] = 1; queue.push([position]); // store a path, not just a position while (queue.length > 0) { var path = queue.shift(); // get the path out of the queue var pos = path[path.length-1]; // ... and then the last position from it var direction = [ [pos[0] + 1, pos[1]], [pos[0], pos[1] + 1], [pos[0] - 1, pos[1]], [pos[0], pos[1] - 1] ]; for (var i = 0; i < direction.length; i++) { // Perform this check first: if (direction[i][0] == end[0] && direction[i][1] == end[1]) { // return the path that led to the find return path.concat([end]); } if (direction[i][0] < 0 || direction[i][0] >= matrix[0].length || direction[i][1] < 0 || direction[i][1] >= matrix[0].length || matrix[direction[i][0]][direction[i][1]] != 0) { continue; } matrix[direction[i][0]][direction[i][1]] = 1; // extend and push the path on the queue queue.push(path.concat([direction[i]])); } } } var path = findWay(start, end); console.log(JSON.stringify(path));