彩灯题小结 3、枚举vs.搜索 ◆效率比较: 枚举本质上属于搜索算法 ■行遍所有可能 合理的顺序和剪枝可以提高效率 结论: ·对阿题进行分析,你会发现需要枚举的东西 ◆枚举的适用范围 往往没有想象的那么多 1.可预先确定解的个数n 2.解变量A,A2,…,Aq的值的可能变 ◆小试牛刀 化(范围预先确定) http:/lacmpku.edu.cn/judgeonline/showproblemPRoblemide 结论 四皇后问题及其解空间树 枚举是一种非常基本的算法思想 实现简单 常用实现方法:多循环(fo循环,whil循环) 效率较低 对问题多加分析,减少循环数和次数 是否有其它更好的方法? 回测法、分支限定法是枚举法的推广 课堂讨论 枚举和字符串操作 ◆每个字母都有一个权值 http://acmpku.edu.cn/judgeOnline/showproblem?p ◆给定字母表,表中字符可以重复 roblem id=1171(Letter Game) 给定一个字典 字典的大小不超过4000 给定单词长度不超过75 彩灯题小结 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id= 1222 26 230 Š 效率比较： Š 小试牛刀： Š 结论： VS Š 对问题进行分析，你会发现需要枚举的东西 往往没有想象的那么多。 3、枚举 vs. 搜索 Š 枚举本质上属于搜索算法 „ 行遍所有可能 „ 合理的顺序和剪枝可以提高效率 Š 枚举的适用范围 „ 1．可预先确定解的个数n „ 2．解变量Al，A 2， …，Aq的值的可能变 化（范围预先确定） 结论 Š 枚举是一种非常基本的算法思想 „ 实现简单 z 常用实现方法：多重循环（for循环，while循环） „ 效率较低 z 对问题多加分析，减少循环重数和次数 z 是否有其它更好的方法？ z 回溯法、分支限定法是枚举法的推广 四皇后问题及其解空间树 1 2 4 3 5 6 7 4 3 9 8 10 11 12 2 4 4 2 3 14 13 15 16 17 2 3 3 2 4 X1=1 18 20 19 21 22 23 3 4 4 3 1 25 24 26 27 28 1 4 4 1 3 30 29 31 32 33 1 3 3 1 4 2 34 36 35 37 38 39 2 4 4 2 1 41 40 42 43 44 1 4 4 1 2 46 45 47 48 49 1 2 2 1 4 3 50 52 51 53 54 55 2 3 3 2 1 57 56 58 59 60 1 3 3 1 2 62 61 63 64 65 1 2 2 1 3 4 X2=2 X3=3 X4=4 Q Q Q Q 课堂讨论 Š 一、枚举和字符串操作 http://acm.pku.edu.cn/JudgeOnline/showproblem?p roblem_id=1171 (Letter Game) Š 每个字母都有一个权值 Š 给定字母表，表中字符可以重复 Š 给定一个字典 „ 字典的大小不超过40000 „ 给定单词长度不超过7