algorithm - 回溯设计技术的通用定义

Question

我正在阅读 Anany Levtin 的 Introduction to Design and analysis of Algorithms 中的反向跟踪算法设计技术。

我很难理解回溯算法的通用定义并将其映射到 4 皇后问题。

For back-tracking algorithm design technique from a more general perspective, most backtracking algorithms fit the following description.

An output of a backtracking algorithm can be thought of as an n-tuple (x1, x2, x3,...,xn) where each coordinate xi is an element of some finite linearly ordered set Si. For example, for the n-queens problem, each Si is the set of integers 1 through n. The tuple may need to satisfy some additional constraints (e.g., the nonattacking requirments in the n-queens problem).

For example for 4 queen problem each Si is set {1, 2, 3, 4}

A back-tracking algorithm generates explicitly or implicityly, a state-space tree, its nodes represent partially constructed tuples with the first "i" coordinates defined by the earlier actions of the algorithm. If such a tuple (x1, x2, x3,.. xi) is not a solution, the algorithm finds the next element in Si+1 that is consistent with the values of (x1, x2, x3...xi) and the problems constraints and adds it to the tuple as its (i+1)st coordinate. If such an element doesnot exist, the algorithm backtracks to consider the next value of xi, and so on.

我对以上文字的问题是

1. 作者所说的“回溯算法显式或隐式生成状态空间树，其节点表示部分构造的元组，第一个“i”是什么意思 由算法的早期操作定义的坐标。如果这样的元组 (x1, x2, x3,.. xi) 不是解，算法会找到下一个元素 在 Si+1 中，与 (x1, x2, x3...xi) 的值和问题约束一致，并将其作为第 (i+1) 个坐标添加到元组中。"?

   具体来说，作者所说的算法在 Si+1 中找到下一个元素是什么意思？

   请用4皇后问题解释上述陈述。

2. 如果元素不存在算法回溯考虑下一个 xi 值？请用 4 皇后问题解释这句话。

谢谢!

Answer 1

这个关于回溯的解释确实很难理解，因为它使用了很多形式化的符号，而不是用于特定目的或证明。让我尝试以不太正式的方式用 4-queens 问题来解释它，这是一个很好的例子:

在回溯过程开始时，棋盘是空的。这是状态空间树的根。这个根有子节点，一个代表我们可以放置第一个皇后的每一种可能性。我们不是在进入下一层之前构造每个子节点(这将导致状态空间树的 BFS)，而是为第一个皇后选择一个可能的位置，从而构造一个子节点。从这个子节点，我们再次有多个选项来放置第二个皇后，所以我们选择一个，依此类推。

如果我们到达我们无法放置剩余女王的节点，我们回溯 - 我们上升一个级别到该节点父节点并检查是否还有我们尚未探索的可能性。如果是，我们通过创建相应的子节点来探索它们，如果不是，我们再次回溯，上升到另一个级别，直到我们找到问题的解决方案(放置所有皇后)或者我们扩展根节点的所有子节点并到达回溯操作期间的根节点 - 这意味着没有解决方案。