hhh*_*hhh 10 graph breadth-first-search backtracking depth-first-search
关于深度优先搜索的维基百科:
深度优先搜索(DFS)是用于遍历或搜索树,树结构或图的算法.一个从根开始(在图形情况下选择一个节点作为根)并在回溯之前尽可能地沿着每个分支进行探索 .
那么什么是广度优先搜索？
"选择起始节点,检查所有节点回溯,选择最短路径,选择邻居节点回溯,选择最短路径,最终找到最佳路径的算法,因为由于连续回溯而遍历每条路径.
正则表达式find的修剪 - 回溯？
由于其使用的多样性,回溯一词令人困惑.UNIX find修剪SO用户解释了回溯.如果您不限制正则表达式的范围,Regex Buddy使用术语"灾难性回溯".它似乎是一个过于广泛使用的伞形术语.所以:
[添加]
关于回溯和示例的良好定义
joh*_*cip 23
混淆是因为回溯是在搜索过程中发生的事情,但它也指的是一种特定的问题解决技术,其中进行了大量的回溯.这些程序被称为后退漏斗.
图片开车进入一个街区,总是在你看到的第一个转弯处(让我们假设没有环路),直到你遇到死路,此时你会开车回到下一条未经检查过的街道的交叉路口.这是"第一种"回溯类型,它大致相当于该词的口语用法.
更具体的用法是指一种解决问题的策略,它类似于深度优先搜索,但当它意识到不值得继续使用某个子树时会回溯.
换句话说 - 一个天真的DFS盲目地访问每个节点,直到它到达目标.是的,它在叶子节点上"回溯".但是回溯也在无用的分支上回溯.一个例子是在Boggle板上搜索单词.每块瓷砖都被其他8块包围,所以树很大,天真的DFS可能需要很长时间.但是当我们看到像"ZZQ"这样的组合时,我们可以安全地停止从这一点开始搜索,因为添加更多的字母不会成为一个单词.
我很喜欢Julie Zelenski教授的这些讲座.她使用回溯解决了8个女王,数独谜题和数字替换谜题,一切都很好动画. 编程抽象,第10讲 编程抽象,第11讲
树是一个图形,其中任何两个顶点之间只有一条路径.这消除了循环的可能性.当您搜索图形时,通常会有一些逻辑来消除周期,因此行为是相同的.此外,使用有向图,您不能沿"错误"方向跟随边.
据我所知,在Stallman的论文中,他们开发了一个逻辑系统,它不仅对查询说"是"或"否",而且实际上通过进行最小数量的更改来修复错误查询.您可以看到第一个回溯定义可能发挥作用的地方.