algorithm - 为什么 DFS 不检查选择用于开发的节点的子节点的目标状态

Question

抱歉，如果我的语法还不够完美，英语不是我的母语。

如果我理解正确，DFS 仅在节点被选择用于开发时而不是在节点生成时才对节点进行目标测试。这对我来说似乎很奇怪，因为在 DFS 选择一个节点进行开发之后，它无论如何都会将该节点的所有子节点添加到打开列表中。在这样做的同时，为什么不检查它的一个 child 是否是目标状态，如果是这样，DFS 可以返回一个解决方案并终止？生成目标状态后继续在更深层次上搜索似乎是在浪费大量时间，我错了吗？

非常感谢!

Answer 1

不，你没看错，当然如果你在当前节点的邻居(你的措辞中的 child )中找到目的地，你可以终止它。

但是，由于两个原因，我会坚持“标准”实现:(只是我个人的顾虑)

1. 更容易实现，更高可读性，例如，你可能想在到达目的地时做一些事情，然后以标准方式与你的方式相比，伪代码就像

//The way I like to implement
void dfs(int x){
  if(x is destination){
     do_something(); return;
  }
  mark x visited
  foreach x's unvisited neighbor{
      dfs(x's neighbor)
  }
}
          
//The way you suggest to implement
void dfs(int x){
  mark x visited
  foreach x's unvisited neighbor{
      if(x's neighbor is destination){
         do_something(); return;
      }
      dfs(x's neighbor)
  }
}

我只是认为，由于 DFS 是基于递归的，并且根据我的理解，通过将基本情况检查从 FOR 循环中移出，将其放在函数的第一位是一种更“类似递归”的实现。

此外，如果 do_something() 是一项相当复杂的任务，如果将检查和处理放在 For 循环中，代码可能会变得困惑(可读性问题)

1. 时间复杂度是一样的 你是对的，它可以节省很多递归级别，取决于节点横向的顺序。

   但是，为了节省时间，是否值得放弃上面提到的可读性？我不这么认为。

   由于时间复杂度相同，只要每个节点最多被访问一次，复杂度就是O(N+M)，其中N是节点数，M是边数

   因此，不值得冒险编写一些乱七八糟的代码来节省一般来说可以忽略不计的时间。