6 Backtracking¶
基本性质
In backtracking, if different solution spaces have different sizes, start testing from the partial solution with the smallest space size would have a better chance to reduce the time cost.
答案
\(\textnormal{T}\)
As for backtracking, which of the following statement is incorrect?
\(\textnormal{A}\). Backtracking method is called "general problem solving method". It can systematically search all or any solutions of a problem
\(\textnormal{B}\). Backtracking is a systematic and jumping search algorithm
\(\textnormal{C}\). The backtracking method needs the queue structure to save the path from the root node to the current extension node
\(\textnormal{D}\). When generating any node in the solution space, the backtracking algorithm first determines whether the node may contain the solution of the problem. If it is sure not, it skips the search for the subtree whose root is the node and backtracks to the ancestor node layer by layer
答案
回溯方法通常使用栈结构（通常通过递归实现）来保存从根节点到当前扩展节点的路径，而不是队列结构。队列结构通常用于广度优先搜索算法，而回溯是一种深度优先搜索策略，故答案为 \(\textnormal{C}\)
温馨提示
回溯方法涉及跳跃回溯到祖先节点，所以可以算作是一种跳跃搜索算法。
回溯算法时间复杂度分析困难的原因
What makes the time complexity analysis of a backtracking algorithm very difficult is that the sizes of solution spaces may vary.
答案
\(\textnormal{F}\)
What makes the time complexity analysis of a backtracking algorithm very difficult is that the time taken to check if a partial solution satisfies the restriction is hard to estimate.
答案
\(\textnormal{F}\)
What makes the time complexity analysis of a backtracking algorithm very difficult is that the time taken to backtrack -- that is, to recover the previous state of a solution -- is hard to estimate.
答案
\(\textnormal{F}\)
What makes the time complexity analysis of a backtracking algorithm very difficult is that the number of solutions that do satisfy the restriction is hard to estimate.
答案
\(\textnormal{T}\)
回溯效率的决定因素
The efficiency of backtracking does not depend on which of the following factors?
\(\textnormal{A}\). Determining the time of solution space
\(\textnormal{B}\). The number of values that satisfy the display constraint
\(\textnormal{C}\). Time to calculate constraint function
\(\textnormal{D}\). The time to compute the bounded function
答案
显式约束直接定义了解空间的范围，约束函数决定了剪枝的效率，限界函数用于优化剪枝，均会影响回溯的效率，且回溯效率并不依赖于确定解空间的时间，故答案为 \(\textnormal{A}\)
The efficiency of backtracking does not depend on which of the following factors?
\(\textnormal{A}\). The time of producing x [k]
\(\textnormal{B}\). The number of x [k] satisfying explicit constraints
\(\textnormal{C}\). The form of solution space of the problem
\(\textnormal{D}\). The time of calculating the upper bound function bound
\(\textnormal{E}\). The number of x [k] satisfying the constraints of constraint function and upper bound function
\(\textnormal{F}\). Calculate the time of constraint function
答案
\(\textnormal{C}\)
\(N\) Queens
In the problem of \(N\) Queens, since the game tree contains \(N!\) leaves, the space complexity for solving the problem is \(\Omega(N!)\).
答案
解空间大小 \(≠\) 空间复杂度，\(N\) 皇后问题回溯法的空间复杂度为 \(O(N)\)，答案为 \(\textnormal{F}\)