Comment on page
Backtracking
Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.
Pseudo code for backtracking algorithm
Pick a starting point.
while(Problem is not solved)
For each path from the starting point.
check if selected path is safe, if yes select it
and make recursive call to rest of the problem
before which undo the current move.
End For
If none of the move works out, return false, NO SOLUTON.
Backtracking is a form of recursion.
The usual scenario is that you are faced with a number of options, and you must choose one of these. After you make your choice you will get a new set of options; just what set of options you get depends on what choice you made. This procedure is repeated over and over until you reach a final state. If you made a good sequence of choices, your final state is agoal state;if you didn't, it isn't.
From Harvard FAS Computer Science S-111:
Recursion Revisited; Recursive Backtracking
// n is the number of the variable that the current
// call of the method is responsible for
boolean findSolution(int n, possibly other params) {
if (found a solution) {
this.displaySolution();
return true;
}
// loop over possible values for the nth variable
for (val = first to last) {
if (this.isValid(val, n)) {
this.applyValue(val, n);
if (this.findSolution(n + 1, other params)) {
return true;
}
this.removeValue(val, n);
}
}
return false;
}
boolean findSolutions(int n, possibly other params) {
if (found a solution) {
this.displaySolution();
this.solutionsFound++;
return (this.solutionsFound >= this.target);
}
// loop over possible values for the nth variable
for (val = first to last) {
if (isValid(val, n)) {
this.applyValue(val, n);
if (this.findSolutions(n + 1, other params)) {
return true;
}
this.removeValue(val, n);
}
}
return false;
}
Backtracking 基本概念：
Backtracking（回溯算法）也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
应用技巧：
- 回溯法在用来求问题的 所有解 时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
- 而回溯法在用来求问题的 任一解 时，只要搜索到问题的一个解就可以结束。
Last modified 3yr ago