搜索算法例题讲解(good)

搜索算法例题讲解史宁 西安电子科技大学ACM基地例1：放苹果（POJ1664）Description 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不 放，问共有多少种不同的分法？（5，1，1和1，1，5是同一种 方法） Input 以下每行均包含二个整数M和N，以空格分开。1=sk-1) sk=n-w; z=z+1; return; for (i=0;i=sk-1) /如果当前放置的苹果个数大于前一个盘子继续放置 w=w+i; sk=i; k=k+1; dfs(k,w); w=w-i; k=k-1; 算法效率的分析n此算法的效率比较低，为指数级算法。效率 相当之低下，不过应对10以内的数据完全能 达到要求。n下面我们看一个剪枝。当剩下的苹果平均放 到剩余的盘子中的时候，每个盘子分的的苹 果数目小于前一个盘子放置的苹果数目，这 样就不满足我们给的要求ai-1=sk-1)sk=n-w;z=z+1;return;for (i=0;i=sk-1)sk=i;k=k+1;dfs(k,w);w=w-i;k=k-1; 优化前后的对比搜索题目小结n暴力搜索只能在很小的数据范围内使用，一 般情况下，所谓的暴力也就是枚举了所有的 状态，在这些状态中找到最终的解。在很多 情况下，搜索题目有以下几类：1.求所有状 态的个数，例如放苹果。2.找出所有解的状 态，例如把放苹果的每种方式求出来。3.求 其中一个可行解。4.求出所有可行解的最优 解。搜索小结二n搜索题目无外乎上面所说的几类，接下来我们来一一分析 下它们的特点。n求最终状态的个数n这个问题我们有时可以转化为一个组合问题n求出所有最终状态n这个问题是最麻烦，必须对状态空间进行全遍历n求出一种可行状态n这个相对简单，有时候可以用随机化或者当搜索到其中一个解的时 候停止搜索n求出最优可行状态n这个问题可以在问题2的基础上再对状态空间解进行一次扫描。也可 以转化成动态规划问题n当然以上都是些常规的解题思想，并不能代表所有问题都 是按照以上的方式进行求解。例2：Catch That Cow（POJ3278）n题目描述：给定一个n,k(0 0)spi2-1pi32=max(spi2-1pi32,spi2pi32+1); 以上代码表示能否向上扩展节点 pi2-1>0 /节点i的x坐标是否大于0 spi2-1pi31k) n binsearch(i,n-1,k);n elsen binsearch(n+1,j,k);n return k; n课后练习POJn1101 The Gamen1753 Flip Game n2312 Battle City n1011 Sticks n1233 Street Crossing n1324 Holedox Moving n1915 Knight Moves n1980 Unit Fraction Partition 总结n两种基本搜索形式需要掌握n深度优先搜索DFSn存储状态的结构为堆栈n广度优先搜索BFSn存储状态的结果为队列n种子填充法n推荐大家使用BFS实现n记忆化搜索n理解其思想，为动态规划的学习做铺垫西安电子科技大学ACM基地欢迎你的加入！