C语言-搜索算法

ACM程序设计杭州电子科技大学2020/4/1722011集训队讲座--第一讲搜索入门(Searching)2020/4/173预备知识1.什么是队列?2.什么是树?3.什么是图?2020/4/174队列队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。(FIFO)2020/4/175队列的实现方法1.方法一：int(元素类型)Queue[MAX_NUM];inttop=1,base=0;入队:Queue[top++]=入队元素;出队:inttmp=Queue[base++];2.方法二:(利用STL)#includequeueusingnamespacestd;queueintQ;入队:Q.push(入队元素);出队:inttmp=Q.pop();2020/4/176树2020/4/177图2020/4/178图的表示法0ABCDEFGHIJA0100000000B1011000000C0100100000D0100110000E0011000000F0001001100G0000010100H0000011011I0000000100J0000000100ABCDEFGHIJABBACDCBEDBEFECDFDGHGFHHFGIJIHJH2020/4/179IndexBFS(宽度优先搜索)(双向广搜)DFS(深度优先搜索)2020/4/1710什么是搜索问题2020/4/1711胜利大逃亡2020/4/1712基本概念状态隐式图状态空间状态转移解答树(0,0,0)(1,0,0)(0,0,1)(0,1,0)(0,2,0)(0,0,2)(0,1,1)(1,0,1)(1,1,0)(2,0,0)节点:所有的状态有向边:状态的转移状态空间:所有状态的集合……可行解:一条从初始状态到目标状态的路径2020/4/1714宽度优先搜索BFS(breadthfirstsearch)适用解决最优解问题如:用时最少;转弯次数最少;代价最优;2020/4/1715BFS先遍历隐式图中通过一条边所能访问到的所有节点,然后访问通过两条边所能访问的所有节点,依次类推.我们来看一个例子….2020/4/1716(1,1,2)(1,2,3)(1,3,4)(3,1,4)(0,3,5)(2,3,5)(1,0,1)(2,1,3)(0,1,1)(2,0,2)(3,0,3)BFS的遍历方式(0,0)(0,1)(0,2)(1,0)(1,1)(1,2)(2,0)(2,1)(2,2)(0,3)(1,3)(2,3)(3,0)(3,1)(3,2)(3,3)011223Queue(0,0,0)3346545(3,3,6)2020/4/1717BFS队列的一些性质123有什么神奇的发现？回忆一下几个细节队列中的状态总是按按关键状态单调排列.为什么?这个性质非常重要.这个性质保证了最先被搜索到的解一定是最优解。2020/4/1718BFS的Hash的方法你是否又曾注意到为什么这里不得到状态(1,1,4)并使其重新入队?剪枝!2020/4/1719什么是剪枝?即剪去解答树上已被证明不可能存在可行解或最优解的子树.不存在解的子树,可以不进行遍历2020/4/1720此题的剪枝方法HASH（最常用）标记已经遍历到的结点，若此后再出现该状态即可直接舍去，不对其进行入队操作。(关键:防止状态不必要的重复)2020/4/1721代码怎么写关键字:队列的应用状态的转移Hash判重2020/4/1722BFS代码框架while(队列不为空){弹出队列头结点nodetemp=Q.pop();判断该状态是否为目的状态if(temp.x==dx&&temp.y==dy)returntemp.t;从该结点状态转移到其他状态for(inti=0;i4;I++){//intgo[][2]={1,0,-1,0,0,1,0,-1};intx=temp.x+go[i][0];inty=temp.y+go[i][1];intt=temp.t+1;}有选择的选择未出现过的状态入队if(hash[x][y]==false){hash[x][y]=true;Q.push(newnode(x,y,t));}}2020/4/1723NightmareSampleInput3332111101134821101110104110411000000111141113SampleOutput4-113直接把经过的地方都hash掉行不行?2020/4/1724反例我们来看一个惊人的反例。581211111410001001141011011000030111411111Hash的关键：状态的重复增加一维记录炸弹剩余的时间用hash[x][y][t]记录到达(x,y)点时炸弹距离爆炸还有t秒的最优解.状态只有位置和时间吗?2020/4/1725再来理解一下状态且看下一个有趣的问题.2020/4/1726非常可乐SampleInput743413000SampleOutputNO3这连图都没有这也能搜索？2020/4/1727状态是什么?你能回答吗?状态即是两个杯子和一个瓶子中各自装有的可乐体积.有了状态如何转移呢?有了状态有了转移(边),是否就能进行搜索了?2020/4/1728还需要考虑搜索的可行性：可能被搜索到的状态数量:N*M*S==1000000如何防止相同状态不被重复搜索.如何剪枝?这里又是判断状态重复的Hash剪枝怎么做?利用hash[n][m][s]=记录(n,m,s)状态是否曾经出现过.还有问题吗?直接开搜!2020/4/1729OceanCurrentsSampleInput5504125033556473472377020623424245145334SampleOutput021思考一下你想到了什么?刚才讲的BFS能行吗?为什么701\|/6-*-2/|\5432020/4/1730队列的性质由于各个状态并不一定按照所用递增的时间入队,队列单调的性质遭到了破坏.严重的后果,最先得到的解不一定是最优解.怎么办?维护队列的单调性.使用优先队列:priority_queue.2020/4/1731优先队列使用优先队列维护队列单调性使并不单调入队的状态按照用时递增的顺序出队2020/4/1732IgnatiusandthePrincessISampleInput56.XX.1...X.2.2...X....XX.XXXXX.SampleOutputIttakes13secondstoreachthetargetposition,letmeshowyoutheway.1s:(0,0)-(1,0)2s:(1,0)-(1,1)3s:(1,1)-(2,1)4s:(2,1)-(2,2)5s:(2,2)-(2,3)6s:(2,3)-(1,3)7s:(1,3)-(1,4)8s:FIGHTAT(1,4)9s:FIGHTAT(1,4)10s:(1,4)-(1,5)11s:(1,5)-(2,5)12s:(2,5)-(3,5)13s:(3,5)-(4,5)FINISH怎么还需要输出路径！？2020/4/1733记录路径记录前驱！记录当前状态是由哪一个状态转移而来的2020/4/1734其他优先问题---逃离迷宫SampleInput255...***.**...........*....11113SampleOutputno与刚才的BFS有什么区别,又有什么相同点?2020/4/1735转弯次数优先既然要求转弯次数最少,我们就要保证队列里的状态按转弯次数单调递增排列,这就要求各个状态按照转弯次数递增的顺序入队.即转弯0次的全部入队以后,才允许转弯1次的入队.依次类推。具体怎么操作?将每个状态转一次弯所能达到的所有结点入队.这样就保证了第一次搜到的目标状态即是所用转弯次数最少的答案.2020/4/1736更加强劲的DTBFS双向广搜(DoubleThresholdBFS)2020/4/1737双向广搜一般来说,从初始结点和目标结点开始分别作两次BFS,每次选择队列中结点少的一边进行扩展,并且检测两边是否出现了状态重合.有兴趣的同学可以试试Solitaire2020/4/1738来看另一类搜索问题深度优先搜索(depthfirstsearch)2020/4/1739深度优先搜索DFS(depthfirstsearch)适用的范围:用于快速寻找可行解,但不要求解为最优.应用不局限于搜索题.2020/4/1740能走出去吗?这个……2020/4/1741DFS的遍历方式每次访问到一个结点（状态）时，检查其邻接结点，若存在可访问子结点时，则递归访问该结点，若无子节点可以访问或子节点已全部被访问完毕则返回上一层。2020/4/1742DFS的遍历路径遍历完成2020/4/1743补充知识什么是递归？关键字：调用自身简单的例子:阶层的递归实现intfunc(intn){if(n==1)return1;elsereturnn*func(n–1);}递归的出口优点：编码量小缺点：效率低2020/4/1744递归过程调用调用调用返回返回返回2020/4/1745连连看SampleInput3412340000432141134112411332124SampleOutputNO2020/4/1746解题怎样判断是否可以消去？本质：从一个点出发是否存在一条转弯次数小于等于两次的路径可以达到另一个点。(不要求最少转弯次数)明显的是否存在可行解问题。2020/4/1747问题:如何判断是否发生转弯?记录当前方向,并且传入下一步子程序.voidDFS(intx,inty,intnum,intdir){if(num2)return;如果发生转弯的行走DFS(x’,y’,num+1,dir’);如果未发生转弯DFS(x’,y’,num,dir);}2020/4/1748暴搜能解决问题吗?不加任何剪枝的直接暴搜.Sample跑的还是挺快的么~~提交一下~~2020/4/1749剪枝!剪枝!剪枝!剪枝的重要性可见一斑。那么有什么地方可以让我们剪枝呢？看下面这张战局图。2020/4/1750已经转弯一次方向完全相反。还有必要走下去吗？2020/4/1751增加剪枝方案VoidDFS(intx,inty,intnum,intdir){if(num=1）{if(dir为x增大方向&&目标x小于现x)return;if(dir为x减小方向&&目标x大于现x)return;if(dir为y增大方向&&目标y小于现y)return;if(dir为y减小方向&&目标y大于现y)return;}…..}既然这样?那么……2020/4/1752这种已经转了两次的情况呢?2020/4/1753再次增加剪枝方案效果非常明显2020/4/1754再次强调剪枝的重要性来看一下DFS在另一类题里的作用.ACMer们：为了ACM事业，努力地剪枝吧！！2020/4/1755PrimeRingProblemSampleInput68SampleOutputCase1:143256165234Case2:123856741258347614765832167438522020/4/1756如何用DFS解决这个问题？用DFS枚举所有状态，判断该状态是否可行。2020/4/1757代码框架这样就行了吗？voidDFS(int当前数字数量){if(当前数字数量==要求数字）{if(符合条件)输出();elsereturn;}else{从未用过的数字中取一个加入到当前位置();DFS(当前数字数量+1);}}2020/4/1758复杂度分析注意到(0n20)裸的DFS最多需要枚举19!(121645100408832000)次怎么办?剪枝！剪！怎么剪？2020/4/1759剪枝若枚举的前几项已经不满足条件，在这个序列的基础上枚举的所有序列还有可能是可行的吗？保证每次枚举都使当前加入的数字与已经在序列里的前一个数字的和