解释BFS和DFS在回溯

Question

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

深度优先搜索（DFS）是一种 算法遍历或搜索 一棵树，树结构或图形。其中一个 从根开始（选择一些 节点作为图例中的根） 并在回溯之前尽可能沿着每个分支探索 。

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

“那些选择起始 节点的算法，检查所有节点回溯， 选择最短的路径，选择邻居节点回溯， 选择最短的路径，最后 发现，因为最佳路径的 遍历每个路径由于连续 回溯。

正则表达式find的修剪 - 回溯？

术语回溯由于其多种用途而混淆。 UNIX的find修剪一个SO用户，用回溯来解释。如果你不限制Regexes的范围，Regex Buddy使用术语“灾难性的回溯”。这似乎是一个过于广泛使用的总称。所以：

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

[新增]

约回溯良好定义和例子

1. The Brute-force method
2. Stallman的（？）发明了长期"dependency-directed backtracking"
3. 回溯和regex例如
4. Depth First Search definition.

Answer 1

混淆的来源，因为回溯一些搜索过程中发生，但它也指的是一个具体的解决问题的技术，其中很多回溯的完成。这样的程序被称为回溯。

驾驶车辆进入附近的图片，总是先看到第一个回合（让我们假设没有回路），直到你死亡，然后开车回到下一个未被访问的街道的交叉点。这是“第一”类型的回溯，这大致相当于该词的口语使用。

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

换句话说 - 一个天真的DFS会盲目地访问每个节点，直到达到目标。是的，它在叶节点上“回溯”。但一个回溯追踪器也回溯在无用的分支。其中一个例子是在Boggle董事会搜寻文字。每个瓷砖被8个其他瓷砖包围，所以树很大，天真的DFS可能需要很长时间。但是当我们看到像“ZZQ”这样的组合时，我们可以安全地停止从这一点开始搜索，因为添加更多的字母不会成为一个单词。

我喜欢Julie Zelenski教授的这些讲座。她解决了8个皇后，一个数独谜题和一个使用回溯的数字替代谜题，并且一切都很好地动画。 Programming Abstractions, Lecture 10 Programming Abstractions, Lecture 11

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

从我所知道的，在Stallman论文中，他们开发了一个逻辑系统，它不仅在查询中表示“是”或“否”，而且通过进行最小数量的更改建议修正错误查询。你可以看到回溯的第一个定义可能会发挥作用。