回溯法与分支界限法

《回溯法与分支界限法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验6回溯法与分支界限法1回溯法C++代码#includeusingnamespacestd;/*判断是否可以在第row行（下标从0开始）放入下一个皇后，可以返回1，否则返回0*/intput_in(int*positions,introw){/*依次判断此皇后之前的所有皇后是否和要放入的皇后位置冲突*/for(inti=0;i

2、!=-(row-i)这两种情况可以合并为abs(a[row]-a[i])!=abs(row-i)。不在同一列可以表示为a[row]!=a[i]因为已经是一行放入一个皇后，所以不会有同一行冲突的情况。*/if(abs(positions[i]-positions[row])==abs(i-row)

3、

4、positions[i]==positions[row])return0;}return1;}/*递归解决N皇后问题，一次放入一个皇后，参数row表示当前要在第row行放入一个皇后*/intsovle_n_queens(int*p

5、ositions,intamount_queens,introw){staticintsolutions=0;//记录解的个数//这里的i表示列数，从第一列开始尝试for(inti=0;i

6、unt_queens-1){solutions++;//打印结果cout<<"第"<

7、olutions;}intmain(){//输入皇后的个数intamount_queens=NULL;cout<<"请输入皇后数量N，这表示棋盘有N*N个格子，并且有N个皇后"<>amount_queens;/*创建皇后位置数组，所表示意义为每个皇后放置在哪一列，行号为数组下标+1，这里不采用二维数组，因为二维数组会使数组的管理以及验证是否可以放入下一个皇后变得更麻烦*/int*positions=newint[amount_queens];//解决N皇后问题并打印解得个数cout<

8、ens<<"皇后问题共有"<

9、以要注意写递归程序的要点：1)合理定义递归程序的入口和出口2)每次递归，只是将问题的规模缩小，而问题性质是不变的。在这个算法中是一次求解棋盘中的一行达到规模缩小而问题性质不变。2分支界限法C++代码#include#include#includeusingnamespacestd;/*单个物品类，树中的节点和用户输入的物品都用这个类表示*/classstuff{public:intweight;//重量intvalue;//价值inttree_level;//在搜索树

10、中的层数intup_bound;//此节点的上界stuff(){}//空构造函数//重载构造函数stuff(intweightt,intvaluee,inttree_levell,intup_boundd):weight(weightt),value(valuee),tree_level(