backtracking算法.docx

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