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