acm-搜索专题

搜索技术包含的内容1.回溯法2.回溯+剪枝法3.广度搜索4.双向广度优先搜索5.A，A*算法6.渐进深度优先算法7.爬山法8.分支限界法9.遗传算法10.与或图与博弈树11.模拟退火法1.回溯法回溯法概念•回溯法也称试探法.•它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。•这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。•回溯策略回溯搜索的示意1AB28C11DE3F69G10HI4J57K状态空间中回溯搜索图中虚线箭头的方向表明了搜索的轨迹，结点边的数字表明了被搜索到的次序回溯法分析•采用递归，算法简单，时间复杂度比较大•采用迭代法，算法设计与题目相关度大，时间复杂度较小。•递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：•ProcSearch(当前状态);•begin•If当前状态等于目标状态thenexit;•for对所有可能的新状态Search(新状态)；•endProcedureBACKTRACK(n)；{k:=l；repeatifTK(x1,x2,...xK-1)中的值未取遍then{xK:＝TK(x1，x2，...,xK-1)中未取过的一个值；ifBK(x1,x2,...,xK)then//状态结点(x1,...xk)被激活ifk＝nthenoutput(x1,x2,...,xk)//输出一个回答结点e1sek:＝k+l；}//深度优先e1sek:＝k-l；//回溯untilk＝0；end；{BACKTRACK}本课件题库网站•题马的走法•在一个4*5的棋盘上，马的起始位置坐标（纵、横）位置由键盘输入，求马能返回初始位置的所有不同走法的总数。（马的位置不能重复，马走“日”字。）SampleinputOutputfortheinput224596Input输入数据只有一行，有两个用空格分开的整数，表示马所在的初始位置坐标。首行首列位置编号为（11）。Output输出一行，只有一个整数，表示马能返回初始位置的所有不同走法的总数。如果输入的马的初始位置超出棋盘边界，则输出ERROR。马的走法分析（1）•由于4*5问题规模小，采用基于递归的回溯法•问题定义：•（1）采用二维数组表示棋盘。•（2）马走步表示方法二维数组，{{-1，-2}，{-1，2}，{-2，1}，{-2，-1}，{1，2}，{1，-2}，{2，1}，{2，-1}}，8个方向。•（3）棋盘的最小坐标，左下角为（1，1）•（4）棋盘越界条件0≤x≤4,0≤y≤5•（5）走过的棋盘位置应该设置一个标示。马的走法分析（3）•递归的回溯算法可描述为：•proceduresearch(now:position);{now是当前位置}•beginfor马从当前位置now出发走一步到位置next的每一种走法–dobeginifnext在棋盘内andnext位置没有走过then–ifnext=出发点then不同走法总数加1–elsebegin标记next已经走过了;search(next)取消位置next的标记;end;–end;•end;•#includeiostreamusingnamespacestd;constintROWS=4;//行数constintCOLUMS=5;//列数intchess[ROWS][COLUMS];//棋盘intnumCount=0;intposX,posY;intdirection[2][8]={{-1,-1,-2,-2,2,2,1,1},{-2,2,1,-1,1,-1,2,-2}};//马走日字voidSolve(intx,inty){inti,j,desX,desY;for(i=0;i8;++i){desX=x+direction[0][i];//目标位置x坐标desY=y+direction[1][i];//目标位置y坐标if(desX=0&&desX4&&desY=0&&desY5&&chess[desX][desY]==0){//满足规则，走到目标处，并继续搜索chess[desX][desY]=1;Solve(desX,desY);chess[desX][desY]=0;}elseif(desX==posX&&desY==posY){//回到了起点numCount++;}}}•intmain(){cinposXposY;memset(chess,0,sizeof(chess));numCount=0;//走法数chess[posX][posY]=1;//起始步Solve(posX,posY);//开始搜索coutnumCountendl;system(pause);return0;}1882--n皇后问题•在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。Input•输入数据只占一行，有1个正整数n，n≤20。•Output•将计算出的彼此不受攻击的n个皇后的一个放置方案输出。第1行是n个皇后的放置方案。•SampleInput•5•SampleOutput•135244皇后问题图示•SampleInput•4•SampleOutput•2413QQQQ()()Q((1,1))()QQ((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))n皇后问题分析•用数组intx[N]表示棋盘状态，例如x[0]=1表示第0行皇后放在第一列。•皇后k在第k行第x[k]列:（k,x[k])•测试方法：测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后j相攻击.–x[j]==x[k]时，两皇后在同一列上;–abs(k-j)==abs(x[j]-x[k])时，两皇后在同一斜线上。–两种情况两皇后都可相互攻击，递归法-n皇后问题（1）•#includestdio.h/**NOTE:该程序是一个解N皇后棋局问题的算法(采用递归解决)*编译环境VC++6*//*程序随N值的改变,从而来解决N皇后问题*/#defineN4intx[N],sols;/*放置皇后到位置(row,col),若成功返回1,失败返回0*/intplace(introw){intj;for(j=0;jrow;j++)/*j代表行*/{if(row-x[row]==j-x[j]||row+x[row]==j+x[j]||x[j]==x[row])return0;}return1;}/*row代表开始轮到放第row行了,前row-1行都已放好*/递归法-n皇后问题（1）•voidbacktrack(introw){intk;if(N==row){sols++;//解的结果加1/*循环打印八皇后棋局(下标转换成从1开始)*/for(k=0;kN;k++)printf((%d,%d),x[k]+1,k+1);printf(\n);}else{inti;for(i=0;iN;i++){x[row]=i;if(place(row))backtrack(row+1);}}}voidqueens(){backtrack(0);}•intmain(void){queens();printf(TotalSolutions:%d\n,sols);return0;}迭代法-n皇后问题（1）•#includestdio.h/**NOTE:编译环境为DevC++*该程序是一个解N皇后棋局问题的算法(采用迭代回溯解决)*/#defineN4/*定义棋盘大小*/staticintsum;/*当前已找到解的个数*/staticintx[N];/*记录皇后的位置,x[i]=j表示皇后i放在棋盘的第i行的第j列*//*确定某一位置皇后放置与否,放置则返回1,反之返回0*/intplace(intk){intj;/*测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击.x[j]==x[k]时，两皇后在同一列上;abs(k-j)==abs(x[j]-x[k])时，两皇*//*后在同一斜线上。两种情况两皇后都可相互攻击，故返回0表示不符合条件。*/for(j=0;jk;j++)if(x[j]==x[k]||abs(j-k)==abs(x[j]-x[k]))return0;return1;}迭代法-n皇后问题（2）•/*回溯搜索解空间*/voidbacktrack(){intk=0;x[0]=-1;while(k=0){x[k]+=1;/*向右移一列*//*向右移至出最右列或可以放置皇后的列*/while((x[k]N)&&!(place(k)))x[k]+=1;if(x[k]N)/*向右移未移出棋盘*/if(k==N-1)chessboard();/*已移至最后一行*/elsex[++k]=-1;/*向下移一行*/elsek--;/*回溯到上一行*/}}intmain(void){backtrack();getch();return0;}2.回溯+剪枝•回溯与剪枝的方法是从树根开始，边试探边往下走，若在某一层次查明不符合题意，则不往下走，砍掉以下的树杈，跳到下一杈上继续试探着往下走。这样边走边砍，砍掉大量的树杈，从而省掉大量测试。一旦走到叶子，就找到了一组解。回溯与剪枝1402著名医生的药方•有个医术高明的医生，开出的药方难以辨认。他有这样的习惯：•他有一个药材库，里面有N种药，除了这N种药，他不会使用其他药。•药材库中的每种药，都有一个他的后续药集合，只有这种药的后续药才能直接出现在这种药的下一个位置。当然，任何一种药都可能同时是几种药的后续药。•这个医生开出的药方是一个列表的形式，在他的一个药方中，一种药只可能出现一次。当他开出一种药和它的后续药后，这种药的其他后续药就不可能出现在之后的序列中。•现在，有一个关于这个医生的药方，药方中写有p种药。可惜的是，药方中有一些药并没有具体辨别出。那么，请你写一个程序，帮忙辨别出药方中不确认的药。当然，对于不确定的药方，可能可以构造出多种不同的药方，那么请你找出所有的情况。•Input•输入数据的第一行只有一个正整数n（0n=500），表示所有药的总数