算法之分支限界法实现.doc

《算法之分支限界法实现.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验5分支限界法实现一、实验目标：1. 熟悉分支限界法应用场景及实现的基本方法步骤；2. 学会分支限界法的实现方法和分析方法： 二、实验内容1.n后问题：编程计算当n=1到8时解的个数，分别利用回溯法和分支限界法实现，比较并分析你的算法效率。回溯法：代码：#include#includeusingnamespacestd;//法一：迭代回溯classQueen{friendintnQueen(int);private:boolPlace(intk);voidBacktrack(intt);intn;//皇后个数int*x;//当前解intsum

2、;//当前已找到的可行方案数};boolQueen::Place(intk){for(intj=1;j

3、

4、(x[j]==x[k]))returnfalse;}returntrue;}voidQueen::Backtrack(intt){if(t>n)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))Backtrack(t+1);}}intnQueen(intn){QueenX;//初始化XX.n=n;X.sum=0;int*p=newint[n+1];fo

5、r(inti=0;i<=n;i++)p[i]=0;X.x=p;X.Backtrack(1);delete[]p;returnX.sum;}intmain(){cout<<"共有"<#includeusingnamespacestd;classQueen{friendintnQueen(int);private:boolPlace(intk);voidredu(intt);intn;//皇后个数int*x;//当前

6、解intsum;//当前已找到的可行方案数};//剪枝函数//判断当前状态是否合理，即皇后会不会互相攻击boolQueen::Place(intk){for(intj=1;j

7、

8、(x[j]==x[k]))returnfalse;}//所有皇后都不会互相攻击returntrue;}intnQueen(intn){QueenX;//初始化XX.n=n;X.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++)p[i]=0;X.x=p;X.redu(1);delete[]p;r

9、eturnX.sum;}voidswap(int&a,int&b){intt=a;a=b;b=t;}voidQueen::redu(intt){if(t>n)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))redu(t+1);}}intmain(){cout<<"共有"<usi

10、ngnamespacestd;#definemaxint10000//n为节点个数，v为源节点，dist为源节点到其他节点距离数组，//prev为源节点到顶点i的最短路径上的前一个节点，c为个节点之间的距离数组voidDijkstra(intn,intv,intdist[],intprev[],int**c){//顶点集合Sbools[maxint];for(inti=1;i<=n;i++){//源节点到各节点的距离记录dist[i]=c[v][i];//S初始化为空s[i]=false;if(dist[i]==maxint)//不可达prev[i]=0;elseprev[i]

11、=v;}//源节点初始化dist[v]=0;s[v]=true;//核心算法for(inti=1;i