1、Backtrackingbacktracking中文称做「回溯法」，穷举多维度数据的方法，可以想作是多维度的ExhaustiveSearch。大意是：把多维度数据看做是是一个多维向量（solutionvector），然后运用递回依序递回穷举各个维度的值，制作出所有可能的数据（solutionspace），并且在递回途中避免列举出不正确的数据。 1.backtrack ([ v1 ,..., vn ]) //[v1,...,vn]是多维度的向量2.{3. /*制作出了一组数据，并检验这组数据正不正确*/4. if ([ v1 ,..., vn ] is well
2、- generated )5. {6. if ([ v1 ,..., vn ] is a solution ) process solution ;7. return ;8. }9. 10. /*穷举这个维度的所有值，并递回到下一个维度*/11. for ( x = possible values of vn + 1 )1. backtrack ([ v1 ,..., vn , x ]);2.}3. 4.call backtrack ([]); //从第一个维度开始逐步穷举撰写程式时
3、，可用阵列来实作solutionvector的概念。 1.int solution [ MAX_DIMENSION ]; //solutionvector，多维度的向量2. 3.void backtrack ( int dimension )4.{5. /*制作出了一组数据，并检验这组数据正不正确*/6. if ( solution [] is well - generated )7. {8. check and record solution ;9. return ;10. }11. 12. /*穷
4、举这个维度的所有值，并递回到下一个维度*/13. for ( x = each value of current dimension )14. {15. solution [ dimension ]= x ;16. backtrack ( dimension + 1 );17. }18.}19. 20.int main ()21.{22. backtrack ( 0 ); //从第一个维度开始逐步列举23.}另外，当我们所需的数据只有唯一一组时，可以让程式提早结束。 1.int solution [
5、 MAX_DIMENSION ];2.bool finished = false ; //如果为true表示已经找到数据，可以结束。3. 4.void backtrack ( int dimension )5.{6. if ( solution [] is well - generated )7. {8. check and record solution ;9. if ( solution is found ) finished = true ; //找到数据了10. return
6、;11. }12. 13. for ( x = each value of current dimension )14. {15. solution [ dimension ]= x ;16. backtrack ( dimension + 1 );17. if ( finished ) return ; //提早结束，跳出这个递回18. }19.}附赠一张图片。画了很久。结合pruning回溯法会在递回途中避免列举出不正确的数据，其意义其实就等同于搜寻树的pruning技术。 1.i
7、nt solution [ MAX_DIMENSION ];2. 3.void backtrack ( int dimension )4.{5. /*pruning：在递回途中避免列举出不正确的数据*/6. if ( solution [] will NOT be a solution in the future ) return ;7. 8. if ( solution [] i
