Wikipedia about Depth First Search:
深度优先搜索（DFS）是用于遍历或搜索树，树结构或图的算法 . 一个从根开始（在图形情况下选择一个节点作为根）并在回溯之前尽可能地沿着每个分支进行探索 .
So what is Breadth First Search?
“选择起始节点的算法，检查所有节点回溯，选择最短路径，选择邻居节点回溯，选择最短路径，最终找到最佳路径，因为由于连续回溯而遍历每条路径 .
Regex find's pruning -- backtracking?
由于其使用的多样性，回溯一词令人困惑 . UNIX的 find 修剪SO用户解释回溯 . 如果您不限制Regex的范围，Regex Buddy使用术语"catastrophic backtracking" . 它似乎是一个过于广泛使用的伞形术语 . 所以：
-
如何定义"backtracking"专门用于图论？
-
什么是"backtracking"在广度优先搜索和深度优先搜索？
[Added]
Good definitions about backtracking and examples
-
Stallman（？）发明的术语"dependency-directed backtracking"
-
回溯和regex示例
1 回答
混淆是因为回溯是在搜索过程中发生的事情，但它也指的是一种特定的问题解决技术，其中进行了大量的回溯 . 这些程序被称为反击者 .
图片开车进入一个街区，总是看到你看到的第一个转弯（让我们假设没有环路），直到你遇到死胡同，此时你会开车回到下一条未经检查的街道的交叉路口 . 这是“第一种”回溯类型，它大致相当于该词的口语用法 .
更具体的用法是指解决问题的策略，类似于深度优先搜索，但当它意识到不值得继续使用某个子树时会回溯 .
换句话说 - 一个天真的DFS盲目地访问每个节点，直到它到达目标 . 是的，它在叶子节点上是"backtracks" . 但是 backtracker 也在无用的分支上回溯 . 一个例子是在Boggle板上搜索单词 . 每个瓷砖被8个其他瓷砖包围，因此树很大，天真的DFS可能需要很长时间 . 但是当我们看到像"ZZQ,"这样的组合时，我们可以安全地停止从这一点开始搜索，因为添加更多的字母不会成为一个单词 .
我很喜欢Julie Zelenski教授的这些讲座 . 她使用回溯解决了8个女王，数独谜题和数字替换谜题，一切都很好动画 . Programming Abstractions, Lecture 10 Programming Abstractions, Lecture 11
树是一个图形，其中任何两个顶点之间只有一条路径 . 这消除了循环的可能性 . 当您搜索图形时，通常会有一些逻辑来消除周期，因此行为是相同的 . 此外，使用有向图，您不能沿“错误”方向跟随边 .
据我所知，在Stallman的论文中，他们开发了一个逻辑系统，它不仅对查询说“是”或“否”，而且实际上通过进行最小数量的更改来建议修复错误查询 . 您可以看到第一个回溯定义可能发挥作用的地方 .