二、贪心法 当一个问题的状态空间很大时，穷举法 计算量可能会太大。 当人们面对一个问题时，可能会采取目 前看来最接近解状态的选择方案。 有时运用最直接的方法，可能会得到很 好的效果
二、贪心法 • 当一个问题的状态空间很大时，穷举法 计算量可能会太大。 • 当人们面对一个问题时，可能会采取目 前看来最接近解状态的选择方案。 • 有时运用最直接的方法，可能会得到很 好的效果
贪心法一般原则 贪心法把构造可行解的工作分阶段来完成。在 各个阶段，选择那些在某些意义下是局部最优 的方案，期望各阶段的局部最优的选择带来整 体最优。 在某些情况下，贪心法得到的可能是最优解， 但更多的情况下，可能只是近似解。 有些问题，只有通过彻底地搜索才能得到最优 解，从而使得求得最优解的代价甚高。这时候， 也许求得一个与最优解相差不多的近似解（次 优解)就可以满足要求。此时选用贪心法较好
贪心法一般原则 • 贪心法把构造可行解的工作分阶段来完成。在 各个阶段，选择那些在某些意义下是局部最优 的方案，期望各阶段的局部最优的选择带来整 体最优。 • 在某些情况下，贪心法得到的可能是最优解， 但更多的情况下，可能只是近似解。 • 有些问题，只有通过彻底地搜索才能得到最优 解，从而使得求得最优解的代价甚高。这时候， 也许求得一个与最优解相差不多的近似解（次 优解）就可以满足要求。此时选用贪心法较好
例：多叉路口交通灯管理问题 十字交叉路口要设置红绿灯来维持交通 秩序，对于多叉路口需要设置几种颜色 的交通灯才能使车辆之间既不相互碰撞， 又能达到最大交通流量呢？ 假设有一个如下图所示的五叉路口，其 中道路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) • 借助于“图”。图中一个顶点表示一种 行驶路线，行驶路线相互矛盾用顶点之 间的连线线“边”来表示。 • 原来的交通管理问题就变为：将图上顶 点分组，使得有边相连的顶点不能在同 一个组内。 • 如果把图上的一个顶点理解为一个国家， 顶点之间的连线表示两个国家有共同的 边界，这个问题也就是著名的地图着色 问题