搜索算法搜索算法设计专题清华大学1搜索本质穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法如何穷举问题拆分多个阶段枚举每个阶段所有可能性搜索算法搜索算法2图论解空间（图）每个阶段（结点）阶段间的转移（边）穷举解空间（遍历图）动态规划（记忆化搜索）最优子结构，无后效性（拓扑图）子问题重叠性（图中结点少）搜索与其他算法搜索与其他算法3搜索搜索& &动态规划划S0tS1S2S3SnW0W1,1W1,2W2,1W2,2W2,3W3,3W3,2W3,1Wn,1Wn,2Wn,3Wn+14深度优先搜索（DFS）记录路径上经过结点标记访问过的结点剪枝方法Hash判重估价剪枝alpha-beta剪枝搜索顺序搜索方法搜索方法S0Sg5极小极大极小极大过程程05-333-3022-30-23 5 41-3068 9-30-33-3-3-21-36-30316011方块极大圆圈极小ab026极大节点的下界为。极小节点的上界为。剪枝的条件：后辈节点的值祖先节点的值时， 剪枝后辈节点的 值祖先节点的值时， 剪枝简记为：极小极大，剪枝极大极小，剪枝Alpha-BetaAlpha-Beta剪枝剪枝7Alpha-BetaAlpha-Beta剪枝剪枝486-315035-33-3022-30-2309-300-303305411-31661abcdefghijkmn8取值范围小的优先搜索制约力强的优先搜索对解影响大的优先搜索增加估价函数的准确度搜索搜索顺序序9广度优先搜索（BFS）队列维护搜索状态避免重复入队剪枝方法Hash判重搜索算法搜索算法10时间复杂度BFSDFS如何结合两个特点？DFS&BFDDFS&BFD11渐进的深度优先搜索（ID-DFS）枚举搜索层数加快DFS的搜索时间便于估价剪枝失败尝试额外时间的开销？搜索算法搜索算法12启发式搜索（A*）g*(n)：从s到n的实际最优代价h*(n)：从n到g的实际最优代价f*(n)=g*(n)+h*(n)：从s经过n到g的实际最优代价h(n)：从n到g的估计最优代价, h(n) h*(n) f(n)=g*(n)+h(n)：估计的s经过n到g的实际最优代价A*算法每次挑选f(n)最小的结点第一次碰到的解就是最优解空间复杂度大搜索算法搜索算法13Heap优化加快最优扩展结点的寻找f(n)=g*(n)+kh(n)K为比例系数，控制速度和误差A*A*算法算法优化化14渐进启发式搜索（IDA*）ID+A*算法在A*的基础上节约空间并且加快剪枝搜索算法搜索算法15折半搜索（双向搜索）搜索算法搜索算法16给定一个01矩阵, 现在要选择一些行，使得每一列有且仅有一个1 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 11, 4, 5例例题1 117覆盖集NP问题搜索双向链表DancingLinks例例题1 118Dfs()如果所有列被覆盖则输出解如果没有可以使用行输出无解枚举可使用行将有交集的行删去进入下一层搜索还原有交集的行例例题1 119给出一张N*M的带障碍的地图（N,M21）A和B在地图上的两点每一时刻A和B可以向周围的8个格子移动一步，或者原地不动但是A和B不能在移动的过程中相碰，并且不能移动到障碍上问A和B交换位置所需最少时间。例例题2 220用(x1, y1, x2, y2)表示A在(x1, y1)，B在(x2, y2)的最小代价寻求最短路，解空间较小，直接BFS例例题2 221用给出的N（N6）个矩形覆盖一个WH的大矩形（可以重叠），使得覆盖的面积最大例例题3 322如何枚举覆盖方案每个矩形都和其他的一个矩形紧挨着，或者和边界紧挨着搜索放置顺序如何统计覆盖面积容斥原理例例题3 323数轴上有N（N10）个点，最左边的点在原点。给出N个点任意两个点的距离，要求你还原这N个点，如果有多解输出字典序最小的解。例例题4 424最长边原点到最右边点距离确定最右点，删除最长边剩余最长边某个新点到原点，或者到最右边的点的距离枚举这两种方案（字典序小的优先把局面上新出现的距离都从集合中删除例例题4 425在一棵有根树上，A、B君轮流砍边。A君只能砍红边，B君只能砍黑边。边带权，砍边的人得到边的权值。令D=A的得分-B的得分，A试图使D最大化，B试图使D尽可能小。求最终得到的D。N=20例例题5100515026终结节点：只剩根的情况。此时D(S)=0。边的情况：如果能通过砍边而连接起来的两个状态之间连一条有向边。图无环，且每个节点连出的边的数量为n阶的。节点数量：220例例题527要求把N（ N36）个人成相等的两组第i个人在第一组有ai的得分，在第二组有bi的得分要求第一组人的得分和第二组人的得分差距尽量小，并求字典序最小方案例例题6 628将N个人平均分为两部分对于前半部分，令第一组人数比第二组多i，枚举所有分组方法，按照第一组比第二组多得分多少排序。对于后半部分，令第一组人数比分到第二组少i个，枚举，之后在表里二分查找合并后能使第一组人的得分和第二组人的得分差距尽量小的前半段分法，更新答案。例例题6 629问题要求设计一个m层的蛋糕，蛋糕的体积为N，蛋糕中每一层都是一个圆柱体，而且每一层的高度H和半径R均要比下一层的小对于给定的n和m，求蛋糕最少可能的表面积(不包括最下一层的下底面)大小。例例题7 730 由于R和H是从下到上递减，所以体积也是从下到上递减，因此选择从下到上的搜索顺序有利于判断当前情况是否可行。 此外，注意到表面积包括每层蛋糕的侧面积和裸露的顶面积。确定了最底层的蛋糕就确定了每层蛋糕裸露的顶面积之和，需要考虑的只剩下每层蛋糕的侧面积。因此这样的搜索顺序有利于判断是否可能出现比已知最优解更优的解。例例题7 731给出一个用正三角形平铺的地图，若两个三角形有公共边，则称之为相连。把一个内部没有空洞的正三角形连通块称之为岛屿，若两个岛屿翻转或旋转后相同，那么称之为相同的岛屿现在你要回答下面两个询问：给出一个有N个三角形的岛屿，问在增加一个正三角形后可以变成多少个不同的岛屿；询问有多少个不同的且有N个三角形的岛屿。N10例例题8 832先对于第二类问题，我们可以看作第一类问题的扩展版所有的N个三角形的岛屿都可以看作是由N-1个三角形的岛屿增加一个正三角形后得到的由于问题求的是最后所有不同的岛屿的外围轮廓线（顺时针方向），因此，我们存储的时候也只要记录轮廓在外围增加一个三角形的操作，即在一条原来的轮廓线上突出一个三角形（绿色部分）例例题8 833两种特殊情况绿色的边在轮廓线相邻位置重复出现，所以要删掉往返走的轮廓线部分紫色的边在廓线不相邻上相邻重复出现，因此构成了一个环，不是合法解。例例题8 834有N个人和M种事件（例如刷牙、吃饭、睡觉）Qi=(Qi,1, Qi,2Qi,Ci)表示第i个人一天的事件序列，Ci表示第i个人一天做的事情的总数（Qi,j是M种事件之一）那么整个世界的轨迹可以表示为P=(Qi1,j1, Qi2,j2Qil,jl).P满足对于每个人Qi,j都出现一次且一次并且Qi,j1出现在Qi,j2之前（j1j2）例例题9 935相关是事件之间的二元关系P1和P2的本质不同当且仅当存在相关事件Q在其中先后位置不同给出每个人的事件序列Qi，和任意两个事件之间的相关关系，求本质不同的事件总数（保证总数小于1000000，N10, M15, Ci20）例例题9 936Q1,0 = 0, Q1,1 = 1Q2,0 = 2, Q2,1 = 1只有0和2不相关P1 = Q1,0, Q1,1, Q2,0, Q2,1P2 = Q1,0, Q2,0, Q1,1, Q2,1P3 = Q1,0, Q2,0, Q2,1, Q1,1P4 = Q2,0, Q2,1, Q1,0, Q1,1P5 = Q2,0, Q1,0, Q2,1, Q1,1?例例题9 937我们把每个人的每个事件当作一个点，来构造一个有向图，图中存在边E(u,v)表示u事件比v事件先发生。首先根据定义，这个图一定是一个拓扑图，因为事件之间发生的先后关系不可能构成一个环。例例题9 938对于每个人来说，由于他的事件要按顺序发生，所以我们可以把他的所有事件点连成一条链。对于不相关的事件，不关心他们之间的先后顺序，不用连边。我们只在相关的事件之间连边，这些边的方向直接决定了当前世界轨迹的本质例例题9 939例例题9 940给出一个连通无向图，要求从1到M给每条边编号要求连出多条边的点，连出的所有边编号互质求一个可行的方案（点数小于50）例例题101041相邻的数字一定是互质的DFS过程中一定是沿着图的边走的若按照DFS序编号，则每个点一定存在两条编号相邻的边例例题101042屏幕上有*个随机的数字，光标初始指向第一个数字，键盘上有6个键，功能如下：Swap0：光标位置不变，将光标所在位置的数字与1号位置的数字交换。Swap1：光标位置不变，将光标所在位置的数字与8号位置的数字交换。Up：光标位置不变，将光标所在位置的数字加1，如果该处数字为9，则按Up之后，数字不变Down：光标位置不变，将光标所在位置的数字减1，如果该处数字为0，则按Down之后，数字不变；Left：光标左移一个位置，如果光标已经在1号位置上，则光标不动；Right：光标右移一个位置，如果光标已经在8号位置上，则光标不动。问将8个数改为我们所需的特定数字最少需要按几步例例题111143直接进行搜索，从初态开始，知道找到末态的最优解为止。无论空间，时间都行不通8个位置100000000个不同的数800000000个状态必须减少状态数例例题111144这六种操作对一个数有两种影响，一种是交换两个数位的位置，另一种是改变某个数位的值。当且仅当光标到达某一数位，对这一数位的值的改变才可能发生，而且其发生的时间并不重要。所以全部操作可分为两种：一种是移位和交换操作，一种是增大和减小操作。例例题111145将操作分离成：先对原数的各数位重新排列（利用移位和交换操作），然后对光标到达过的位置进行增大或减小。问题转化：1.对每一种排列和光标到达情况，求出最少需要的操作数。(此过程与输入无关)2.求出在每一种排列下，需要的增大和减小操作的次数。(要求所有需要改变值的数位均被访问过)例例题111146状态数：8个位置40320种排列情况28种光标访问情况进一步缩小状态数：因为光标是连续移动的，所以除了第8位以外，假如某一位被访问过，则它之前的数位均被访问过。第8位可用右交换操作访问，不在此列由此得到14种光标访问情况现在状态数为8 40320 14,可以接受了例例题111147给出三个整数N、K和M你每次操作可以令N = N+M/N-M/N*M/N%M问最少多少次操作后有N % k = （N + 1）% k-1000 = N = 1000, 1 K = 1000, 0 M = 1000例例题121248广度优先搜索是否可以对于中间过程mod k？即(a op b) % K = (a % K) op b) % K ?当op为取余操作时不成立例例题121249对于%运算仅出现一次开头出现一次%开头出现 * % （结果为0）对于%操作，只有两种了 N % M，N*M%M=0,然后就是就是进行+， -， *，而且我们已经知道对于+，-，*可以直接一边取余一边运算例例题121250谢谢51