第 1 章 贪婪算法
虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决
许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下 ，
为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达
到要求，这时就必须寻求另外的方法来求解该问题。
本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货
箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方
案。
1.1 最优化问题
本章及后续章节中的许多例子都是最优化问题（ optimization problem），每个最优化问题都包含一组限
制条件（ c o n s t r a i n t）和一个优化函数（ optimization function），符合限制条件的问题求解方案称为
可行解（ feasible solution），使优化函数取得最佳值的可行解称为最优解（ optimal solution）。
例 1-1 [ 渴婴问题] 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不
同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到 n 种不同的饮料。根据以前关于这
n 种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮
料赋予一个满意度值：饮用 1 盎司第 i 种饮料，对它作出相对评价，将一个数值 si 作为满意度赋予第 i 种
饮料。
通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要，但是不幸的是 ：
具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设 ai 是第 i 种饮料的总量（以盎
司为单位），而此婴儿需要 t 盎司的饮料来解渴，那么，需要饮用 n 种不同的饮料各多少量才能满足婴儿
解渴的需求呢？
设各种饮料的满意度已知。令 xi 为婴儿将要饮用的第 i 种饮料的量，则需要解决的问题是：
找到一组实数 xi（1≤i≤n），使 n ?i = 1si xi 最大，并满足：n ?i=1xi =t 及 0≤xi≤ai 。
需要指出的是：如果 n ?i = 1ai < t，则不可能找到问题的求解方案，因为即使喝光所有的饮料也不能使
婴儿解渴。
对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这些数学公式，可以对输入/ 输出
作如下形式的描述：
输入：n，t，si ，ai（其中 1≤i≤ n，n 为整数，t、si 、ai 为正实数）。
输出：实数 xi（1≤i≤n），使 n ?i= 1si xi 最大且 n ?i=1xi =t（0≤xi≤ai）。如果 n ?i = 1ai <t，则输出
适当的错误信息。
在这个问题中，限制条件是 n ?i= 1xi =t 且 0≤xi≤ai，1≤i≤n。而优化函数是 n ?i= 1si xi 。任何满足限制
条件的一组实数 xi 都是可行解，而使 n ?i= 1si xi 最大的可行解是最优解。
例 1-2 [装载问题] 有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样 ，
但货箱的重量都各不相同。设第 i 个货箱的重量为 wi（1≤i≤n），而货船的最大载重量为 c，我们的目的
是在货船上装入最多的货物。
这个问题可以作为最优化问题进行描述：设存在一组变量 xi ，其可能取值为 0 或 1。如 xi 为 0，则货箱
i 将不被装上船；如 xi 为 1，则货箱 i 将被装上船。我们的目的是找到一组 xi ，使它满足限制条件 n ?i =
1wi xi ≤c 且 x i ? {0, 1}, 1 ≤i≤n。相应的优化函数是 n ?i= 1xi 。
满足限制条件的每一组 xi 都是一个可行解，能使 n ?i= 1xi 取得最大值的方案是最优解。
例 1-3 [最小代价通讯网络] 城市及城市之间所有可能的通信连接可被视作一个无向图，图的每条边都被
赋予一个权值，权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点（城市）的
连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树，
而最优解是其中具有最小代价的生成树。
1
剩余63页未读，继续阅读
评论0