基本算法和经典问题选讲 中国科学技术大学 袁平波
基本算法和经典问题选讲 中国科学技术大学 袁平波
主要内容 穷举法 贪心法 回溯法
主要内容 • 穷举法 • 贪心法 • 回溯法
一、穷举法（枚举法） 列出问题的全部可能解，然后找到最佳解 例： 设有A、B、C、D四个数都在1~16范围 内。要求打印出四个数都不相同时，其和 为34的所有值。 算法分析： 最直接的想法是设置A、B、C、D四个变 量，都从1至16循环。需要164次。且循环 中还必须判四数有所重复的情况
一、穷举法（枚举法） • 列出问题的全部可能解，然后找到最佳解 • 例： 设有A、B、C、D四个数都在1～16范围 内。要求打印出四个数都不相同时，其和 为34的所有值。 • 算法分析： 最直接的想法是设置A、B、C、D四个变 量，都从1至16循环。需要164次。且循环 中还必须判四数有所重复的情况
加上一定的限制条件 设A<B<C<D,A的初值为1，B的初值为 A+1,C的初值为B+1,D的初值为C+1。 每个循环的终值也可以算出： A+A+1+A+2+A+3=34 A=7 1+B+B+1+B+2=34 B=10 1+2+C+C+1=34 C=15 1+2+3+D=34 D=28
加上一定的限制条件 • 设A<B<C<D，A的初值为1，B的初值为 A＋1，C的初值为B＋1，D的初值为C+1。 • 每个循环的终值也可以算出： A + A+1 + A+2 + A+3 = 34 A=7 1 + B + B+1 + B+2 = 34 B=10 1 + 2 + C + C+1 = 34 C＝15 1＋2＋3＋D＝34 D＝28
算法实现函数 void fournums() int a,b,c,d for (a 1;a<-7;a++) for(b=a+1;b<=l0;b++) for(c=b+1;c<=15;c++) for(d=c+1,d<=28,d++) if (a+b+c+d ==34)cout <<a,b,c,d
算法实现函数 void fournums() { int a, b, c, d ; for (a = 1; a<=7; a++) for (b = a+1; b<=10; b++) for (c = b+1; c<=15; c++) for (d = c+1; d<=28; d++) if (a+b+c+d == 34) cout <<a ,b,c,d }
二、贪心法 当一个问题的状态空间很大时，穷举法 计算量可能会太大。 当人们面对一个问题时，可能会采取目 前看来最接近解状态的选择方案。 有时运用最直接的方法，可能会得到很 好的效果
二、贪心法 • 当一个问题的状态空间很大时，穷举法 计算量可能会太大。 • 当人们面对一个问题时，可能会采取目 前看来最接近解状态的选择方案。 • 有时运用最直接的方法，可能会得到很 好的效果
贪心法一般原则 贪心法把构造可行解的工作分阶段来完成。在 各个阶段，选择那些在某些意义下是局部最优 的方案，期望各阶段的局部最优的选择带来整 体最优。 在某些情况下，贪心法得到的可能是最优解， 但更多的情况下，可能只是近似解。 有些问题，只有通过彻底地搜索才能得到最优 解，从而使得求得最优解的代价甚高。这时候， 也许求得一个与最优解相差不多的近似解（次 优解)就可以满足要求。此时选用贪心法较好
贪心法一般原则 • 贪心法把构造可行解的工作分阶段来完成。在 各个阶段，选择那些在某些意义下是局部最优 的方案，期望各阶段的局部最优的选择带来整 体最优。 • 在某些情况下，贪心法得到的可能是最优解， 但更多的情况下，可能只是近似解。 • 有些问题，只有通过彻底地搜索才能得到最优 解，从而使得求得最优解的代价甚高。这时候， 也许求得一个与最优解相差不多的近似解（次 优解）就可以满足要求。此时选用贪心法较好
例：多叉路口交通灯管理问题 十字交叉路口要设置红绿灯来维持交通 秩序，对于多叉路口需要设置几种颜色 的交通灯才能使车辆之间既不相互碰撞， 又能达到最大交通流量呢？ 假设有一个如下图所示的五叉路口，其 中道路C和E是箭头所示的单行道。我们 把可以同时行驶而不发生碰撞的路线用 一种颜色的交通灯指示，对于以下的13 种行驶路线，显然交通灯颜色越少则管 理效率越高
例：多叉路口交通灯管理问题 • 十字交叉路口要设置红绿灯来维持交通 秩序，对于多叉路口需要设置几种颜色 的交通灯才能使车辆之间既不相互碰撞， 又能达到最大交通流量呢？ • 假设有一个如下图所示的五叉路口，其 中道路C和E是箭头所示的单行道。我们 把可以同时行驶而不发生碰撞的路线用 一种颜色的交通灯指示，对于以下的13 种行驶路线，显然交通灯颜色越少则管 理效率越高
多叉路口交通灯管理问题(2) 13种行驶路线 AB.AC.AD BA.BC.BD DA.DB.DC EA.EB.EC,ED 不能同时行驶的路线 AB、BC等
多叉路口交通灯管理问题(2) • 13种行驶路线 – AB,AC,AD – BA,BC,BD – DA,DB,DC – EA,EB,EC, ED • 不能同时行驶的路线 – AB、BC等
多叉路口交通灯管理问题(3) 借助于“图”。图中一个顶点表示一种 行驶路线，行驶路线相互矛盾用顶点之 间的连线线“边”来表示。 原来的交通管理问题就变为：将图上顶 点分组，使得有边相连的顶点不能在同 一个组内。 如果把图上的一个顶点理解为一个国家， 顶点之间的连线表示两个国家有共同的 边界，这个问题也就是著名的地图着色 问题
多叉路口交通灯管理问题(3) • 借助于“图”。图中一个顶点表示一种 行驶路线，行驶路线相互矛盾用顶点之 间的连线线“边”来表示。 • 原来的交通管理问题就变为：将图上顶 点分组，使得有边相连的顶点不能在同 一个组内。 • 如果把图上的一个顶点理解为一个国家， 顶点之间的连线表示两个国家有共同的 边界，这个问题也就是著名的地图着色 问题