搜索与回溯算法(C++)

第五章搜索与回溯算法搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。递归回溯法算法框架[一]intSearch(intk){for(i=1;i=算符种数;i++)if(满足条件){保存结果if(到目的地)输出解;elseSearch(k+1);恢复：保存结果之前的状态{回溯一步}}}递归回溯法算法框架[二]intSearch(intk){if(到目的地)输出解;elsefor(i=1;i=算符种数;i++)if(满足条件){保存结果;Search(k+1);恢复：保存结果之前的状态{回溯一步}}}【例1】素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。【算法分析】非常明显，这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。【算法流程】1、数据初始化；2、递归填数：判断第i个数填入是否合法；A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能；【参考程序】#includecstdio#includeiostream#includecstdlib#includecmathusingnamespacestd;boolb[21]={0};inttotal=0,a[21]={0};intsearch(int);//回溯过程intprint();//输出方案boolpd(int,int);//判断素数intmain(){search(1);couttotalendl;//输出总方案数system(pause);}intsearch(intt){inti;for(i=1;i=20;i++)//有20个数可选if(pd(a[t-1],i)&&(!b[i]))//判断与前一个数是否构成素数及该数是否可用{a[t]=i;b[i]=1;if(t==20){if(pd(a[20],a[1]))print();}elsesearch(t+1);b[i]=0;}}intprint(){total++;couttotal;for(intj=1;j=20;j++)couta[j];coutendl;}boolpd(intx,inty){intk=2,i=x+y;while(k=sqrt(i)&&i%k!=0)k++;if(ksqrt(i))return1;elsereturn0;}【例2】设有n个整数的集合｛1,2,…,n｝，从中取出任意r个数进行排列（rn），试列出所有的排列。#includecstdio#includeiostream#includeiomanipusingnamespacestd;intnum=0,a[10001]={0},n,r;boolb[10001]={0};intsearch(int);//回溯过程intprint();//输出方案intmain(){coutinputn,r:;cinnr;search(1);coutnumber=numendl;//输出方案总数}intsearch(intk){inti;for(i=1;i=n;i++)if(!b[i])//判断i是否可用{a[k]=i;//保存结果b[i]=1;if(k==r)print();elsesearch(k+1);b[i]=0;}}intprint(){num++;for(inti=1;i=r;i++)coutsetw(3)a[i];coutendl;}【例3】任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。当n=7共14种拆分方法：7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4total=14【参考程序】#includecstdio#includeiostream#includecstdlibusingnamespacestd;inta[10001]={1},n,total;intsearch(int,int);intprint(int);intmain(){cinn;search(n,1);//将要拆分的数n传递给scouttotal=totalendl;//输出拆分的方案数system(pause);}intsearch(ints,intt){inti;for(i=a[t-1];i=s;i++)if(in)//当前数i要大于等于前1位数，且不过n{a[t]=i;//保存当前拆分的数is-=i;//s减去数i，s的值将继续拆分if(s==0)print(t);//当s=0时，拆分结束输出结果elsesearch(s,t+1);//当s0时，继续递归s+=i;//回溯：加上拆分的数，以便产分所有可能的拆分}}intprint(intt){coutn=;for(inti=1;i=t-1;i++)//输出一种拆分方案couta[i]+;couta[t]endl;total++;//方案数累加1}【例4】八皇后问题：要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）放置第ｉ个(行)皇后的算法为：intsearch(i)；{intj;for(第i个皇后的位置j=1;j=8;j++)//在本行的8列中去试if(本行本列允许放置皇后){放置第i个皇后；对放置皇后的位置进行标记；if(i==8)输出//已经放完个皇后elsesearch(i+1)；//放置第i+1个皇后对放置皇后的位置释放标记，尝试下一个位置是否可行；}}【算法分析】显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在／斜线上的行列值之和相同；如果同在＼斜线上的行列值之差相同；从下图可验证：１２３４５６７８１２３４５６７８｜／＼｜／＼｜／＼｜／－－－▲－－－－／｜＼／｜＼／｜＼考虑每行有且仅有一个皇后，设一维数组Ａ[1..8]表示皇后的放置：第ｉ行皇后放在第ｊ列，用Ａ[i]＝j来表示，即下标是行数，内容是列数。例如：A[3]=5就表示第3个皇后在第3行第5列上。判断皇后是否安全，即检查同一列、同一对角线是否已有皇后，建立标志数组ｂ[1..8]控制同一列只能有一个皇后，若两皇后在同一对角线上，则其行列坐标之和或行列坐标之差相等，故亦可建立标志数组ｃ[1..16]、ｄ[-7..7]控制同一对角线上只能有一个皇后。如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。在这种方式下，要表示两个皇后I和J不在同一列或斜线上的条件可以描述为：A[I]A[J]ANDABS(I-J)ABS(A[I]-A[J]){I和J分别表示两个皇后的行号}【参考程序】#includecstdio#includeiostream#includecstdlib#includeiomanipusingnamespacestd;boold[100]={0},b[100]={0},c[100]={0};intsum=0,a[100];intsearch(int);intprint();intmain(){search(1);//从第1个皇后开始放置system(pause);}intsearch(inti){intj;for(j=1;j=8;j++)//每个皇后都有8位置(列)可以试放if((!b[j])&&(!c[i+j])&&(!d[i-j+7]))//寻找放置皇后的位置//由于C++不能操作负数组，因此考虑加7{//放置皇后,建立相应标志值a[i]=j;//摆放皇后b[j]=1;//宣布占领第j列c[i+j]=1;//占领两个对角线d[i-j+7]=1;if(i==8)print();//８个皇后都放置好,输出elsesearch(i+1);//继续递归放置下一个皇后b[j]=0;//递归返回即为回溯一步,当前皇后退出c[i+j]=0;d[i-j+7]=0;}}intprint(){inti;sum++;//方案数累加1coutsum=sumendl;for(i=1;i=8;i++)//输出一种方案coutsetw(4)a[i];coutendl;}【例5】马的遍历中国象棋半张棋盘如图4（a）所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如图4（a）中所示为一种跳行路线，并将所经路线打印出来。打印格式为：0,0-2,1-3,3-1,4-3,5-2,7-4,8…【算法分析】如图4（b）,马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：1:（i,j）→（i+2,j+1）；(i3,j8)2:（i,j）→（i+1,j+2）；(i4,j7)3:（i,j）→（i-1,j+2）；(i0,j7)4:（i,j）→（i-2,j+1）；(i1,j8)搜索策略：S1:Ａ[１]:=(0,0);S2:从Ａ[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下一个到达的顶点；S3:打印路径。【参考程序】#includecstdio#includeiostream#includecstdlibusingnamespacestd;inta[100][100],t=0;//路径总数和路径intx[4]={2,1,-1,-2},//四种移动规则y[4]={1,2,2,1};intsearch(int);//搜索intprint(int);//打印intmain()//主程序{a[1][1]=0;a[1][2]=0;//从坐标(0,0)开始往右跳第二步search(2);system(pause);};intsearch(inti){for(intj=0;j=3;j++)//往4个方向跳if(a[i-1][1]+x[j]=0&&a[i-1][1]+x[j]=4&&a[i-1][2]+y[j]=0&&a[i-1][2]+y[j]=8)//判断马不越界{a[i][1]=a[i-1][1]+x[j];//保存当前马的位置a[i][2]=a[i-1][2]+y[j];if(a[i][1]==4&&a[i][2]==8)print(i);elsesearch(i+1);//搜索下一步}}intprint(intii){{t++;coutt:;for(inti=1;i=ii-1;i++)couta[i][1],a[i][2]--;cout4,8endl;}}【例6】设有A，B，C，D，E五人从事J1，J2，J3，J4，J5五项工作，每人只能从事一项，他们的效益如下。每人选择五项工作中的一项，在各