如何解决可视化算法的问题

Question

我想实现一个问题，即在迷宫中从（0,0）单元格到（m-1，n-1）单元格找到路径，其中有一些障碍物。
我使用递归回溯算法来解决这个问题，我只想做一些可视化，以便我们可以看到当我们在迷宫中行进时路径是如何被取的。
我看到了这个问题here 现在我已经使用JavaScript实现了它，我正在给我们访问的单元格涂上蓝色，然后如果我们回溯，就再次删除颜色，但是所有事情都发生得非常快，因此我尝试使用 sleep()函数进行一些延迟，但我认为我没有正确使用它们，因为显示任何随机模式而不是它所采取的正确路径。

如果有人能帮助我解决这个问题，那将是一个很大的帮助。
您可以在here检查我的问题

我用于寻找路径的算法是：

let getMazePath = async (maze, r, c, ans) => {
  if (
    r < 0 ||
    c < 0 ||
    r >= maze.length ||
    c >= maze[0].length ||
    maze[r][c] == 1 ||
    visited[r][c] == 1
  )
    return;

  if (r == maze.length - 1 && c == maze[0].length - 1) {
    document.getElementById("path-display").innerHTML =
      "Path is: '" + ans + "'";
    console.log("Path is: '" + ans + "'");
    return;
  }

  let currSq = document.getElementById(r + "_" + c);
  currSq.classList.add("visited-square");
  await sleep(1000);
  visited[r][c] = 1;

  getMazePath(maze, r - 1, c, ans + "t");
  getMazePath(maze, r, c - 1, ans + "l");
  getMazePath(maze, r + 1, c, ans + "d");
  getMazePath(maze, r, c + 1, ans + "r");

  visited[r][c] = 0;
  currSq.classList.remove("visited-square");
  await sleep(1000);
};

function sleep(ms){
  return new Promise((resolve) => {
    setTimeout(resolve, ms);
  })
}

- sachuverma

Answer 1

你忘记等待递归调用。

通过在 getMazePath 调用前加上 await 来修复它：

await getMazePath(maze, r - 1, c, ans + "t");
await getMazePath(maze, r, c - 1, ans + "l");
await getMazePath(maze, r + 1, c, ans + "d");
await getMazePath(maze, r, c + 1, ans + "r");

在CodePen上查看实时演示。

---

您可能还希望在找到路径时停止运行它。

为此，返回答案并进行检查：

let getMazePath = async (maze, r, c, ans) => {
  if (
    r < 0 ||
    c < 0 ||
    r >= maze.length ||
    c >= maze[0].length ||
    maze[r][c] == 1 ||
    visited[r][c] == 1
  )
    return; 

  if (r == maze.length - 1 && c == maze[0].length - 1) {
    document.getElementById("path-display").innerHTML =
      "Path is: '" + ans + "'";
    console.log("Path is: '" + ans + "'");
    return ans;
        // ^^^
  }

  let currSq = document.getElementById(r + "_" + c);
  currSq.classList.add("visited-square");
  await sleep(1000);
  visited[r][c] = 1;

  {
    const res = await getMazePath(maze, r - 1, c, ans + "t");
    if(res) return res
  }
  {
    const res = await getMazePath(maze, r, c - 1, ans + "l");
    if(res) return res
  }
  {
    const res = await getMazePath(maze, r + 1, c, ans + "d");
    if(res) return res
  }
  {
    const res = await getMazePath(maze, r, c + 1, ans + "r");
    if(res) return res
  }
  visited[r][c] = 0;
  currSq.classList.remove("visited-square");
  await sleep(1000);
};

查看实际演示，请访问CodePen

- FZs

---

你能告诉我为什么在递归调用之前添加await修饰符就可以解决问题吗？我对async await不是很了解。 - sachuverma

@sachuverma 因为这是对一个异步函数的调用。异步函数在被调用后立即返回，并返回所谓的Promise对象，使用它可以检查调用的状态，但异步函数的执行是异步的（因此得名，对吧？）。await暂停异步函数的执行，直到给定的Promise完成。如果没有这些await，函数只会启动递归调用，但不会等待它们完成。而且，同时执行的多个函数会改变相同的对象，可能会造成大问题。 - FZs