词条 | 回朔算法 |
释义 | 在程序设计中,有这样一类问题:求一类解,或求全部解,或求最优解的问题(例如八皇后问题),不是根据某种确定的算法设计法则,而是利用试探和回朔的搜索技术求解. 回朔还是设计递归算法的重要方法,其求解过程实质:是一个先序遍历一棵"状态树"但是这棵树不是在遍历前预先建立的,而是隐含在遍历过程中. 为了应用回朔,所求的解必须能表示成一个n元组(x1,x2,…,xn),其中xi是取自某个有穷集si.下面给出n皇后的程序代码,给出代码前先描述问题:在一个n×n的棋盘上放置n个皇后,且使得每两个皇后之间不能相互"攻击"也就是使得每两个不在同一行,同一列及同一斜角线.(经典问题八皇后问题) #include<iostream.h> #include<math.h> int sum=0;//用于统计解的个数 int n;//表示皇后的个数 int *x;//解向量 bool place(int k)//判断是否能放置 { //cout<<"begin place"; for(int j=1;j<k;j++)//若j==k则同行 if(abs(k-j)==abs(x[j]-x[k])||x[j]==x[k])//abs(k-j)==abs(x[j]-x[k])表示在斜对角线 //x[j]==x[k]表示在同一列 return false; return true; } void backtract_queen(int t) { if(t>n) {//一次求解完成,计数器加一,并将该组解输出 sum++; for(int i=1;i<=n;i++) cout<<x<<" "; cout<<endl; } else for(int i=1;i<=n;i++) { x[t]=i; if(place(t)) backtract(t+1);//递归调用 } } void main() { cout<<"input the number of queen:"; cin>>n; x=new int[n]; backtract_queen(1); cout<<"sum="<<sum<<endl; cout<<"edn\"; } |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。