算法5

17学年—18学年第1学期算法设计与实践实验报告专业名称：数字媒体技术课程名称：算法设计与实践一、实验题目：5.8将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。设B={1,2,…,n}是n块电路板的集合，L={N1,N2,…,Nm}是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是x[i]。x所确定的电路板排列Density(x)密度定义为跨越相邻电路板插槽的最大连线数。例：如图，设n=8,m=5，给定n块电路板及其m个连接块：B={1,2,3,4,5,6,7,8}，N1={4,5,6}，N2={2,3}，N3={1,3}，N4={3,6}，N5={7,8};其中两个可能的排列如图所示，则该电路板排列的密度分别是2，3。左上图中，跨越插槽2和3,4和5，以及插槽5和6的连线数均为2。插槽6和7之间无跨越连线。其余插槽之间只有1条跨越连线。在设计机箱时，插槽一侧的布线间隙由电路板的排列的密度确定。因此，电路板排列问题要求对于给定的电路板连接条件(连接块)，确定电路板的最佳排列，使其具有最小密度。5.11卫兵布置问题：一个博物馆由排成m*n个矩形阵列的陈列室组成，需要在陈列室中设立哨位，每个哨位上除的哨兵除了可以监视自己所在陈列室外，还可以监视他上、下、左、四个陈列室，试给出一个最佳哨位安排方法，使得所有陈列室都在监视之下，但使用的哨兵最少。二、实验分析：5.8电路板排列问题是NP难问题，因此不大可能找到解此问题的多项式时间算法。考虑采用回溯法系统的搜索问题解空间的排列树，找出电路板的最佳排列。设用数组B表示输入B[i][j]的值为1当且仅当电路板i在连接块Nj中。设total[j]是连接块Nj中的电路板数。对于电路板的部分排列x[1:i]，设now[j]是x[1:i]中所包含的Nj中的电路板数。由此可知，连接块Nj的连线跨越插槽i和i+1当且仅当now[j]0且now[j]！=total[j]。用这个条件来计算插槽i和i+1间的连线密度。在解空间排列树的每个节点处，算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。因此计算密度所消耗的总计算时间为O(mn!)。另外，生成排列树需要O(n!)时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd=0。因此最优解被更新的额次数为O(m)。更新最优解需要O(mn)时间。综上，解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn!)。5.11本题的解是一个nm的0-1矩阵jiX,，1,jiX当且仅当陈列室（i,j）有哨兵。初始令所有的1,jiX，mi,,2,1，nj,,2,1.算法从（1,1）开始直到（m,n）为止，搜索树是二叉树，有nm层.每个结点对应一个陈列室位置.如果令0,jiX，取消（i,j）位置的哨兵，进入左子树；否则进入右子树。在进入左子树时需要检查房间被监视的情况。即当取消（i,j）位置的哨兵时，此位置及其上、下、左、右位置是否被监视。如果有不被监视的情况出现，该分支不在搜索，最坏情况下的时间复杂度为)2(nmO.三、实验代码：5.8//电路板排列问题回溯法求解#includestdafx.h#includeiostream#includefstreamusingnamespacestd;ifstreamfin(5d11.txt);classBoard{friendintArrangement(int**B,intn,intm,intbestx[]);private:voidBacktrack(inti,intcd);intn,//电路板数m,//连接板数*x,//当前解*bestx,//当前最优解bestd,//当前最优密度*total,//total[j]=连接块j的电路板数*now,//now[j]=当前解中所含连接块j的电路板数**B;//连接块数组};templateclassTypeinlinevoidSwap(Type&a,Type&b);intArrangement(int**B,intn,intm,intbestx[]);intmain(){intm=5,n=8;intbestx[9];//B={1,2,3,4,5,6,7,8}//N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}coutm=m,n=nendl;coutN1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}endl;cout二维数组B如下：endl;//构造Bint**B=newint*[n+1];for(inti=1;i=n;i++){B[i]=newint[m+1];}for(inti=1;i=n;i++){for(intj=1;j=m;j++){finB[i][j];coutB[i][j];}coutendl;}cout当前最优密度为:Arrangement(B,n,m,bestx)endl;cout最优排列为：endl;for(inti=1;i=n;i++){coutbestx[i];}coutendl;for(inti=1;i=n;i++){delete[]B[i];}delete[]B;return0;}voidBoard::Backtrack(inti,intcd)//回溯法搜索排列树{if(i==n){for(intj=1;j=n;j++){bestx[j]=x[j];}bestd=cd;}else{for(intj=i;j=n;j++){//选择x[j]为下一块电路板intld=0;for(intk=1;k=m;k++){now[k]+=B[x[j]][k];if(now[k]0&&total[k]!=now[k]){ld++;}}//更新ldif(cdld){ld=cd;}if(ldbestd)//搜索子树{Swap(x[i],x[j]);Backtrack(i+1,ld);Swap(x[i],x[j]);//恢复状态for(intk=1;k=m;k++){now[k]-=B[x[j]][k];}}}}}intArrangement(int**B,intn,intm,intbestx[]){BoardX;//初始化XX.x=newint[n+1];X.total=newint[m+1];X.now=newint[m+1];X.B=B;X.n=n;X.m=m;X.bestx=bestx;X.bestd=m+1;//初始化total和nowfor(inti=1;i=m;i++){X.total[i]=0;X.now[i]=0;}//初始化x为单位排列并计算totalfor(inti=1;i=n;i++){X.x[i]=i;for(intj=1;j=m;j++){X.total[j]+=B[i][j];}}//回溯搜索X.Backtrack(1,0);delete[]X.x;delete[]X.total;delete[]X.now;returnX.bestd;}templateclassTypeinlinevoidSwap(Type&a,Type&b){Typetemp=a;a=b;b=temp;}5.11#includefstream#includeiostreamusingnamespacestd;ifstreamfin(input.txt);ofstreamfout(output.txt);ofstreamtestout(testout.txt);classExhibit_hall{friendvoidSetrobot(int,int);private:voidset(inti,intj,inta[]);//安排哨兵voidrecover(inti,intj,inta[]);voidBacktrack(inti,intj);voidGreedySearch();//贪婪搜索intsearch(inti,intj);//搜索在a[i][j]安排哨兵人时它所监督未被监督的陈列室个数voidset(inti,intj);intm,n;//陈列馆的行数,列数intmn;//陈列室个数intg_num;//陈列室中已被监视的个数intnum;//当前哨兵个数intnum1;//用于贪心搜索中哨兵的个数int**x;//当前解intbestn;//当前最优解的个数int**bestx;//当前最优解};voidExhibit_hall::set(inti,intj,inta[])//x[][]为1表示此房间已放置了一个哨兵，为2表示此房间已被监视{num++;a[0]=x[i][j];if(a[0]==0)g_num++;//若此陈列室未被监视，则此时已被监视g_num++x[i][j]=1;//此位置放置了一个哨兵if(x[i-1][j]==0){a[1]=1;x[i-1][j]=2;g_num++;}//若上方未被监视,则此时设置未已被监视if(x[i][j+1]==0){a[2]=1;x[i][j+1]=2;g_num++;}if(x[i+1][j]==0){a[3]=1;x[i+1][j]=2;g_num++;}if(x[i][j-1]==0){a[4]=1;x[i][j-1]=2;g_num++;}}voidExhibit_hall::recover(inti,intj,inta[])//撤消哨兵{num--;x[i][j]=a[0];if(a[0]==0)g_num--;if(a[1]){x[i-1][j]=0;g_num--;}if(a[2]){x[i][j+1]=0;g_num--;}if(a[3]){x[i+1][j]=0;g_num--;}if(a[4]){x[i][j-1]=0;g_num--;}a[0]=0;a[1]=0;a[2]=0;a[3]=0;a[4]=0;}voidExhibit_hall::Backtrack(inti,intj)//回溯{if(im){if(numbestn){for(intk=1;km+1;k++)for(intl=1;ln+1;l++)bestx[k][l]=x[k][l];bestn=num;}return;}if(num+(mn-g_num)/5=bestn)return;//当此陈列室已被监视，则没必要在此陈列室安排哨兵//因为x[i+1][j+1]放置一机器人优于此处哨兵if(x[i][j]!=0)Backtrack(i+j/n,j%n+1);//在此陈列室被监视else{inta[5]={0};if(im)//在此陈列室下面安排哨兵监视此陈列室{set(i+1,j,a);Backtrack(i,j);recover(i+1,j,a);}if((jn)&&(x[i][j+1]==0||x[i][j+2]==0))//在此陈列室右边安排哨兵监视此陈列室{set(i,j+1,a);Backtrack(i,j);recover(i,j+1,a);}if(x[i+1][j]==0&&x[i][j+1]==0)//在此陈列室安排哨兵{set(i,j,a);Backtrack(i,j);recover(i,j,a);}}}intExhibit_hall::search(inti,intj){if(i==m+1||j==n+1)return0;intcount=0;if(x[i][j]==0)count++;if(x[i-1][j]==0)count++;if(x[i][j+1]==0)count++;if(x[i+