从回溯的角度解释BFS和DFS
关于深度优先搜索的维基百科：
深度优先搜索（DFS）是一种 遍历或搜索的算法 树、树结构或图。一 从根开始（选择一些 节点作为图例中的根） 并尽可能地探索 回溯之前的每个分支。
那么什么是广度优先搜索？
“选择起始点的算法 节点，检查所有节点回溯， 选择最短路径，选择邻居节点回溯， 最终选择了最短路径 找到最优路径，因为 由于连续遍历每条路径 回溯。
正则表达式find的修剪——回溯？
术语回溯由于其多种用途而令人困惑。 UNIX 的 find 修剪 SO 用户用回溯进行了解释。如果您不限制正则表达式的范围，Regex Buddy 将使用术语“灾难性回溯”。这似乎是一个使用过于广泛的总括术语。那么：
- 您如何专门为图论定义“回溯”？
- 广度优先搜索和深度优先搜索中的“回溯”是什么？
[已添加]
有关回溯的良好定义和示例
Wikipedia about Depth First Search:
Depth-first search (DFS) is an
algorithm for traversing or searching
a tree, tree structure, or graph. One
starts at the root (selecting some
node as the root in the graph case)
and explores as far as possible along
each branch before backtracking.
So what is Breadth First Search?
"an algorithm that choose a starting
node, checks all nodes backtracks,
chooses the shortest path, chose neighbour nodes backtracks,
chose the shortest path, finally
finds the optimal path because of
traversing each path due to continuous
backtracking.
Regex find's pruning -- backtracking?
The term backtracking confuses due to its variety of use. UNIX's find pruning an SO-user explained with backtracking. Regex Buddy uses the term "catastrophic backtracking" if you do not limit the scope of your Regexes. It seems to be a too widely used umbrella-term. So:
- How do you define "backtracking" specifically for Graph Theory?
- What is "backtracking" in Breadth First Search and Depth First Search?
[Added]
Good definitions about backtracking and examples
- The Brute-force method
- Stallman's(?) invented term "dependency-directed backtracking"
- Backtracking and regex example
- Depth First Search definition.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
之所以会出现这种混乱，是因为回溯是在搜索过程中发生的事情，但它也指的是一种进行大量回溯的特定问题解决技术。此类程序称为回溯程序。
想象一下开车进入一个社区，总是在你看到的第一个转弯处（假设没有环路），直到你遇到死胡同，此时你开车回到下一条无人访问的街道的交叉路口。这是“第一种”回溯，大致相当于该词的口语用法。
更具体的用法是指一种类似于深度优先搜索的问题解决策略，但当它意识到不值得继续沿着某个子树向下时会回溯。
换句话说，天真的 DFS 会盲目地访问每个节点，直到达到目标。是的，它在叶节点上“回溯”。但是回溯器也会在无用的分支上回溯。一个例子是在 Boggle 板上搜索单词。每个图块都被其他 8 个图块包围，因此树很大，并且简单的 DFS 可能会花费很长时间。但是，当我们看到像“ZZQ”这样的组合时，我们可以安全地从此时开始停止搜索，因为添加更多字母不会使其成为一个单词。
我喜欢朱莉·泽连斯基教授的这些讲座。她使用回溯法解决了 8 个皇后、一个数独谜题和一个数字替换谜题，并且所有内容都具有精美的动画效果。
编程抽象，讲座 10
编程抽象，讲座 11
树是任意两个顶点只有一个的图他们之间的路径。这消除了循环的可能性。当您搜索图表时，您通常会有一些逻辑来消除循环，因此行为是相同的。此外，对于有向图，您不能沿着“错误”方向跟踪边。
据我所知，在斯托曼的论文中，他们开发了一个逻辑系统，它不仅对查询说“是”或“否”，而且实际上通过进行最少数量的更改来建议修复不正确的查询。您可以看到回溯的第一个定义可能会发挥作用。
The confusion comes in because backtracking is something that happens during search, but it also refers to a specific problem-solving technique where a lot of backtracking is done. Such programs are called backtrackers.
Picture driving into a neighborhood, always taking the first turn you see (let's assume there are no loops) until you hit a dead end, at which point you drive back to the intersection of the next unvisited street. This the "first" kind of backtracking, and it's roughly equivalent to colloquial usage of the word.
The more specific usage refers to a problem-solving strategy that is similar to depth-first search but backtracks when it realizes that it's not worth continuing down some subtree.
Put another way -- a naive DFS blindly visits each node until it reaches the goal. Yes, it "backtracks" on leaf nodes. But a backtracker also backtracks on useless branches. One example is searching a Boggle board for words. Each tile is surrounded by 8 others, so the tree is huge, and naive DFS can take too long. But when we see a combination like "ZZQ," we can safely stop searching from this point, since adding more letters won't make that a word.
I love these lectures by Prof. Julie Zelenski. She solves 8 queens, a sudoku puzzle, and a number substitution puzzle using backtracking, and everything is nicely animated.
Programming Abstractions, Lecture 10
Programming Abstractions, Lecture 11
A tree is a graph where any two vertices only have one path between them. This eliminates the possibility of cycles. When you're searching a graph, you will usually have some logic to eliminate cycles anyway, so the behavior is the same. Also, with a directed graph, you can't follow edges in the "wrong" direction.
From what I can tell, in the Stallman paper they developed a logic system that doesn't just say "yes" or "no" on a query but actually suggests fixes for incorrect queries by making the smallest number of changes. You can kind of see where the first definition of backtracking might come into play.