程序设计综合实践课件-回溯法 - 八皇后问题

三、回溯法

回溯法（Backtracking）又称试探-回溯法，也是一种重要的算法设计方法。它在求解问题时需要向前搜索很多步，以达到解题目标；问题可以有多个答案，每一步向前搜索时，都可能有很多选项，在当时状态下无法确定哪个选项是问题答案的一部分，这一步的多个选项都可能是某个答案中的正确选择，也可能事后确定这一步的所有选项都不是任何答案中的正确选择，因此，只能先试探选择这一步的某个选项，前进一步，继续试探向前搜索。在向前试探搜索过程中，当探索到某一步时，发现原先选择并不能达到目标，或者继续向前试探可能获取的答案无法更优时，就停止继续向前搜索，退回一步，重新试探选择没有试探过的选项，继续向前试探搜索。这种向前试探，走不通就回溯、再走其它未走路径的技术称为回溯法，或试探-回溯法。特别需要注意，回溯时应该恢复到前一次选择前状态，不能影响后面的试探-回溯。1

当试探完所有步，获得问题的一个答案时，如果需要寻求更多答案或迭代最佳答案，也可以退回一步，继续回溯，以获得更多答案或迭代最佳答案，直到退回到最初出发点，试探-回溯完成，确定问题所有答案、迭代最佳答案或确定问题无答案。当试探完所有步，获得问题的一个答案并且不需要寻求更多答案时，可以直接结束试探-回溯过程。2

把试探-回溯过程中每一步的状态作为一个结点，出发状态结点为根结点。当前状态中试探选择某一个选项后进入下一个状态，这两个状态结点间形成父子关系，这样，试探-回溯过程中所有的状态结点构成一个树，称为状态空间树，参见下面小节图2.4。树根结点是开始出发时状态结点，搜索过程中获得问题答案的状态结点是叶子结点。高度为h的满二叉树结点数为，搜索完满二叉树的算法时间复杂性也是，因此，在试探-回溯过程中，为提高算法的效率，应尽量优化，减去不必要树枝，减少状态空间树的结点数。试探回溯法采用深度优先策略，一般情况下可以用递归函数实现回溯法，问题和必要的状态、答案用Problem描述，p->n表示问题的规模，CheckOk(p)表示检查目前的选择是否可行。回溯法框架如下：3boolBackTrace(Problem*p,inti)//试探第i步{if(已获得一组解){//试探完所有步，如i>p->nOutputSolution(p);returntrue;//输出一组解或迭代最优解}else{foreach(selection：p目前选项集)//循环试探所有选项{p试探本次selection选择;if(CheckOk(p))//本次选择是否可行{status=BackTrace(p,t+1);//进一步试探if(status&&只需求一组解)returntrue;}恢复p本次selection选择前状态，回溯}}returnfalse;}43.1八皇后问题5八皇后问题求解是试探回溯法的典型应用。八皇后问题：国际象棋棋盘中，位于同一行的两个皇后会相互攻击，位于同一列的两个皇后也会相互攻击，位于右上45度斜线的两个皇后也会相互攻击，位于左上135度斜线的两个皇后也会相互攻击，其它位置的两个皇后不会相互攻击。要求8乘8的棋盘上放满8个皇后，相互之间平安相处，这样的摆放方案有哪些？右图2.2是其中的一种摆放方案。八皇后问题可以推广到nxn的棋盘上摆放n个皇后问题，用试探-回溯法解决。图2.2八皇后问题示意图6图2.3四皇后试探搜索过程部分状态示意图

为简化过程，以n=4为例讲述摆放过程。显然，同一行只能摆放一个皇后，n个皇后只能位于n行。7图2.4四皇后试探-回溯状态空间树#defineMaxN20structS8Queen{intN;intiMatrixA[MaxN][MaxN];//棋盘矩阵，便于输出intiColPerRowA[MaxN];//每行皇后摆放列号，便于检查intiSolutionCount;};8//初始化问题voidInitProbelm(structS8Queen*pQueenProblem,intn);//打印一个解voidPrintSolution(structS8Queen*pQueenProblem);//试探第i个皇后摆放voidTry(structS8Queen*pQueenProblem,inti);//检查目前第i个皇后摆放是否okintCheckOk(structS8Queen*pQueenProblem,inti);9//初始化问题voidInitProbelm(structS8Queen*pQueenProblem,intn){pQueenProblem->N=n;inti,j;pQueenProblem->iSolutionCount=0;for(i=0;i<pQueenProblem->N;++i)for(j=0;j<pQueenProblem->N;++j)pQueenProblem->iMatrixA[i][j]=0;}10//打印一个解voidPrintSolution(structS8Queen*pQueenProblem){inti,j;printf("Solution%d:\n",pQueenProblem->iSolutionCount);for(i=0;i<pQueenProblem->N;++i){for(j=0;j<pQueenProblem->N;++j)printf("%1d",pQueenProblem->iMatrixA[i][j]);printf("\n");}printf("\n");}11//试探第i个皇后摆放voidTry(structS8Queen*pQueenProblem,inti){if(i>pQueenProblem->N){++pQueenProblem->iSolutionCount;PrintSolution(pQueenProblem);return;//继续回溯}

12（待续）intj;for(j=1;j<=pQueenProblem->N;++j){pQueenProblem->iMatrixA[i-1][j-1]=1;//试探摆放在j列pQueenProblem->iColPerRowA[i-1]=j;if(CheckOk(pQueenProblem,i))Try(pQueenProblem,i+1);//继续试探摆放下个皇后pQueenProblem->iMatrixA[i-1][j-1]=0;//恢复状态，回溯}}13//检查目前第i个皇后摆放是否okintCheckOk(structS8Queen*pQueenProblem,inti){intiQueenColNow=pQueenProblem->iColPerRowA[i-1];//当前行摆放皇后列号intiRow;for(iRow=1;iRow<i;++iRow){intiQueenCol=pQueenProblem->iColPerRowA[iRow-1];//iRow行已摆放皇后列号if(iQueenCol==iQueenColNow)return0;//同一列，有冲突if(iQueenCol+iRow==iQueenColNow+i)return0;//右上角已摆放皇后，有冲突if(iQueenCol-iRow==iQueenColNow-i)return0;//左上角已摆放皇后，有冲突}return1;//ok}14intmain(){intn;while(1){printf("请输入棋盘大小(4~20):\n");scanf("%d",&n);if(n<4||n>20)break;structS8QueentheQueenProbl