穷举回溯搜索1

算法设计与分析王歧目录•动态规划•贪心算法•状态空间搜索法•分治法•随机算法•模拟算法•递归算法•数论算法回溯算法•对于有些最优解问题，没有任何的理论也无法采用精确的数学公式来帮助我们找到最优解，我们只能用穷举算法。在这里我们介绍一种系统化的穷举搜索技术，称为回溯技术。•所谓回溯技术就是向人走迷宫一样，先选择一个前进方向尝试，一步步试探，在遇到死胡同不能再往前的时候就会退到上一个分支点，另选一个方向尝试，而在前进和回撤的路上都设置一些标记，以便能够正确返回，直到达到目标或者所有的可行方案都已经尝试完为止。回溯算法•在通常的情况下，我们使用递归方式来实现回溯技术，也就是在每一个分叉点进行递归尝试。在回溯是通常采用栈来记录回溯过程，使用栈可使穷举过程能回溯到所要的位置，并继续在指定层次上往下穷举所有可能的解。回溯算法用伪代码描述如下：•Procsearch(当前状态)；•Begin•If当前状态等于目标状态thenexit；•for对所有可能的新状态•search(新状态);•End;回溯算法的经典问题•八皇后问题。•骑士周游问题•地图着色问题八皇后问题•问题描述在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相“冲突”（在每一横列竖列斜列只有一个皇后）。算法流程•１、数据初始化。２、从n列开始摆放第n个皇后，先测试当前位置(n,m)是否等于０如果是，摆放第n个皇后，并宣布占领，接着进行递归；否则，测试下一个位置(n,m+1)，但是如果当n=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。３、当n8时，便一一打印出结果。问题分析•这道题可以用递归来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：1、冲突。包括行、列、两条对角线2、数据结构1、冲突，包括行、列、两条对角线：•（1）列：规定每一列放一个皇后，不会造成列上的冲突；（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2、数据结构•（1）解数组A。A[I]表示第I个皇后放置的列；I=1,…,8；（2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；I=1,…,8；（3）对角线冲突标记数组C、D。C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16•优点：逐一测试标准答案，不会有漏网之鱼。八皇后问题程序•#includestdio.h•#includestdlib.h•#includetime.h•intmain(intargc,char*argv[])•{intq[1024];inti,j,k,c,n;time_ttm;•switch(argc)•{case1:n=8;break;•case2:n=atoi(argv[1]);•if(n=0||n=1024)return0;break;•default:return0;•}•tm=time(0);•for(i=0,c=0,q[0]=0;;)•{if(n==q[i])•{if(0==i)break;•i--;•q[i]++;•continue;•}•for(j=0;ji;j++)•if(q[i]==q[j]||q[i]-i==q[j]-j||q[i]+i==q[j]+j)•break;•if(j==i)•{if(n-1==i)•{c++;•if(n10)•{printf(%5d:,c);•for(k=0;kn;k++)•printf(%d,q[k]+1);•printf(\n);•}•q[i]=n;•}•else•{i++;•q[i]=0;•}•}•elseq[i]++;•}•printf(total:%d,%dsec\n,c,(int)(time(0)-tm));•return0;•}N皇后问题•发信人:PowerStation(WarezKiller),信区:sources标题:最快的N皇后问题CProgram发信站:饮水思源站(ThuMay1501:25:391997),转信/*最快的N皇后问题CProgram这个程需仍然采用传统的递归算法，但使用了C的位操作以极大地提高了运行速度。law的程序算13皇后用了43秒，而我的仅用7秒，快六倍,半个数量级,:))).(比较时删去了火火的输出部分以示公平).同时我的程序可非常容易的转换成asm,还能更快。本程序去掉了输出各解的功能，一方面是为了尽可能的快，另一方面似乎也没有必要。(真有人看吗?)*/#includestdio.h#includestdlib.h#includetime.hlongsum=0,upperlim=1;voidtest(longrow,longld,longrd){if(row!=upperlim){longpos=upperlim&~(row|ld|rd);while(pos){longp=pos&-pos;pos-=p;test(row+p,(ld+p)1,(rd+p)1);}}elsesum++;}intmain(intargc,char*argv[]){time_ttm;intn=8;if(argc!=1)n=atoi(argv[1]);tm=time(0);if((n1)||(n32)){printf(heh..Ican'tcalculatethat.\n);exit(-1);}printf(%dQueens\n,n);upperlim=(upperlimn)-1;test(0,0,0);printf(Numberofsolutionsis%ld,%dseconds\n,sum,(int)(time(0)-tm));}/*在另一台较快的workstation上的结果。12QueensNumberofsolutionsis14200,1seconds13QueensNumberofsolutionsis73712,4seconds14QueensNumberofsolutionsis365596,28seconds15QueensNumberofsolutionsis2279184,138seconds16QueensNumberofsolutionsis14772512,993seconds本程序可算到32阶，但朝过18阶后，记录解总数的longintsum将溢出，需采用其它方法。如用另一个longint来记录更高位，各位不难做到。*/--※修改:·PowerStation於May1506:27:26修改本文·[FROM:pc-48.emcb.cc.u]※来源:·饮水思源站bbs.sjtu.edu.cn·[FROM:pc100-5.emcb.cc]素数环•问题：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。•分析：非常明显，这是一道回溯的题目。从1开始，每个空位有20（19）种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。算法流程•1、数据初始化；2、递归填数：判断第J种可能是否合法；A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能；•任何一个正整数都可以用2的幂次方表示.例如:137=2^7+2^3+2^0同时约定次方用括号来表示,即a^b可表示为a(b)由此可知,137可表示为:2(7)+2(3)+2(0)进一步:7=2^2+2+2^0(2^1用2表示)3=2+2^0所以最后137可表示为:2(2(2)+2+2(0))+2(2+2(0))+2(0)又如:1315=2^10+2^8+2^5+2+1所以1315最后可表示为:2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)输入:正整数(n=20000)输出:符合约定的n的0,2表示(在表示中不能有空格)搜索算法•搜索算法，是一种在状态空间中寻找特定的目标状态及到达目标状态的途径的系统方法。搜索是计算机求解问题的最基本方法，适用面很广，没有向动态规划那样对状态有最优化原理和无后效性的约束。•当然对具体问题，特别是运用了某种智能化的优化手段，也许会带来某些具体的约束。•当所给定的问题用状态网络表示时，则求解过程可归结为对状态空间的遍历。搜索空间是搜索达到的状态空间，它是状态空间的一部分。当问题有解时使用不同的求解策略，找到解的搜索空间范围是有区别的。一般来说，对大空间问题，搜索策略是要解决组合爆炸问题。搜索算法的一般模式•一般说来，搜索算法要求记录完整的搜索空间，即保留所有生成的节点。这样做有两个目的：状态判重和输出解路径。•为了方便描述选择待扩展的节点和生成新节点的过程，我们同时将节点组织成两张表，称为CLOSED表和OPEN表。CLOSED表中存放已经扩展过的节点，OPEN表中存放已经生成但尚未扩展的节点。搜索开始之前CLOSED表是空的，而OPEN表中只有初始节点。•搜索过程可描述为：从OPEN表中选择一个结点u，将结点u从OPEN表中删除，加入到CLOSED表，然后扩展结点u得到新结点v1，…，vk，(这些顶点的状态应该于已经生成的节点的状态是不同的)，将这些结点加入到OPEN表中。•Proceduregraph_search;•Begin•CLOSED表初始化为空；•OPEN表初始化为空；•whileOPEN表非空do•取OPEN表中的一个结点u;•从OPEN表中删除u;•u进入CLOSED表；•对扩展结点u得到的每个新结点vido•ifvi的状态与CLOSED表和OPEN表中•的节点的状态都不行同then•vi进入OPEN表；•End;•End;两种基本的搜索算法•深度优先搜索：优先扩展尚未扩展且具有最大深度的结点；•广度优先搜索：就是在扩展完第k层的结点之后，才扩展第k+1层的结点。•如果OPEN表示后进先出的，深度•如果OPEN表示先进先出的，广度深度优先与回溯•从本质上说，回溯和深度优先搜索几乎就是一回事了。但两者还是有差别的。•首先，回溯方式不保留完整的树结构，只记住当前工作的一条路经，回溯就是对这条路径进行修正；而深度优先搜索则记下完整的搜索树，搜索树同时起到记录解路径和状态判重的作用。因此，回溯方式明显的节省空间。•（迷宫问题、八皇后问题）•其次，回溯方式要就能够按照一种事先确定好的某种固定排序依次调用规则。即对每一层I事先都确定好一个规则的序列Ri1，Ri2，…，Rin，假设第i层当前规则是Rik，如果到第i+1层发现所有的规则都不合适，就回溯到第i层，若kn，则继续尝试规则Rik+1，否则在回溯到第i-1层，这种对规则有序性要求的原因是，回溯方式不保留完整的树结构。而深度优先搜索则没有对规则有序性的要求。•在实际应用中，把两者的优点结合起来，形成一种新的算法模式，以后在提到深度优先搜索就是指这种新算法。搜索算法的优化手段•剪枝：如果能够通过一些信息，说明继续扩展该结点不可能到达目标结点，则可以将搜索树在该结点以下的分支全部剪去，从而达到减少搜索范围、提高搜索速度的目的。•对扩展结点u得到的每个新结点vido•ifvi不满足剪枝条件then•ifvi的状态与CLOSED表和OPEN表中•的节点的状态都不行同then•vi进入OPEN表；广度优先搜索算法BFS•广度优先搜索(BreadthFirstSearch)•对图G=(V，E)进行BFS搜索的步骤可直观的叙述如下。从任意选定的r开始，依次检查所有与