算法-搜索与回溯对于某个问题如果没有

搜索与对于某个问题，如果没有高效的算法，或者用高效即通过枚举每一种可行的方案来找到题目的答案。 只要当前枚举到的状态可行度 就继续枚举下去。当找到一 方案或者无法继续枚举下去时 就退回到上一状态。退回到 一状态的过程叫做回溯给定给定n（n≤10），求1,2,3,…,n的全排列数什么是全排列如果一个数列含包含这n个数，并且这n个都仅出现一次，符合该条件的所有数列叫做这n个数的全排列。如1,2,3三个元素的全排列为1,2,31,3,22,3,13,1,2可能有的同学已经注意到这个问题的答案就是如果要输出所有方案呢

一个方我们可以用一个布尔数组used示每个数字是否用过，用过为e未用过为false。用ans[i]记录第i个位置的数是多少#include#includeusingnamespaceintintintint{return}voiddfs(int{int

if{for(i=1;i<=n;i++)printf("%d",}for{if{ //标 //回}}}深深度优先搜索的一般框架void{if已找到一种方then枚举每种选if选择可then}TYVJM发现身高接近的人似乎更合得来。M7举办的派对共有()个人参加，M需要把他们安排在圆桌上。M的安排原则是，圆桌上任意两个相邻人的身高之差不能超过。请告诉M7他共有多少种安排方法。输出符合要求的安排总12 23 312是同一种安排方把n个人安排在圆桌上，其实就是n个数的我们可以与上一题一样求出每个排列，再检验这个方是否符合条因为123 231 312是同一方案，所以我们的方案数要除有没有更好的做法我们发现，当我们确定下第一个位置的人与第二个位置的人时，他们的身高可能已经不符合要求了，但我们仍然搜索了下去。我们可以一边搜索一边判断。依次确定每个位置上的人，检验一下该位置的人与前一位置的人是否符合要求当所有人都已确定，再检验n位置与1位置的人是否符要我们可以把第一个人固定在第一个位置再进行搜索，这样最后的答案就不用再除以nprogramcan:array[0..10]ofboolean;a,ans:array[0..10]oflongint;procedureifi>nifabs(ans[n]-theninc(s);

forj:=1tondoifcan[j]and(abs(a[j]-ans[i-1])<=k)fori:=1tondoread(a[i]);经典问N皇后问在n×n（n≤）的国际象棋棋盘上，放置n个皇后，使任何一个皇后都不能吃掉另一个，需满足的条件是：同一行、同一列、同一对角线上只能有一个皇后。43214321我们可以依次确定每一行皇的位

若无法放下皇后则回到上一行即回

当n行的皇后都已确定后，我就找到了一种方放放用a数组标记某列能否用b数组标记左下到右上的对角线能否用c数组标记右programbahuanghou;a,b,c:array[-100..100]f:array[0..100]oflongint;proceduredfs(i:longint);

c[i-ifi>nforj:=1tonifa[j]andb[i+j]andc[i-

石石子合你有n堆石头质量分别为W1，W2，……，Wn(W≤100000）。现需要你将石头合并为两部分，使两部分的质量之和最接近输入：第一行为整数n（1≤n≤20），表示有n堆石子。第二行n个数，为每堆石子的质量输出：一行。只需要输出合并后两部分的质量之和的差样例输入5581327样例输出3我们可以知道这我们可以知道这n堆石子的质量和sum可以用搜索枚举哪些石子放在第一部分，得到第一部分的质量可以用搜索枚举哪些石子放在第一部分，得到第一部分的质量a，求出所有方案中（（a）a）中最小的即为答案。如果第一部分石子质量之和已超过总质量的一半，继续向该如果第一部分石子质量之和已超过总质量的一半，继续向该部分中加入石子，两部分质量差的绝对值必然增大，没有继续搜索的必要。programshizihebw:array[0..20]offunctionmin(a,b:longint):longint;ifa>bthenexit(b)elseprocedureif(tot*2>=sum)or(k>n)thenans:=min(ans,abs(sum-tot-

fori:=1ton输入只有一个整数n，表示待拆分的自然数n。1+2与2+1时间限样例输7样例输

输入7，则7拆分的结果一共有14种情况，所以输出我们可以枚举一个数，用n减去这个数，再枚举一个数，再减去这个数，直至减到0，我们就找到了一种方案。但是这样做会有重复，即对于3我们会先减1再减2，也会先减2再减1，该如何避免重复？我们可以在搜索的时候可以记录一个变量last，表示上次减掉的是哪个数，我们只允许减小于等于last的数，这样可以避免重复。programP1171;procedureiftot=0thenfori:=lastdownto1

s:=s-//因为我们把n=n了一种方案，所以方案数要减iftot-i>=0thendfs(i,tot-有有一个未填满的数独，求这个数独填满后能获得的最大总分分数计算方法总分数为每个方格上的分值和完成这个数独时填在相应格上的数字的积的总NOIP2009靶形数时间限样例输70090000100005900002000800502000000000644002092010608008050401样例输一个最简单的想法我们可以从左上角到右下角枚举每一个未填上的格子，再枚举它可以放哪些数字，将它填上后继续搜索。当所有格子都填上后，计算一下总分，如果总分大于当前最优值就更新最优值严重超时我们还可以对上面的想法进行改进：我们可以先计算出每个格子的选择数先确定可选择数小的格子从而避免搜索到过多无法得到可行方案的状这样还好，，但是依旧超时如果要使程序能通过任何数据，可以采用位运算加速搜索和cinglnks，但这两种方法在联赛范围内基本不会出现，我们不进行深入讨论。另外还用一种方法可以得到10分：根据当前状态确定每个格子的选择数programsudoku;fenshu:array[1..9,1..9]ofmap:array[0..9,0..9]oflongint;hang,lie,ge:array[1..9,1..9]ofboolean;x,y:array[0..81]oflongint;c:array[0..81]ofprocedurecalc;//计算总fori:=1to9forj:=1to9ifs>ansthenans:=s;procedureifk>tthenfori:=1totifc[i]forj:=1to9ifhang[x[i],j]andlie[y[i],j]andge[z[x[i],y[i]],j]thenifw>=minthenbreak;ifw<minend;//找出当前选择最少fori:=1to9do//枚举填哪个ifhang[xx,i]andlie[yy,i]andge[z[xx,yy],i]thenc[p]:=true;//回fori:=1to9forj:=1to9ifmap[i,j]=0

给定整数给定整数和三个字符串s1,2,3，这三个字符由种大写字母组成，相同的大写字母代表相同的数字。这三个字符串表示三个进制的数字a,b,c，且满足ab=c，求各个大写字母分别代表什么数字。51034NOIP2004考虑到进位的问题，我们很容易想到从最低位开始搜索当搜索到第i位时，会有以下几种情况第i位3个数都已确第i位3第i位3第i位3个数都未确只需验证是否合法，合法则继续搜

继续搜索枚举一个未知数，同2确定另一个未知数继续搜枚举两个未知数，同2确定另一个未知数继续搜通过上述处理我们可以通过大部分的数据，但是还是不能拿到满分，最慢的一个数据要运行分钟左右。在搜索过程中，有些位还没有搜到，但可能这些位上的3个数字都已确定，我们就可以先判断这些位是否合法，这样可以将时间大大缩短，所有数据均可在1内出解广度优先搜广度优先搜索广度优先搜用队列保存待扩展的节点，从队首队取出节点，扩展出的新节点放入队尾，直到找到目标节广度优先搜索的代码框{{取队首节点扩展，并将扩展出的节点放入队尾必要时要记住每个节点的父节点}}合理编码，减小存储代需要考虑的问一个boolean标志数组flag判重用的标志数组只需要362,880Hash时时间与空间的权1.从某个顶点出发开始访问，被访问的顶作相应的标记，并输出访问顶点号作相应的标记；3.再依次根2中所有被访问的邻接点，访层，搜索量就会非常庞大，往往就POJ1077八数码问八数码问题是人工智能中的经典问POJ1077八数码问题：经典搜索问3*308共0表01245788238231465712345678 21762247766例题：移字母（NKOJ目标状态为(b)1搜索过122345645678 ==(51)针对字符串的一些hash算法，比如ELFHash和双向广度优先搜有些问题按照广度优先搜索法则扩展点的规则，既适合顺序，也适合逆序，于是我们考虑在寻找目标结点或路径的搜索过程中，初始结点向目标结点和目标结点向初始结点同时进行扩展，直至在两个扩展方向上出现同一个子结点，搜索结束，这就是双向搜索过程。如果确实存在一条从初始结点到目标结点的最初始结点相交点→目标结点所形成的一条路径即是所求最佳正向扩逆向扩双向搜索结点扩展顺答树并不是棵完全树在扩展完一层后，下双向搜索的数据结建立两个队列，OPEN[1]，CLOSED[1]，OPEN[2]，双向广度优先搜索算法//DOUBFS初始化，初始结点，和目标结点分别进入OPEN[1]和OPEN[2]表head[1]=1;tail[1]=1;head[2]=1;if(tail[1]-head[1]<=tail[2]-head[2])t=1;elset=2；//优先扩展待讨论节点比较少那个方for(i=head[t];i<=tail[t];i++)expand(t)；//讨论队列中的结//函数expand(t)void