搜索
回溯法应用一、课题内容和要求在人机对弈、决策问题、人工智能、组合数学等等一系列非数值问题的算法设计中，回溯法是经常采用的一种重要而有效的方法。回溯法是一种选优搜索法。按选择最优解的条件向前搜索，以达到目的。但每当搜索到某一步时，发现其达不到预期的效果，就退回一步重新选择。这种行不通就退回的技术称为回溯法。回溯法的逻辑思路可表示为一棵数，根节点是初始状态，没搜索到一个节点都有若干个可供选择的后续节点，没有任何能够达到目标的暗示，只有走着瞧，不行了就回溯到上一层节点，回复刚刚使用的参数，再走另一条路径，所以回溯法的本质是穷举与试探，找到从根节点到叶子节点的所有正确结果。八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。二、需求分析运用面向对象思想，将八皇后问题的解决放在一个类中来解决。“构造函数模块”用来实现数据的初始化。“主程序模块”，负责调用其他函数依次在一到八行放置皇后，并按一定规律调整皇后位置，求出八皇后问题的所有解，并输出到文件。“皇后放置模块”，在解决问题过程中，需要将“皇后”依次放置到第一、二、……、八行。该模块负责尝试在某一行放置一个“皇后”，放置成功返回一个“成功”值，说明当前皇后放置在某一个位置上可能存在“解”。否则失败的话，返回“失败”值，说明当前行无论怎样放置皇后，都得不到解，只有调整上面行的皇后的位置。“输出模块”，负责将某一种皇后放置的方法写到文件中以供查看。三、概要设计2输出模块：开始输出八行皇后的放置位置结束3Queen类中问题解决模块：开始标志位置为1标志位是否大于0能否在第“标志位行放置一个皇后”是返回解法数否结束此皇后是否位于第8行输出一种解法标志位减1（继续寻找）是是标志位减一（退一行）否标志位加1（继续往下1行寻找）否4皇后放置模块：（负责在某一行放置皇后）开始消除当前行及下一行以前皇后位置的影响当前皇后是否在第8列否皇后位置变为当前位置加1是否超过第8列是返回“失败”结束是否与前面的皇后有冲突否是是记录该皇后位置，将相应列、斜线占用返回“成功”5主类成员变量及函数原型声明：classQueen{private:intlocation[9];//location[i]（i大于，小于等于）表示在（i，location(i)）的位置放置了一个“皇后”boolLR[16];//LR[i]（i大于，小于等于）从左上角往右下角数第i条斜线上是否有皇后，true为真intlr_orgin[16];//lr_origin用以记录左上角往右下角数第i条斜线被哪一行的皇后占用，未被占用为0boolRL[16];//RL[i]（i大于，小于等于）从右上角往左下角数第i条斜线上是否有皇后，true为真intrl_orgin[16];//rl_origin用以记录从右上角往左下角数第i条斜线被哪一行的皇后占用，未被占用为0boolline[9];//line[i]（i大于，小于等于8）表示在第i列上是否有皇后，true为真intline_orgin[9];//line[i]（i大于，小于等于8）表示在第i列上被哪一行的皇后占用，未被占用为0intnum;//用以统计解的个数public:Queen();//构造函数实现数据的初始化boolmytry(inti);//测试第i行皇后的位置，成功返回true，失败返回false；intSolveProblem();//八皇后问题的解决voidResult();//输出结果，*8的样式显示，在皇后安放处显示一个Q};成员变量设计：数组location[9]用来记录一至八行各个皇后所在列的序号（location[0]不使用）。LR[16]负责记录从左上角往右下角数，一至十六条斜线是否被占用（即实现皇后间的相互影响）。由于回溯时需要消除已经放置的部分皇后产生的影响（即改变LR[16]数组的值），所以必须记录某一个值的改变是有哪一行的皇后引起的，否则无法知道哪些影响是该消除的，所以需要设计一个数组lr_origin[16]，他的元素与LR[16]一一对应，每当某一条斜线被占用时，先将LR的某一元素的值改变，同时再在lr_origin中相应元素中记录下此改变是由某一行引起的。数组RL[16]、rl_origin[16]道理相同，只不过是记录从右上角至左下角第i条斜线的使用情况。此外，某一列是否被占用，被哪一行的皇后占用，也需要记录下来，所以设计bool数组line[9]，和int型l数组ine_origin[9]。有了这些，就可以记录某一皇后放置的位置，及产生的影响，同时也可以在需要的时候将相应的影响消除，便于重新放置皇后。6成员函数设计：类的构造函数，实现数据的初始化。一个函数负责调用其他函数解决八皇后问题。由于八皇后问题需要不断尝试在某一行放置一个皇后，所以将这一动作也封装到一个函数中，用一个函数实现，第几行放置皇后就将几作为参数传进去。找到一种解法后需要输出结果，将结果的输出放置到一个函数中实现。四、详细设计1、类的设计具体解释见“概要设计”，不再重复类Queen（）的声明：classQueen{private:intlocation[9];//location[i]（i大于，小于等于）表示在（i，location(i)）的位置放置了一个“皇后”boolLR[16];//LR[i]（i大于，小于等于）从左上角往右下角数第i条斜线上是否有皇后，true为真intlr_orgin[16];boolRL[16];//RL[i]（i大于，小于等于）从右上角往左下角数第i条斜线上是否有皇后，true为真intrl_orgin[16];boolline[9];//line[i]（i大于，小于等于）表示在第i列上是否有皇后，true为真intline_orgin[9];intnum;//统计解法的数量public:Queen();boolmytry(inti);intSolveProblem();voidResult();};2、类Queen的构造函数主要负责将数据初始化，主要是几个数组，将其中的元素全部清零，用于统计方法数的num也置为零：Queen::Queen(){//构造函数实现数据的初始化num=0;intk;for(k=0;k=8;k++){location[k]=0;line[k]=false;line_orgin[k]=0;7}for(k=0;k=15;k++){LR[k]=false;lr_orgin[k]=0;RL[k]=false;rl_orgin[k]=0;}}3、八皇后问题解决函数。初始将8个皇后都放在棋盘的外列，即数组location的值全为0。然后从第一行开始放置皇后，每一行又从第一列开始扫描。如果在第flag行找到了合适位置，则将其位置存储到location[flag]中，同时将相应的列、斜线置为“被占用”状态。然后看下一行，即flag++，如果在找到了合适位置，则存入数组location[flag]中，如果没有合适的位置，那就说明上一行皇后的位置不能产生解。此时，就应该重新调整上一行（即flag--）皇后的位置，调整过后再继续往下放置皇后，（即回溯）。每当第8行成功放置了一个皇后就找到了一个“解”，输出之。当全部的可能都试过以后，就求出了八皇后问题的全部解：intQueen::SolveProblem(){//八皇后问题的解决intflag;//flag作为标志位，表示当前第flag行进行尝试，看可不可以放置一个皇后intk;flag=1;//从第一行开始尝试while(flag0){if(mytry(flag)==true)//如果在第flag行可以找到合适的位置放置“皇后”{if(flag==8){num++;//当前是第行皇后找到合适的位置，解法数加一，输出结果Result();flag--;//标志位后移一位，即下次继续调整上一行皇后的位置}else{flag++;//不是最后一行，则flag加一，继续找下一行的皇后的位置}}else{flag--;//找不到就把flag减一，即下次调整上一行皇后的位置8}}returnnum;}4、在第i行放置一个皇后函数。上一步可能是在i-1行成功放置了一个皇后，也有可能是在i+1行放置皇后失败，“回溯”到第i行。所以，如果i+1行放置过皇后,需要将i+1行皇后产生的影响全部消除，然后再尝试在第i放置皇后。如果当前行皇后的位置已经在第八列，则直接返回“失败”。否则，继续尝试。将location[i]的值不断加1(当然控制在小于等于八)，检查该新的皇后的位置，该列是否被占用，所在的斜线上是否已经放置过皇后。如果有冲突，则继续检查下一列，如果无冲突，则将皇后位置固定，将该列、所在两条斜线置为“被占用”状态，记录下被第i行占用，返回“成功”：boolQueen::mytry(inti){//测试第i行皇后的位置，成功返回true，失败返回false；intk;if((i+1)=8){location[i+1]=0;}for(k=0;k=8;k++){if(line_orgin[k]==i||line_orgin[k]==i+1)//i行及以后i+1行皇后放置产生的影响全部消除{line_orgin[k]=0;line[k]=false;}}for(k=0;k=15;k++){if(rl_orgin[k]==i||rl_orgin[k]==i+1)//i行及以后i+1行皇后放置在RL斜线上产生的影响全部消除{rl_orgin[k]=0;RL[k]=false;}}for(k=0;k=15;k++){if(lr_orgin[k]==i||lr_orgin[k]==i+1)//i行及以后i+1行皇后放置在LR斜线上产生的影响全部消除9{lr_orgin[k]=0;LR[k]=false;}}if(location[i]==8)//如果当前行皇后的位置在最后一列，则放弃往后尝试，直接返回失败{returnfalse;}for(++location[i];location[i]=8;location[i]++){if((line[location[i]]==0)&&(LR[i+location[i]-1]==false)&&(RL[i-location[i]+8]==false))//在i行，location[i]列可以放置皇后{line[location[i]]=1;//location[i]列标记为已占用line_orgin[location[i]]=i;//location[i]列被i行的皇后占用LR[i+location[i]-1]=true;//从左上往右下角第i+location[i]-1条斜线被标记为占用lr_orgin[i+location[i]-1]=i;//从左上往右下角第i+location[i]-1条斜线被标记被第i行占用RL[i-location[i]+8]=true;//从右上往左下角第i-location[i]+8条斜线被标记为占用rl_orgin[i-location[i]+8]=i;//从右上往左下角第i-location[i]+8条斜线被标记被第i行占用returntrue;}}returnfalse;}5、结果输出函数，结果保存在location数组中，为了便于查看，将结果写入到文件“result.txt”中，当然，可以进行适当的格式控制，在8*8的格子中，若未放置皇后显示“_”，反之，显示“Q”：voidQueen::Result(){//输出结果，8*8的样式显示，在皇后安放处显示一个Qintj,k;ofstreamfout(result.txt,ios::app);10fout解法num:endl;for(j=1;j=8;j++){for(k=1;klo