递归与算法算法专题

《递归与算法算法专题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归与回溯算法专题ACM组吴国龙主要内容回溯法的基本思想回溯法的常用方法应用举例得分得分得十分是非得失发的十分飞一.基本思想：从问题的某一种可能出发,搜索从这种情况出发所能达到的所有可能,当这一条路走到"尽头"的时候,再倒回出发点,从另一个可能出发,继续搜索.这种不断"回溯"寻找解的方法,称作"回溯法".二.一般步骤1.定义一个解空间，它包含问题的解。2.利用适于搜索的方法组织解空间。3.利用深度优先法搜索解空间。4.利用限界函数避免移动到不可能产生解的子空间。回溯法基本思想与步骤回溯常用方法1.递归回溯法voidRBacktrack(int

2、k){for(每个x[k],使得x[k]∈T(x[0],x[1]…x[k-1])&&(Bk(x[0],x[1]…x[k]))){if((x[0],x[1]…x[k])是一个可行解)输出x[0],x[1]…x[k]；elseRBacktrack(k+1);}}2.迭代回溯法voidIBacktrack(intn){intk;while(k>=0){if(还有尚未检测的x[k]∈T(x[0],x[1]…x[k-1])&&(Bk(x[0],x[1]…x[k]))){if((x[0],x[1]…x[k])是一个可行解)输出x[0],x[1]…x[k]

3、；k++;}elsek--;}}在8×8格的棋盘上放置彼此不受攻击的8个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。8后问题等价于在8×8格的棋盘上放置8个皇后，任何2个皇后不放在同一行或同一列或同一斜线上，哪么一共有多少种解法呢？？1234567812345678QQQQQQQQ12345678应用举例8-皇后问题主要解法与思想问题分析:第一步定义问题的解空间这个问题解空间就是8个皇后在棋盘中的位置.第二步定义解空间的结构可以使用8*8的数组，但由于任意两个皇后都不能在同行，我们可以用数组下标表示行，数组

4、的值来表示皇后放的列，故可以简化为一个一维数组x[9]。第三步以深度优先的方式搜索解空间，并在搜索过程使用剪枝函数来剪枝根据条件:x[i]==x[k]判断处于同一列abs(k-i)==abs(x[k]-x[i]判断是否处于同一斜线解析代码如下：#include#includeusingnamespacestd;intx[9];intsum=1;voidprint(){//输出当前可能的解//cout<<"第"<

5、]<<"";cout<

6、

7、abs(k-i)==abs(x[k]-x[i]))//判断处于同一列或同一斜线returnfalse;}returntrue;}voidqueen(inti){//回溯尝试皇后位置,i为行数if(i>8){print();return;}for(intj=1;j<=8;j++){x[i]=j;if(canPlace(i))queen(i+1);}}i

8、ntmain(){//主函数queen(1);cout<<“共有可能解数为:”<