我到目前为止使用的所有回溯算法都是基于递归的。但我没能找到任何证据证明回溯不能是非递归的。那么问题是,回溯算法是否总是使用递归?
发布于 2022-02-15 20:11:14
不,回溯可以不用递归完成。下面是一个例子:非递归回溯,使用堆栈
boolean solve(Node n) {
put node n on the stack;
while the stack is not empty {
if the node at the top of the stack is a leaf {
if it is a goal node, return true
else pop it off the stack
}
else {
if the node at the top of the stack has untried children
push the next untried child onto the stack
else pop the node off the stack
}
return false
}一个真实的例子
正如我所测试的,非递归解决方案的速度要快得多。我并不是说非递归解决方案总是更快,但它确实为性能优化提供了更大的灵活性(而不是保存整个调用堆栈,而是决定将什么放入堆栈中)。
https://stackoverflow.com/questions/46094082
复制相似问题