关于深度优先搜索的维基百科：
深度优先搜索（DFS）是一种
遍历或搜索的算法
树、树结构或图。一
从根开始（选择一些
节点作为图例中的根）
并尽可能地探索回溯之前的每个分支。
那么什么是广度优先搜索呢？
“一种选择起始点的算法
节点，检查所有节点回溯,
选择最短路径，选择邻居节点回溯,
最终选择了最短路径
找到最优路径，因为
由于连续遍历每条路径
回溯。
Regex find的修剪——回溯？
回溯一词因其用途广泛而令人困惑。 UNIX 的find修剪 SO 用户用回溯来解释。如果您不限制正则表达式的范围，Regex Buddy 将使用术语“灾难性回溯”。这似乎是一个使用过于广泛的总括术语。所以：
- 您如何专门为图论定义“回溯”？
- 广度优先搜索和深度优先搜索中的“回溯”是什么？
[Added]
关于回溯的良好定义和示例
- 蛮力法 http://web.archive.org/web/20141109193758/http://web.cse.ohio-state.edu/%7Egurari/course/cis680/cis680Ch19.html
- 斯托曼（？）发明的术语“依赖定向回溯” http://web.archive.org/web/20130523233954/http://www.kerneltrap.org/node/4484
- 回溯和regex http://web.archive.org/web/20090517003722/http://kerneltrap.org/node/16028 example
- 深度优先搜索定义。 https://encyclopediaofmath.org/wiki/Depth-first_search
之所以会出现这种混乱，是因为回溯是在搜索过程中发生的事情，但它也指的是一种进行大量回溯的特定问题解决技术。此类程序称为回溯程序。
想象一下开车进入一个社区，总是在你看到的第一个转弯处（假设没有环路），直到你遇到死胡同，此时你开车回到下一条无人访问的街道的交叉路口。这是“第一种”回溯，大致相当于该词的口语用法。
更具体的用法是指类似于深度优先搜索的问题解决策略，但当它意识到不值得继续沿着某个子树向下时会回溯。
换句话说，天真的 DFS 会盲目地访问每个节点，直到达到目标。是的，它在叶节点上“回溯”。但一个回溯器也会在无用的分支上回溯。一个例子是在 Boggle 板上搜索单词。每个图块都被其他 8 个图块包围，因此树很大，并且简单的 DFS 可能会花费很长时间。但是，当我们看到像“ZZQ”这样的组合时，我们可以安全地从此时开始停止搜索，因为添加更多字母不会使其成为一个单词。
我喜欢朱莉·泽连斯基教授的这些讲座。她使用回溯法解决了 8 个皇后、一个数独谜题和一个数字替换谜题，并且所有内容都具有精美的动画效果。编程抽象，第 10 讲 http://www.youtube.com/watch?v=NdF1QDTRkck
编程抽象，第 11 讲 http://www.youtube.com/watch?v=p-gpaIGRCQI
树是一种图，其中任何两个顶点之间只有一条路径。这消除了循环的可能性。当您搜索图表时，您通常会有一些逻辑来消除循环，因此行为是相同的。此外，对于有向图，您不能沿着“错误”方向跟踪边。
据我所知，在斯托曼的论文中，他们开发了一个逻辑系统，它不仅对查询说“是”或“否”，而且实际上通过进行最少数量的更改来建议修复不正确的查询。您可以看到回溯的第一个定义可能会发挥作用。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
