计算机算法分析与设计(第四版)习题算法分析部分详解(实验六)

参考代码实验六分支限界法//6-1、6-6项目VC++6.0测试通过//6-15项目VC2005测试通过//6-1最小长度电路板排列问题//头文件stdafx.h//stdafx.h:includefileforstandardsystemincludefiles,//orprojectspecificincludefilesthatareusedfrequently,but//arechangedinfrequently//#pragmaonce#defineWIN32_LEAN_AND_MEAN//Excluderarely-usedstufffromWindowsheaders#includestdio.h#includetchar.h//TODO:referenceadditionalheadersyourprogramrequireshere//sy61.cpp:Definestheentrypointfortheconsoleapplication.////Description://分支限界法6_1最小长度电路板排列问题//#includemy.h#includestdafx.h#includeiostream#includequeueusingnamespacestd;intn,m;//#includeOutOfBounds.h//定义节点类classBoardNode{参考代码friendintFIFOBoards(int**,int,int,int*&);//非类成员，可以访问私有成员的函数，最优序列查找public:operatorint()const{returncd;}//返回常数cdintlen();public:int*x,s,cd,*low,*high;//x表示当前节点的电路板排列，s表示当前节点排列好的电路板的数//表示当前节点的最大长度，low，high分别表当前节点表示每一个连接块的第一个，和最后一个电路板//的位置};//编写类的len()函数,求出当前节点的连接块长度的最大值intBoardNode::len(){inttmp=0;for(intk=1;k=m;k++)if(low[k]=n&&high[k]0&&tmphigh[k]-low[k])tmp=high[k]-low[k];returntmp;}intFIFIOBoards(int**B,intn,intm,int*&bestx)//n为电路板的数量，m为连接块的数量{//intbestd;queueBoardNodeq;//声明BoardNode类的节点队列qBoardNodeE;E.x=newint[n+1];//为数组指针x分配n+1个动态空间，存储当前的排列E.s=0;//最初时，排列好的电路板的数目为0E.cd=0;E.low=newint[m+1];//存储每个连接块的第一个电路板的位置E.high=newint[m+1];//存储每个连接块的最后一个电路板的位置for(inti=1;i=m;i++){E.high[i]=0;//初始化开始时的每个连接块的最后一个电路板的位置为0，表示连接块i还没有电路板放入E.x的排列中E.low[i]=n+1;//初始化开始时的每个连接块的第一个电路板的位置为n+1，表示连接块i还没有电路板放入E.x的排列中}for(i=1;i=n;i++)E.x[i]=i;//初始化E.x的排列为1，2,3.....nintbestd=n+1;//最优距离bestx=0;//记录当前最优排列do{if(E.s==n-1)//当已排列了n-1个时参考代码{//判断是否改变每个连接块的最后一个电路板的位置for(intj=1;j=m;j++)if(B[E.x[n]][j]&&nE.high[j])E.high[j]=n;intld=E.len();//存储当前节点的各连接块长度中的最大长度//如果当前的最大长度小于了n+1if(ldbestd){delete[]bestx;bestx=E.x;bestd=ld;//最优距离}elsedelete[]E.x;//删除分配给E.x的数组空间delete[]E.low;//删除分配给E.low的数组空间delete[]E.high;//删除分配给E.high的数组空间}else{intcurr=E.s+1;//rr记录现在应该排列第几个电路板for(inti=E.s+1;i=n;i++)//处理扩展节点下一层所有子节点{BoardNodeN;N.low=newint[m+1];//与if中的意思相同N.high=newint[m+1];for(intj=1;j=m;j++){N.low[j]=E.low[j];//将E.low[]中的值赋给N.low[]N.high[j]=E.high[j];if(B[E.x[i]][j]){if(currN.low[j])N.low[j]=curr;//若当前节点连接块j的第一个电路板的位置比现在正在排列的电路板的位置还小if(currN.high[j])N.high[j]=curr;}}N.cd=N.len();//如果，当前节点的最大长度小于了最优长度则：if(N.cdbestd){N.x=newint[n+1];N.s=E.s+1;参考代码for(intj=1;j=n;j++)N.x[j]=E.x[j];N.x[N.s]=E.x[i];//交换位置N.x[i]=E.x[N.s];//交换位置q.push(N);//将节点N加入队列中}else{delete[]N.low;delete[]N.high;}//printf(%d,bestd);}delete[]E.x;//当前扩展节点所有子节点均考虑，变成死结点}//try{if(!q.empty()){E=q.front();//取队列首节点作为扩展节点q.pop();}elsereturnbestd;//}//catch(OutOfBounds)//{//returnbestd;//}//printf(finish);}while(!q.empty());returnbestd;return1;}//测试voidmain(){//scanf(%d%d,&n,&m);cinnm;int**B=newint*[n+1];for(intt=0;t=n;t++)B[t]=newint[m+1];for(inti=1;i=n;i++)for(intj=1;j=m;j++)cinB[i][j];参考代码//scanf(%d,&B[i][j]);int*bestx=newint[n+1];intbestd=0;bestd=FIFIOBoards(B,n,m,bestx);printf(%d\n,bestd);for(i=1;i=n;i++){coutbestx[i];}coutendl;}//6-6经典n皇后问题//Description:经典n皇后问题广度优先建议n=14解空间为子集树//参考答案说排列树是不正确的，本例打印n*n棋盘的所有解，即放置方法#includeiostream#includefstream#includealgorithm#includefunctional#includequeueusingnamespacestd;//本例子直接输入棋盘大小，不用文件//ifstreamin(input.txt);//请在项目文件夹下新建一个input.txt//ofstreamout(output.txt);classNode{public:Node(intn){t=0;this-n=n;loc=newint[n+1];for(inti=0;i=n;++i){loc[i]=0;}}Node(constNode&other){this-t=other.t;this-n=other.n;this-loc=newint[n+1];for(inti=0;i=n;++i){this-loc[i]=other.loc[i];}}intt;//已放置t个皇后参考代码int*loc;//loc[1:t]intn;//共放置n个皇后boolcheckNext(intnext);voidprintQ();};boolNode::checkNext(intnext){inti;for(i=1;i=t;++i){if(loc[i]==next)//检测同列{returnfalse;}if(loc[i]-next==t+1-i)//检测反斜线行差==列差{returnfalse;}if(loc[i]-next==i-t-1)//检测正斜线{returnfalse;}}returntrue;}voidNode::printQ(){for(inti=1;i=n;++i){coutloc[i];}coutendl;}classQueen{public:intn;//n皇后intansNum;//对于n皇后解的个数Queen(intn){this-n=n;ansNum=0;}voidArrangQueen();};voidQueen::ArrangQueen(){queueNodeQ;Nodeini(n);//初始化参考代码Q.push(ini);while(!Q.empty()){Nodefather=Q.front();//取队列下一个节点Q.pop();if(father.t==n){father.printQ();++ansNum;}for(inti=1;i=n;++i)//一次性将当前扩展节点所有子节点考虑完，符合条件的插入队列{if(father.checkNext(i)){NodeChild(father);++Child.t;Child.loc[Child.t]=i;Q.push(Child);}}}}intmain(){//#defineincin//#defineoutcoutcout请输入棋盘大小n:;intn;cinn;//从文件中读入一个整数//for(intCase=1;Case=cases;++Case){//intn;//inn;QueenQ(n);Q.ArrangQueen();//outCase#Case:Q.ansNumendl;cout共Q.ansNum种放置皇后方法，如上所示。endl;//}return0;}//6-15排列空间树问题VC2005测试通过//stdafx.h头文件//stdafx.h:includefileforstandardsystemincludefiles,//orprojectspecificincludefilesthatareusedfrequently,but//arechangedinfrequently参考代码//#pragmaonce#defineWIN32_LEAN_AND_MEAN//Excluderarely-usedstufffromWindowsheaders#includestdio.h#includetchar.h//TODO:referenceadditionalheadersyourprogramrequireshere//头文件MinHeap2.h；最小堆实现#includeiostreamtemplateclassTypeclassGraph;templateclassTclassMinHeap{templateclassTypefriendclassGraph;public:MinHeap(intmaxheapsize=10);~MinHeap(){delete[]heap;}intSize()const{returncurrentsize;}TMax