回溯和深度优先搜索有什么区别？ [英] What's the difference between backtracking and depth first search?

问题描述

回溯和深度优先搜索之间有什么区别？

What's the difference between backtracking and depth first search?

推荐答案

回溯是一种更通用的算法。

Backtracking is a more general purpose algorithm.

深度优先搜索是与搜索树结构相关的回溯的一种特殊形式。从Wikipedia：

Depth-First search is a specific form of backtracking related to searching tree structures. From Wikipedia:

一个从根开始（在图例中选择某个节点作为根），并沿着每个根尽可能地探索

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.

它使用回溯作为处理树的一部分，但仅限于树结构。

It uses backtracking as part of its means of working with a tree, but is limited to a tree structure.

回溯可用于可以消除部分域的任何类型的结构-无论它是否是逻辑树。 Wiki示例使用一个棋盘和一个特定的问题-您可以查看一个特定的动作，并消除它，然后回溯到下一个可能的动作，消除它，等等。

Backtracking, though, can be used on any type of structure where portions of the domain can be eliminated - whether or not it is a logical tree. The Wiki example uses a chessboard and a specific problem - you can look at a specific move, and eliminate it, then backtrack to the next possible move, eliminate it, etc.

这篇关于回溯和深度优先搜索有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！