javascript - DFS 矩阵的正确方法是什么？

标签 javascript algorithm recursion depth-first-search

我做这道练习题是为了找出一个词是否存在于矩阵中，这让我意识到我并不完全理解 DFS。

在 Cracking the Coding Interview 中，DFS 的伪代码是:

void search(Node root) {
  if (root == null) return;
  visit(root);
  root.visited = true;
  for each (Node n in root.adjacent) {
    if (n.visited == false) {
      search(n);
    }
  }
}

对我来说，这看起来像这样的格式:

  1. 目标
  2. 标记
  3. 循环
  4. 如果邻居不满足条件，则提早保释
  5. 递归

所以用这种格式，我写了函数dfs():

  function dfs(r, c, i) {    
    // goal
    if (i === word.length-1) return true;

    // mark
    board[r][c] = '#';

    // loop and recurse each neighbor
    for (var d of dirs) {
      var nr = r + d[0];
      var nc = c + d[1];

      // bail early if neighbor does not meet conditions
      if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue;  // neighbor is out of bounds
      if (board[nr][nc] === '#') continue;                                            // neighbor already visited
      if (board[nr][nc] !== word[i+1]) continue;                                      // neighbor does not meet goal

      // recursion
      var result = dfs(nr, nc, i+1);

      // un-mark
      board[r][c] = word[i];

      return result;
    }
  }

其次，我注意到大多数解决方案根本不使用 for 循环，而只是为每个邻居编写 4 次递归。考虑到这一点，我编写了 dfs2():

  1. 目标
  2. 如果当前节点不满足条件，则提前退出
  3. 标记

  4. 递归

    function dfs2(r, c, i) {    
// goal
if (i === word.length) return true;

// bail early if current does not meet conditions
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;  // current is out of bounds
if (board[r][c] === '#') return false;                                          // current already visited
if (board[r][c] !== word[i]) return false;                                      // current does not meet goal

// mark
board[r][c] = '#';

// recursion
var result = dfs2(r+1, c, i+1) || dfs2(r-1, c, i+1) || dfs2(r, c+1, i+1) || dfs2(r, c-1, i+1);

// un-mark
board[r][c] = word[i];

return result;
}

这更简洁，但对我来说更难理解。第一个版本 dfs() 做了一个循环，并在递归之前尽早放弃了邻居，这对我来说更有意义。 “如果邻居不好，就不要去那里。”第二个版本没有循环，因此它会在当前节点上执行所有检查。

我注意到的第一件事是，在涉及网格的大多数问题中，解决方案都涉及递归后的“取消标记”。为什么是这样？这是否仅适用于“单词搜索问题”等特定情况，您可能希望将来以不同的路径重新访问该节点？

哪个是正确的，dfs() 或 dfs2()？

https://repl.it/MSCw/0 以下是全部内容:

var dirs = [
  [0,1],  // r
  [1,0],  // d
  [0,-1], // u
  [-1,0], // l
];

var wsBoard = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
];

var exist = function(board, word, version) {
  for (var r = 0; r < board.length; r++) {
    for (var c = 0; c < board[0].length; c++) {
      if (board[r][c] === word[0])
        if (dfs(r, c, 0)) return true;
        // if (dfs2(r, c, 0)) return true;
    }
  }

  return false;

  function dfs(r, c, i) {
    console.log(`(${r},${c})\t${i}: ${word[i]}`);

    // goal
    if (i === word.length-1) return true;

    // mark
    board[r][c] = '#';

    // loop and recurse each neighbor
    for (var d of dirs) {
      var nr = r + d[0];
      var nc = c + d[1];

      // bail early if neighbor does not meet conditions
      if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue;  // neighbor is out of bounds
      if (board[nr][nc] === '#') continue;                                            // neighbor already visited
      if (board[nr][nc] !== word[i+1]) continue;                                      // neighbor does not meet goal

      console.log(board);

      // recursion
      var result = dfs(nr, nc, i+1);

      // un-mark
      board[r][c] = word[i];

      return result;
    }
  }

  function dfs2(r, c, i) {
    console.log(`(${r},${c})\t${i}: ${word[i]}`);

    // goal
    if (i === word.length) return true;

    // bail early if current does not meet conditions
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;  // current is out of bounds
    if (board[r][c] === '#') return false;                                          // current already visited
    if (board[r][c] !== word[i]) return false;                                      // current does not meet goal

    // mark
    board[r][c] = '#';

    console.log(board);

    // recursion
    var result = dfs2(r+1, c, i+1) || dfs2(r-1, c, i+1) || dfs2(r, c+1, i+1) || dfs2(r, c-1, i+1);

    // un-mark
    board[r][c] = word[i];

    return result;
  }
};

console.log(exist(wsBoard, 'ABCCED'));  // => true
console.log(exist(wsBoard, 'SEE'));     // => true
console.log(exist(wsBoard, 'ABCB'));    // => false

最佳答案

我相信尽管 dfs 和 dfs2 都基于相同的想法 dfs 有一个缺陷，它返回的结果是只探索第一条路!

看看这个例子，我试图在板中找到 FOO，很明显，它是第一列，但是你的实现返回 false

var dirs = [
  [0,1],  // r
  [1,0],  // d
  [0,-1], // u
  [-1,0], // l
];

var board = [
  ['F','O','X'],
  ['O',' ',' '],
  ['O',' ',' ']
];

var exist = function(word) {
  function dfs(r, c, i) {
    // mark
    board[r][c] = '#';

    // goal
    if (i === word.length-1) return true;

    // loop and recurse each neighbor
    for (var d of dirs) {
      var nr = r + d[0];
      var nc = c + d[1];

      // bail early if neighbor does not meet conditions
      if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue;  // neighbor is out of bounds
      if (board[nr][nc] === '#') continue;                                            // neighbor already visited
      if (board[nr][nc] !== word[i+1]) continue;                                      // neighbor does not meet goal

      // recursion
      var result = dfs(nr, nc, i+1);

      // un-mark
      board[r][c] = word[i];

      return result;
    }
  }
  for (var r = 0; r < board.length; r++) {
    for (var c = 0; c < board[0].length; c++) {
      if (board[r][c] === word[0]) {}
        if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

console.log(exist('FOO'))

问题是您的 for 循环将始终返回第一次递归的结果，要修复它，让我们将 result 移到循环之外，使其成为 false 并在找到有效路径后使其采用 true 的值。

var dirs = [
  [0,1],  // r
  [1,0],  // d
  [0,-1], // u
  [-1,0], // l
];

var board = [
  ['F','O','X'],
  ['O',' ',' '],
  ['O',' ',' ']
];

var exist = function(word) {
  function dfs(r, c, i) {
    // mark
    board[r][c] = '#';

    // goal
    if (i === word.length-1) return true;

    // assume that there's no valid path initially
    var result = false
    // loop and recurse each neighbor
    for (var d of dirs) {
      var nr = r + d[0];
      var nc = c + d[1];

      // bail early if neighbor does not meet conditions
      if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue;  // neighbor is out of bounds
      if (board[nr][nc] === '#') continue;                                            // neighbor already visited
      if (board[nr][nc] !== word[i+1]) continue;                                      // neighbor does not meet goal

      // recursion
      result = result || dfs(nr, nc, i+1);

    }

    // un-mark
    board[r][c] = word[i];
    
    return result;
  }
  for (var r = 0; r < board.length; r++) {
    for (var c = 0; c < board[0].length; c++) {
      if (board[r][c] === word[0]) {}
        if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

console.log(exist('FOO'))

如果我们查看 dfs2，唯一的区别是 for 循环是展开的，例如 

var result = false;
for (var dir in dirs) {
   // ...
   result = result || dfs(nr, nc, i+1)
}
return result;

// becomes

var result = dfs2(...) || dfs2(...) || ...

The first things that I noticed was that in most problems involving a grid, solutions involve "un-marking" after the recursion. Why is this?

在某些解决方案中，您实际上可能会改变您正在使用的对象，例如在另一个经典问题中，该问题是找到一个单词的所有排列，您可以通过递归地改变单词来解决它，在找到一个排列后下一次递归调用将使用不同的状态(这是不希望的)，此问题中的unmarking 概念被翻译成将单词转换为其先前状态的还原操作。

Which is correct, dfs() or dfs2()?

两者都是正确的(好吧，在 dfs 修复之后)，但是，dfs2 会递归到无效状态，例如越界单元格或不属于单词的单元格，就复杂性而言，这种额外的开销只是一个常数乘数，例如即使您想象从每个单元访问每个邻居，复杂度也是 O(4 * # rows * # columns)

关于javascript - DFS 矩阵的正确方法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46636146/

上一篇：python - 如何展开列表理解

下一篇：c# - 为什么 HashSet<T>.IntersectWith 的时间复杂度取决于相等比较器？

相关文章：

javascript - 云函数: Checking if email exists in users document in Firestore not working

javascript - ng-View 无法在单页应用程序中工作

javascript - Mongoose find 和 findOne 返回整个集合

python - 井字游戏和 Minimax AI

recursion - 调用此递归函数时如何避免堆栈溢出

javascript - 如何让我的 JQuery 作用于我的按钮而不是输入元素

algorithm - 大量设备/节点的距离计算

c - C语言中如何遍历双向链表中的n个元素？

algorithm - 如何从建筑物中扔出 2 个鸡蛋并用 ~c*sqrt(F) throws 找到 F 层？

java - 递归方法不遍历所有树节点

©2024 IT工具网  联系我们