搜索及其优化.

1、搜索及其优化 杨志灿 搜索 搜索树 初始状态 目标状态 状态的表示与扩展 图搜索 N皇后 搜索 状态的扩展顺序 深度优先搜索 DFS(Depth-First Search) 优先扩展新状态 递归/回溯/人工栈 宽度优先搜索 BFS(Breadth-First Search） 依状态的产生顺序扩展 队列 Spiders 通过将一棵树的某个节点与另一棵树的节点合并使两棵树 合并为新的树 给定n棵树，将其合并为一棵树，使新树的最长链尽量长， 输出长度 1=n=100， 树大小=100 CodeForces 120 F Spiders 新树的最长链等于n棵树最长链长度之和。 求最长链 从树的每个节点D

2、FS/BFS，不断更新最长链长度。 O(n2) 从树的任意一个节点DFS/BFS，找出距离最远的点P，从点P进行 DFS/BFS，再次求最远的点Q，PQ即为最长链。 O(n) DP O(n) 迭代加深搜索 DFS在一些问题模型中可能无限扩展 如8数码问题 增加深度限制：假设目标状态所处深度不超过某阈值。 问题条件或人为假设 当搜索深度到达阈值时直接剪枝，不再往下搜索。 迭代加深搜索 Iterative Deepening Depth-First Search 求最优/深度最低/步数最少解 不断放宽迭代深度限制 第一次找到的目标状态即为最优解 与DFS不同 何时用IDDFS而不用BFS 空间限制

3、极强时 时间限制内求较优解 计算机博弈、规划等 当状态的存储与表示比较麻烦/费时时 迭代加深搜索 效率对比 设解所在深度为d，每个状态都能扩展出b个状态。 BFS Nbfs=1+b+b2+bd = (bd+1-1)/(b-1) IDDFS (d+1)+d*b+(d-1)*b2+2bd-1+bd = b/(b-1) * (bd+1-1)/(b-1) - (d+1)/(b-1) = b/(b-1)*Nbfs - (d+1)/(b-1) 两种算法的扩展节点数渐进相同 双向广度搜索 从初始状态和目标状态两个方向BFS 用hash等方法将两者的搜索路径相接 例 八数码 双向广度搜索 效率对比 设解所在深

4、度为d，每个状态都能扩展出b个状态。 BFS Nbfs=1+b+b2+bd = (bd+1-1)/(b-1) Bidirectional BFS (1+b+b2+bd/2) * 2 = 2 * (bd/2+1-1)/(b-1) Hash/数据结构判重 Knight Moves 一个L*L的象棋棋盘，给定马的起点和终点，求最少步数 4 = L = 300 POJ 1915 可行性剪枝 在搜索的同时，实时判断是否可能存在可行解 若不可能存在任何可行解，进行剪枝 判断方法 放缩、放宽条件限制 举例 精确覆盖问题 重复覆盖问题 精确覆盖问题 Exact Cover Problem 全集X，X的子集的集

5、合为S 精确覆盖 S的子集S*，满足X中的每一个元素在S*中恰好出现一次 精确覆盖问题 求最小的精确覆盖 举例 数独 N皇后 NP完全问题 重复覆盖问题 Set Cover Problem 全集X，X的子集的集合为S 重复覆盖 S的子集S*，满足X中的每一个元素在S*中至少出现一次 重复覆盖问题 求最小的重复覆盖 举例 数独 八皇后 NP完全问题 最优性剪枝 在搜索的同时，实时判断是否可能存在比当前最优解更优 的解 若不可能存在比当前最优解更优的解，进行剪枝 判断方法 放缩、放宽条件限制 可用贪心/构造等方法预处理出一些较优解为最优性剪枝 提供方便 举例 精确覆盖问题 重复覆盖问题 飘飘乎数独

6、 飘飘乎数独共n行，每行的数字都由1m自然数填满（每 行中每个数字用且只能用一次） 3=n, m Ri+1且Hi Hi+1。 希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。 令Q = S 对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的 值），使S最小。 （除Q外，以上所有数据皆为正整数） N = 10000, M = 20 NOI 1999 生日蛋糕 体积V = R2H 侧面积A = 2RH 底面积A = R2 DFS 从下到上确定每层蛋糕的半径与高度 可行性剪枝 最大化体积 N 最优性剪枝 最大化表面积 堆/平衡树 优点 相比盲目搜索，更快搜索到较/最优解 使最优性剪枝更强，避

7、免大量无用搜索/分支 A算法 八数码问题 h(n) 不在位的数字个数 不在位的数字的距离和 h(n)=0 无后效性 动态规划 Dijkstra A算法可能/需要重复扩展节点 极端举例：h是随机值 A*算法 若满足h(n)=h*(n)，则称为A*算法 A*第一次扩展目标节点t时，就找到了最优解 要求耗散值均为非负数 证明顺序： 在有限问题中，若存在可行解，A算法一定成功结束 A*结束前，必存在f(n)f*(s)的待扩展节点（n是在最佳路径上的 节点） A*选作扩展的任一节点n，有f(n)f*(s) 任一f(n)h1(n)） 则A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节 点至少和A

8、2一样多 K短路 在有向/无向有权无负环图中，求s到t的K短路 两条路不同，当且仅当访问节点序列不同 解法 h(n)为n到t的最短路 从t出发倒着做一遍最短路求h() 第i次扩展目标节点t时即为i短路 只需维护f值前k小的待扩展节点 传教士和野人 N个传教士和N个野人准备渡河，河岸有一条船，每次至 多可供k人乘渡 为了安全起见，任何时刻在河的两岸以及船上的野人数目 总是不超过传教士的数目（但允许在河的某一岸只有野人 而没有传教士） 求最少摆渡次数 传教士和野人 启发式搜索 常用方法 优先搜索分支少、限制多的 精确覆盖问题 重复覆盖问题 优先搜索更有可能出最优解的 A算法 A*算法 myster

9、ious permutation 给定一数字串，求有多少分隔方法，使其成为从1开始的 自然数的全排列 例：13927111104831265 排列1：13,9,2,7,1,11,10,4,8,3,12,6,5 排列2：13,9,2,7,11,1,10,4,8,3,12,6,5 数字串长度不超过192 mysterious permutation 数字串长度不超过192 数字从1至多到100 直觉上可行解数目不多 搜索 预处理筛出无解情况 数字个数不对 某个数字从没出现过 多于5个相同连续数字 mysterious permutation 只需搜索11至99的位置 因没有前导零，故100和整十的位置固定 搜索完二位数和三位数后，1至9必然有且只有一种填法 优先搜索可填入位置少的数字 实时维护可填入位置数 攻占黄金乡 一个长方体空间，用(0,0,0)(n-1,m-1,k-1)表示里面的 每一个单位区域 t艘不同等级的战舰出现在t个不同的区域，从战舰上涌出 山羊。 每一个单位时刻，山羊们会从自己所在的区域向四周6个 方向扩展一个区域（如果那个相邻的区域已经被占领了， 就不扩展），如