• 1. ACM程序设计之 搜索基础
  • 2. 搜索是竞赛中的通用解题法1.基本概念 2.搜索的基本方式 3.搜索的变形 搜索动态规划贪心构造图论约10%约15%约5%约5%约10%计算几何纯数学题数据结构其它约5%约20%约5%约25%
  • 3. 什么是搜索算法呢? 搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。 搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。
  • 4. 1.基本概念状态 状态转移 搜索树 状态空间 可行解 最优解
  • 5. 状态 对问题以及事物状态在某一发展阶段的数学描述 状态转移 问题从一种状态转移到另一种状态的操作
  • 6. 搜索树 以阶段中每一个状态作为一个点,状态之间的转移作为边,形成一个隐式图。 其中我们把初始状态看做根。那么我们的搜索过程实际上就是在对这个树的结点做遍历。 这棵树也可以称为状态空间
  • 7. 比如:二分查找2 3 4 5 6 8 12 20 32 45 65 74 86 95 100headmidtail
  • 8. 查找示意图:A[1]~A[15]A[1]~A[7]A[9]~A[15]A[1]~A[3]A[5]~A[7]A[1]~A[1]A[3]~A[3]……
  • 9. 思考:1、在一百万个元素里查找某个元素大约需要比较多少次?2、时间复杂度:O(logN)
  • 10. 可行解 最优解
  • 11. 2、搜索算法分类枚举算法 广度优先搜索(BFS) 深度优先搜索(DFS) 双向广度优先搜索 A*算法 回溯算法
  • 12. 枚举算法:最直接的搜索方法,列举问题的所有状态.然后从中找出问题的解 广度优先搜索:从初始状态开始,通过规则来生成第一层结点,同时检查生成结点中是否有目标结点.若没有则生成下一层接点,并检查是否有目标结点… 深度优先搜索:从初始结点开始扩展,按照某中顺序不断的向下扩展,直到找到目标状态或者是无法继续扩展
  • 13. 双向广度优先搜索:从两个方向同时开始进行搜索,两个方向的起始点分别为目标状态和初始状态. A*算法:一种典型的启发示搜索 F(n) = G(n) + H(n) G(n) 从起始点到结点n的最佳路径实际代价 H(n) 从结点n目标结点的估计代价
  • 14. 深度优先搜索 用堆栈存储 当前结点为下一次扩展结点的父结点0123456
  • 15. 搜索到的路径 0->1->3 0->1 -> 4 0->2 -> 5 0->2 -> 6
  • 16. void DFS(int curNode,int curDepth){ if(curNode == Target ) return ; if(curEdpth > MaxDepth)return; for(int i=0;i
  • 17. 广度优先搜索采用队列存储 每次扩展出当前结点的所有子结点0123456
  • 18. 广度优先搜索void BFS(int curNode,int curDepth){ while(front < rear) { ++front; for(i = 0; i < m; i++) { newNode = Expend(q[front].node) if(!Exist(newNode)) { q[rear++].node = newnode; } if(newNode == target) return ; } } return; }
  • 19. 搜索算法举例:八数码难题在3×3的方格棋盘上,分别放置了标有数字1、2、3、4、5、6、7和8的八个棋子5847362158473621 S0 初始 状态 Sg 目标 状态空出一个位置使棋子可以移动,形成不同的局面问题 要使棋盘进入某种预定局面应如何移动棋子
  • 20. 深度 优先 搜索 算法 举例2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 52 8 3 1 4 7 6 52 3 1 8 4 7 6 52 8 3 1 4 7 6 52 8 3 1 6 4 7 52 8 3 1 4 7 6 52 8 3 1 6 4 7 52 8 3 1 6 4 7 52 8 3 7 1 4 6 5 8 3 2 1 4 7 6 52 8 1 4 3 7 6 52 8 3 1 4 5 7 6 1 2 3 7 8 4 6 51 2 3 8 4 7 6 52 8 3 6 4 1 7 52 8 3 1 6 7 5 48 3 2 1 4 7 6 52 8 3 7 1 4 6 52 8 1 4 3 7 6 52 8 3 1 4 5 7 6123456789101112131 2 3 8 4 7 6 5目标0 层1 层2 层3 层4 层规则:空格上下左右下左右
  • 21. 广度 优先 搜索 算法 举例2 3 1 8 4 7 6 5125673目标840层1层2层3层 2 3 1 8 4 7 6 52 8 3 1 4 7 6 52 3 1 8 4 7 6 5下左右2 8 3 1 4 7 6 52 8 3 1 6 4 7 52 8 3 1 4 7 6 5下左右1 2 3 8 4 7 6 5下2 3 4 1 8 7 6 5下2 8 3 1 6 4 7 52 8 3 1 6 4 7 5左右2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5上下2 8 1 4 3 7 6 52 8 3 1 4 5 7 6 上下1 2 3 7 8 4 6 51 2 3 8 4 7 6 5下右规则:空格上下左右
  • 22. DFS & BFSDFS可以找出两个状态之间的一条路径 BFS可以找出两个状态之间的最短路径
  • 23. 回溯搜索是DFS的一种改进,更实用的搜索求解方法。 与DFS的区别 扩展结点时,DFS将所有子结点全部扩展出来,再选取最新的一个结点进行扩展。 回溯搜索只扩展所有子结点的其中一个,然后再以这一子结点去扩展下一个子结点,当某个结点不能再扩展出新结点的时候,就删除这个结点,用其父结点来扩展新的结点。 DFS最后寻找解的路径,回溯搜索路径即解路径 回溯法的最大优点 占用内存少,只需存取当前的一条搜索路径。 适用范围 要求所有解方案的问题 试探性求解问题中
  • 24. POJ3414给两个桶,两个桶的体积分别为A和B,要求用这个两个桶装出C体积的水,如果可以的话就输出装法,不可以的话就输出impossibie. A,B<=100, 并且是要求输出最少的步数和方法。
  • 25. 队列的应用很简单 关键的地方就是状态设计和判重
  • 26. 状态设计状态的设计固然要全面 这样才能表现出问题每个阶段的不同特征 但是广搜的空间问题往往决定了状态的设计必须精简
  • 27. 一个二维迷宫里,小白鼠从起始位置出发,希望经过最少的转弯来从出口出去。
  • 28. 由广搜的性质,我们决定将转弯数作为关键值进行搜索 但是中间的状态只用二维坐标(x,y)无法表示出小白鼠的朝向问题。于是再加一个描述符方向dir,于是状态变为(x,y,dir)便可全面表示出小白鼠的状态。
  • 29. 状态空间的优化状态压缩 设计优化
  • 30. POJ1753给定一个4*4的黑白棋盘的初始状态,判断能否通过满足一些给定的翻转规则,使得所有棋面的颜色都一样,如果可以,输出最小步数。
  • 31. 由于每个格子只有黑白两种状态,我们用0,1来分别表示 于是4*4的格子也只需要2^16=64K
  • 32. 状态判重一般的方法有两个 Map或者二分 Hash Map和二分是添加查找O(lgn)级别的 但是STL的map会有一个还可以接受的常数 Hash的添加查找都是期望O(1)的
  • 33. HashHash就是把一个node类型的对象映射到一个关键值key上,然后按照key的值分类储存。举个例子,把350个苹果放到400个盒子里,期望情况每个盒子都应该不超过一个。如此查找和添加就是期望O(1)的。
  • 34. 不过冲突是无法避免的 解决冲突的办法一般有两种 开散列 闭散列 我们一般选择开散列
  • 35. Struct hash_t{ node key; hash_t* next; }pool[MAXN],*pp=pool,*mark[M]; //M为hash表地址的大小 Int hash(node);//映射函数
  • 36. Void Insert(node t){ Int v=hash(t); pp->next=mark[v]; pp->key=t; mark[v]=pp++; } Bool find(node t){ int v=hash(t); for(hash_t *p=mark[v];p;p=p->next){ if(p->node==t)return true; } return false; }
  • 37. 标记数组也属于hash的一种 其中hash函数值就是数字本身
  • 38. DFS的优化如果只求一个可行解,那么找到以后就可以返回了。 判重在有些时候是有必要的。 在搜索树上,把一些不可能存在可行解或者更优解的树枝减掉。
  • 39. 剪枝可行性剪枝 最优性剪枝
  • 40. POJ1011 STICKS已知一些等长的木棍被切成,n个短木棍.现在要根据这些短木棍的长度来求接原来木棍的长度,由于可能有多组解,因此 要求求出最短的可能长度. 小木棍的个数不超过64 如:9 5 2 1 5 2 1 5 2 1 原来的可能最短长度为: 6 5+1 5+1 5+1 2+2+2
  • 41. 典型例题算法分析:由题目意思可知道要求的木棍最短长度一定在已经知道的木棍长度的最大值max和已知木棍的总和sum之间.因此可以从max到sum枚举一个长度来判断这些木棍能否构成这个长度.
  • 42. 剪枝1:分段数res肯定能被总长度sum整除 剪枝2:每段的长度不可能大于初始分段的最大值 剪枝3:将输入的数据从大到小排序,因为一支长度为L的完整木棍肯定比几支短木棍拼成的同样长度的用处小(短小的用途更灵活一点) 剪枝4 :找到结果之后在能返回的地方马上返回递归的上一层 剪枝5:相同长度的木棍不要搜索多次,用当前的这支搜下去得不出结果,那么用下一支同样长度的还是得不到结果
  • 43. 剪枝6:相当关键的剪枝,就是栽在这个剪枝上面两个多小时。判断当前长度是不是大于每段应该的长度,如果大于则没必要往下递归 剪枝7:不用说了,前面的肯定都用过了,所以从level+1开始 剪枝8: if(all-times+1
  • 44. 3.搜索的变形3.1记忆化搜索 3.2迭代加深搜索 3.3双向广度优先搜索 3.4周界搜索 3.5优先队列广搜 3.6A*搜索 3.7IDA*搜索 3.8Alpha-Beta减枝搜索
  • 45. 3.1记忆化搜索记忆化就是在搜索的过程中,对已算出的节点关键值进行记忆化,以减少下次再用到此节点时引起的重复搜索。
  • 46. POJ1163 The Triangle 给定一个三角形数塔 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 求最大的从顶部到底部的路线上的和
  • 47. PKU1088 滑雪给定高度矩阵,人可以向四周矮的地方滑,求最长路径的长度 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
  • 48. 记忆化和动态规划本质是一样的,只是一般情况下,状态求解有一个规则拓扑序的情况下我们会使用动态规划的形式,否则就使用记忆化搜索的形式
  • 49. 3.2迭代加深搜索这个东西是一般情况下是在不知道最短转移次数的情况下,为了弥补广搜的空间不足的问题所产生的搜索方法。 For(DEPTH=init();dfs();++DEPTH); 但是由于不知道上界,在问题无解的情况下回显的非常无助。
  • 50. For(DEPTH=init();dfs();++DEPTH); 但是由于不知道上界,在问题无解的情况下回显的非常无助。 值得一提的是这种搜索方法会对深度浅的层数进行多次重复搜索。所以并不推荐。
  • 51. *类似的搜索方法还有迭代加宽搜索和柱形搜索,由于都不是主流,跳之
  • 52. 3.3双向广度优先搜索这种方法用在已知起点终点,求最短转移次数的问题中。
  • 53. 如果按节点扩展,就会出现以下情况:
  • 54. 3.4周界搜索这种方法用在初始终止位置确定,但是多组数据中共用同一个起点或终点的情况。 如果目标节点是确定的,那么我们进行一次反向的搜索,把搜到的节点全部保存在一个表里。
  • 55. 如果正向搜索用BFS的话,那么反向的周界搜索必须按一个确定的层数作为上界进行搜索。 这个参数对搜索的效率的影响是巨大的,浅了正向的工作就大了,深了反向工作就大了,所以要慎重。建议取在估计深度的一半附近,具体的偏移修正根据数据组数而定。
  • 56. 3.5优先队列广搜优先队列就是一个有优先级的队列,出队顺序不再是按时间顺序,而是按优先级的大小。 所有操作都是O(lgn)级别的 Priority_queue PQ; PQ.top()队列里优先级最大元素 PQ.push(x)添加元素 PQ.pop()弹出元素 PQ.empty()测试是否为空
  • 57. 优先队列搜索就是贪心的每次取当前已扩展的最小耗费节点。 算法的正确性由每次取得的节点的耗费值不减来保证,所以转移代价不能是负的。此种搜索方法跟DIJKSTRA最短路算法本质也是一样的。只是思维角度不一样。
  • 58. 3.6A*搜索这是一个最常用的智能搜索方案。 先来介绍一下启发函数。
  • 59. S:一个状态 F(s):启发函数,表示从初始状态开始,经过状态s的路径上最少需要多少代价才可以找到终点之一。 G(s):从初始状态到当前状态s的最小代价 H(s):估价函数,从当前状态s到终点之一最少需要多少代价。 容易看出F(s)=G(s)+H(s)
  • 60. F(s),G(s),H(s)都是估计量,于是我们设F*(s),G*(s),H*(s)为他们对应的真实值(在程序结束前是未知的)。 由于H(s)是H*(s)的一个下界,且G(s)==G*(s),那么F(s)=G(s)+H(s)<=G*(s)+H*(s)=F*(s) 这样,F*(s)是我们所想知道的,于是我们只要按顺序考虑已扩展节点的F(s)值并依次扩展就可以保证在第一个F*(s)被确认之前不存在比它更小的F*(s’)。
  • 61. 于是我们只要保证一点,H()是相容的,即H(s)<=H*(s),我们的估价函数是真实值的一个下限便可以了。
  • 62. 理论上,如果启发信息充分,我们可以很快的找到所需状态。
  • 63. 易错点如果g(x)的转移费用不恒为1的话,必须等到f(x)第一个出堆才是真的最小结果
  • 64. 8数码问题H()可以设计成 max(不在目标位置的颜色块数-1,0)
  • 65. Poj1475:Pushing Boxes
  • 66. 将H()定为箱子从当前点到目标点的最短距离,这步是要以周界的方式从目标点开始BFS出来的。 这显然是一个下界了,而且在只有一个箱子的情况下效果还是比较好的。当然如果能把人的状态加入是更好了。
  • 67. POJ3732 Paint Me Less给定一张被染色的方格图,相邻同色的方格称为一个块,染色的条件是同一个块需要一起染。求一个可以将原图全部染成0色的一个最短染色方案。 图是4*4的,颜色有20种。
  • 68. 以不等于0的颜色数作为H(),用A*直接搞下来就可以了
  • 69. 3.7IDA*(迭代A*)这个算法是为了解决A*算法空间不足的问题的(A*显然是广搜的形式),解决方法自然是用时间来弥补。 这个方法综合了A*的启发函数和迭代加深搜索的特点。 用迭代加深的方法来解决最小上界不确定的情形 用 A*的启发函数来进行上界减枝。
  • 70. 由于只要有解就可以返回,所以也没有必要做判重,所以排序树就可以不用写了。当然做了更好。 而且深搜只用到栈,这样也省掉了堆。 于是IDA*的最大好处体现出来了,代码量少
  • 71. POJ3460 Booksort
  • 72. 3.8Alpha-Beta减枝搜索这类减枝是用在对弈类的题目上,假设双方都是足够聪明的条件下所用的搜索方法。 或者说做一些对弈项目的电脑下棋选择之类的事情才用的到的。
  • 73. 先说max-min局面
  • 74. 对奕情况下当然要使己方量化值最优,当然选择所有可以到达的状态里的最大值,这就是max局面。 但是对方也是足够聪明的,要预先估计这个聪明,就得默认对方是会选择对你最不利的情形,即在所有可达状态里选择最小的,这就是min局面。
  • 75. 于是利用这个max和min的特性我们可以做一些事情。
  • 76. 这个上下界减枝就叫Alpha-Beta减枝。 尤其在分叉数巨大的情况下,这个减枝有着强效。可以使原本计算量无法达到的搜索深度在同样时间内深入多倍。
  • 77. 一般的搜索中认为胜局局面为1负为-1,和棋为0。 但在分叉数很大的智能对奕的情况下应该用一个值来估计选择的好坏,也就是在深度达到一个定值的情况下来估计当前局面的形势。当然这个深度越深,做出的选择也越可靠。
  • 78. 局面估价函数的选择也决定了搜索的智能程度。 下面介绍一下经典估价函数
  • 79. ○×九宫棋,四子棋估价函数定为把空格的位置都放入己方棋子所连成的直线数
  • 80. 围棋,象棋,国际象棋当前局面上所放的己方棋子减去对方棋子数。其中后两者的棋子数是要加权才科学的。 其中后两者在还未达到深度上限的过程中如果王被吃了,就可以直接返回-INF或者吃王返回INF
  • 81. POJ3527 Generalized Connect Four 给定一个合法的四子棋局面,双方足够聪明,判定黑方选手胜利,失败或者平局
  • 82. 由于max-min局面所设计的就是考虑双方足够聪明的情况下的讨论。于是我们用Alpha-Beta所做出的判断就是精确解。 那么估价函数设为如果黑线出现那么返回1,白线出现返回-1,其他情况为0就可以了。
  • 83. 如果轮到黑方下就做max局面 白方下就做min局面 判断顶层的返回值就可以了
  • 84. Thanks to ACMaryland的关于BFS的精华讲义让我有勇气再次研究搜索……