从回溯的角度解释BFS和DFS

Question

维基百科关于深度优先搜索：

深度优先搜索(DFS)是一种遍历或搜索树、树结构或图的算法.一个从根开始(在图例中选择某个节点作为根)，并在回溯之前尽可能地沿着每个分支进行探索。

，那么广度优先搜索是什么？

“一种选择起始节点、检查所有节点回溯、选择最短路径、选择相邻节点回溯、选择最短路径、由于连续回溯遍历每条路径而最终找到最优路径的算法。

find**'s Regex剪枝--回溯？**

回溯一词因其用途的多样性而混淆。UNIX的find修剪了一个用回溯方式解释的用户.Regex Buddy使用“灾难性回溯”一词，如果您不限制您的Regexes的范围。这似乎是一个被广泛使用的保护伞术语。所以：

1. 你是如何为图论定义“回溯”的？
2. 什么是“回溯”在广度优先搜索和深度优先搜索？

添加了

关于回溯的好定义和示例

1. 布鲁特力法
2. 斯泰尔曼(？)发明术语“依赖导向回溯”
3. 回溯与regex实例
4. 深度优先搜索定义。

Answer 1

这种混淆是因为回溯是在搜索过程中发生的事情，但它也指的是一种特定的问题解决技术，其中有大量的回溯。这样的程序被称为回溯者。

开车进入一个街区，总是在你看到的第一个拐弯处(假设没有循环)，直到你到达死胡同，这时你开车回到下一条没人去过的街道的交叉口。这是“第一种”回溯，它大致相当于这个词的口语化用法。

更具体的用法是指一种解决问题的策略，类似于深度优先搜索，但当它意识到不值得继续下去某个子树时，就会回溯。

换句话说--天真的DFS盲目地访问每个节点，直到达到目标。是的，它在叶节点上“回溯”。但是backtracker也会在无用的分支上回溯。一个例子是在Boggle板上搜索单词。每个瓷砖周围都是8个其他的，所以树是巨大的，天真的DFS可能会花费太长的时间。但是，当我们看到像"ZZQ“这样的组合时，我们可以安全地停止从这里搜索，因为添加更多的字母是不可能的。

我喜欢朱莉·泽伦斯基教授的讲座。她解决了8个皇后，一个sudoku难题，和一个数字替代谜使用回溯，一切都是很好的动画。编程摘要，第10课 编程摘要，讲座11

树是一个图，其中任意两个顶点之间只有一条路径。这消除了循环的可能性。当您搜索一个图时，通常会有一些逻辑来消除循环，所以行为是一样的。此外，对于有向图，您不能沿着“错误”的方向跟踪边。

据我所知，在Stallman的论文中，他们开发了一个逻辑系统，它不只是在查询上说“是”或“不是”，而是通过进行最少的更改来建议对不正确的查询进行修正。你可以看到回溯的第一个定义可能在哪里起作用。