搜索算法设计专题课件

1、清华大学李晓潇搜索本质 穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法如何穷举 问题拆分多个阶段 枚举每个阶段所有可能性图论 解空间（图） 每个阶段（结点） 阶段间的转移（边） 穷举解空间（遍历图）动态规划（记忆化搜索） 最优子结构，无后效性（拓扑图） 子问题重叠性（图中结点少）4S0tS1S2S3SnW0W1,1W1,2W2,1W2,2W2,3W3,3W3,2W3,1Wn,1Wn,2Wn,3Wn+1深度优先搜索（DFS） 记录路径上经过结点 标记访问过的结点剪枝方法 Hash判重 估价剪枝 alpha-beta剪枝 搜索顺序S0Sg605-333-3022-30-23

2、5 41-3068 9-30-33-3-3-21-36-30316011方块极大圆圈极小ab02极大节点的下界为。极小节点的上界为。剪枝的条件： 后辈节点的值祖先节点的值时， 剪枝 后辈节点的 值祖先节点的值时， 剪枝简记为： 极小极大，剪枝 极大极小，剪枝8486-315035-33-3022-30-2309-300-303305411-31661abcdefghijkmn取值范围小的优先搜索制约力强的优先搜索对解影响大的优先搜索 增加估价函数的准确度广度优先搜索（BFS） 队列维护搜索状态 避免重复入队剪枝方法 Hash判重时间复杂度 BFSDFS如何结合两个特点？渐进的深度优先搜索（ID

3、-DFS） 枚举搜索层数 加快DFS的搜索时间 便于估价剪枝 失败尝试额外时间的开销？启发式搜索（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)最小的结点 第一次碰到的解就是最优解 空间复杂度大Heap优化 加快最优扩展结点的寻找f(n)=g*(n)+kh(n) K为比例系数，控制速度和误差渐进启发式搜索（IDA*） ID+A*算法 在A*的基础上节

4、约空间 并且加快剪枝折半搜索（双向搜索）给定一个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覆盖集 NP问题搜索 双向链表 DancingLinksDfs()如果所有列被覆盖则输出解如果没有可以使用行输出无解枚举可使用行将有交集的行删去进入下一层搜索还原有交集的行给出一张N*M的带障碍的地图（N,M21）A和B在地图上的两点每一时刻A和B可以向周围的8个格子移动一步，或者原地不动但是A和B不能在移动的过程

5、中相碰，并且不能移动到障碍上问A和B交换位置所需最少时间。用(x1, y1, x2, y2)表示A在(x1, y1)，B在(x2, y2)的最小代价寻求最短路，解空间较小，直接BFS用给出的N（N6）个矩形覆盖一个WH的大矩形（可以重叠），使得覆盖的面积最大如何枚举覆盖方案 每个矩形都和其他的一个矩形紧挨着，或者和边界紧挨着 搜索放置顺序如何统计覆盖面积 容斥原理数轴上有N（N10）个点，最左边的点在原点。给出N个点任意两个点的距离，要求你还原这N个点，如果有多解输出字典序最小的解。最长边 原点到最右边点距离 确定最右点，删除最长边剩余最长边 某个新点到原点，或者到最右边的点的距离 枚举这两种

6、方案（字典序小的优先 把局面上新出现的距离都从集合中删除在一棵有根树上，A、B君轮流砍边。A君只能砍红边，B君只能砍黑边。边带权，砍边的人得到边的权值。令D=A的得分-B的得分，A试图使D最大化，B试图使D尽可能小。求最终得到的D。N=201005150终结节点：只剩根的情况。此时D(S)=0。边的情况：如果能通过砍边而连接起来的两个状态之间连一条有向边。图无环，且每个节点连出的边的数量为n阶的。节点数量：220要求把N（ N36）个人成相等的两组第i个人在第一组有ai的得分，在第二组有bi的得分要求第一组人的得分和第二组人的得分差距尽量小，并求字典序最小方案将N个人平均分为两部分对于前半部分

7、，令第一组人数比第二组多i，枚举所有分组方法，按照第一组比第二组多得分多少排序。对于后半部分，令第一组人数比分到第二组少i个，枚举，之后在表里二分查找合并后能使第一组人的得分和第二组人的得分差距尽量小的前半段分法，更新答案。问题要求设计一个m层的蛋糕，蛋糕的体积为N，蛋糕中每一层都是一个圆柱体，而且每一层的高度H和半径R均要比下一层的小对于给定的n和m，求蛋糕最少可能的表面积(不包括最下一层的下底面)大小。 由于R和H是从下到上递减，所以体积也是从下到上递减，因此选择从下到上的搜索顺序有利于判断当前情况是否可行。 此外，注意到表面积包括每层蛋糕的侧面积和裸露的顶面积。确定了最底层的蛋糕就确定了

8、每层蛋糕裸露的顶面积之和，需要考虑的只剩下每层蛋糕的侧面积。因此这样的搜索顺序有利于判断是否可能出现比已知最优解更优的解。给出一个用正三角形平铺的地图，若两个三角形有公共边，则称之为相连。把一个内部没有空洞的正三角形连通块称之为岛屿，若两个岛屿翻转或旋转后相同，那么称之为相同的岛屿现在你要回答下面两个询问： 给出一个有N个三角形的岛屿，问在增加一个正三角形后可以变成多少个不同的岛屿； 询问有多少个不同的且有N个三角形的岛屿。N10先对于第二类问题，我们可以看作第一类问题的扩展版 所有的N个三角形的岛屿都可以看作是由N-1个三角形的岛屿增加一个正三角形后得到的由于问题求的是最后所有不同的岛屿的外

9、围轮廓线（顺时针方向），因此，我们存储的时候也只要记录轮廓 在外围增加一个三角形的操作，即在一条原来的轮廓线上突出一个三角形（绿色部分）两种特殊情况 绿色的边在轮廓线相邻位置重复出现，所以要删掉往返走的轮廓线部分 紫色的边在廓线不相邻上相邻重复出现，因此构成了一个环，不是合法解。有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之

10、前（j1j2）相关是事件之间的二元关系P1和P2的本质不同当且仅当存在相关事件Q在其中先后位置不同给出每个人的事件序列Qi，和任意两个事件之间的相关关系，求本质不同的事件总数（保证总数小于1000000，N10, M15, Ci20）Q1,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?我们把

11、每个人的每个事件当作一个点，来构造一个有向图，图中存在边E(u,v)表示u事件比v事件先发生。首先根据定义，这个图一定是一个拓扑图，因为事件之间发生的先后关系不可能构成一个环。对于每个人来说，由于他的事件要按顺序发生，所以我们可以把他的所有事件点连成一条链。对于不相关的事件，不关心他们之间的先后顺序，不用连边。我们只在相关的事件之间连边，这些边的方向直接决定了当前世界轨迹的本质给出一个连通无向图，要求从1到M给每条边编号要求连出多条边的点，连出的所有边编号互质求一个可行的方案（点数小于50）相邻的数字一定是互质的DFS过程中一定是沿着图的边走的若按照DFS序编号，则每个点一定存在两条编号相邻的

12、边屏幕上有*个随机的数字，光标初始指向第一个数字，键盘上有6个键，功能如下： Swap0：光标位置不变，将光标所在位置的数字与1号位置的数字交换。 Swap1：光标位置不变，将光标所在位置的数字与8号位置的数字交换。 Up：光标位置不变，将光标所在位置的数字加1，如果该处数字为9，则按Up之后，数字不变 Down：光标位置不变，将光标所在位置的数字减1，如果该处数字为0，则按Down之后，数字不变； Left：光标左移一个位置，如果光标已经在1号位置上，则光标不动； Right：光标右移一个位置，如果光标已经在8号位置上，则光标不动。问将8个数改为我们所需的特定数字最少需要按几步直接进行搜索，

13、从初态开始，知道找到末态的最优解为止。无论空间，时间都行不通8个位置100000000个不同的数800000000个状态必须减少状态数这六种操作对一个数有两种影响，一种是交换两个数位的位置，另一种是改变某个数位的值。当且仅当光标到达某一数位，对这一数位的值的改变才可能发生，而且其发生的时间并不重要。所以全部操作可分为两种：一种是移位和交换操作，一种是增大和减小操作。将操作分离成：先对原数的各数位重新排列（利用移位和交换操作），然后对光标到达过的位置进行增大或减小。问题转化：1.对每一种排列和光标到达情况，求出最少需要的操作数。(此过程与输入无关)2.求出在每一种排列下，需要的增大和减小操作的次数。(要求所有需要改变值的数位均被访问过)状态数：8个位置40320种排列情况28种光标访问情况进一步缩小状态数：因为光标是连续移动的，所以除了第8位以外，假如某一位被访问过，则它之前的数位均被访问过。第8位可用右交换操作访问，不在此列由此得到14种光标访问情况现在状态数为8 40320 14,可以接受了给出三个整数N、K和M你每次操作可以令N = N+M/N-M/N*M/N%M问最少多少次操作后有N % k = （N + 1