用回溯来解释BFS和DFS [英] Explain BFS and DFS in terms of backtracking

问题描述

深度优先搜索（DFS）是一个$ b $的深度优先搜索：

b算法用于遍历或搜索
a树，树结构或图。一个
从根开始（在图例中选择一些
节点作为根节点）
，并且在回溯之前尽可能沿着每个分支探索
。

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

选择开始
节点，检查所有节点 backtracks ，
选择最短路径，选择邻居节点 backtracks ，
选择最短路径，最后
找到最佳路径，因为
遍历每条路径，因为连续的
回溯。

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

由于各种用法，回溯会造成混淆。UNIX的 find 修剪一个SO用户，用backtracking解释。Regex Buddy使用这个术语灾难性的回溯，如果你不限制你的正则表达式的范围这似乎是一个过于广泛使用的总称。所以：

1. 你如何为图论定义回溯？


2. 什么是回溯在广度优先搜索和深度优先搜索？

[新增]

有关回溯和示例的良好定义
$ b

1. 蛮力法


2. Stallman's（？）发明的术语依赖引导回溯


3. Backtracking和正则表达式示例


4. < a href =http://eom.springer.de/D/d110150.htm =nofollow noreferrer>深度优先搜索定义。

解决方案

混淆出现了，因为回溯是s在搜索过程中发生的事情，但它也指的是一个特定的问题解决技术，其中大量的回溯完成。这样的程序被称为backtrackers。

开车进入邻居，总是在你看到的第一个回合（让我们假设没有回路）直到你死亡，这点你开车回到下一个未访问的街道的交叉点。这是第一类型的回溯，这大致相当于单词的口语使用。

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

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

我喜欢这些Julie Zelenski教授讲座。她解决了8个皇后，一个数独谜题和一个使用回溯的数字替代谜题，并且一切都很好地动画。
编程抽象，第10讲
程序设计抽象第11讲

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

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

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:

1. How do you define "backtracking" specifically for Graph Theory?
2. What is "backtracking" in Breadth First Search and Depth First Search?

[Added]

Good definitions about backtracking and examples

1. The Brute-force method
2. Stallman's(?) invented term "dependency-directed backtracking"
3. Backtracking and regex example
4. Depth First Search definition.

解决方案

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.

这篇关于用回溯来解释BFS和DFS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！