数据结构算法与应用-c++语言描述13

《数据结构算法与应用-c++语言描述13》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、下载第三部分算法设计方法第13章贪婪算法离开了数据结构的世界，现在进入算法设计方法的世界。从本章开始，我们来研究一些算法设计方法。虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。本书的第13~17章提供了五种基本的算法设计方法：贪婪算法、分而治之算法、动态规

2、划、回溯和分枝定界。而其他的常用高级方法如：线性规划、整数规划、遗传算法、模拟退火等则没有提及。有关这些方法的详细描述请参见相关书籍。本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。13.1最优化问题本章及后续章节中的许多例子都是最优化问题（optimizationproblem），每个最优化问题都包含一组限制条件（constraint）和一个优化函数（optimizationfunctio

3、n），符合限制条件的问题求解方案称为可行解（feasiblesolution），使优化函数取得最佳值的可行解称为最优解（optimalsolution）。例13-1[渴婴问题]有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n种不同的饮料。根据以前关于这n种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值：饮用1盎司第i种饮料，对它作出相对评价，将一个数值s作为满意度赋予第i种饮料。

4、i通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要，但是不幸的是：具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i种饮料的总量（以盎司为单位），而此婴儿需要t盎司的饮料来解渴，那么，需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢？设各种饮料的满意度已知。令x为婴儿将要饮用的第i种饮料的量，则需要解决的问题是：inn找到一组实数x（1≤i≤n），使åsx最大，并满足：åx=t及0≤x≤a。iiiiiii=1i=1n需要指出的是：如果åa

5、案，因为即使喝光所有的饮料也ii=1不能使婴儿解渴。406第三部分算法设计方法下载对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这些数学公式，可以对输入/输出作如下形式的描述：输入：n，t，s，a（其中1≤i≤n，n为整数，t、s、a为正实数）。iiiinnn输出：实数x（1≤i≤n），使åsx最大且åx=t（0≤x≤a）。如果åa

6、一组实数x都是可行解，而使åsx最大的可行解是最优解。iiii=1例13-2[装载问题]有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样，但货箱的重量都各不相同。设第i个货箱的重量为w（1≤i≤n），而货船的最大i载重量为c，我们的目的是在货船上装入最多的货物。这个问题可以作为最优化问题进行描述：设存在一组变量x，其可能取值为0或1。如x为0，ii则货箱i将不被装上船；如x为1，则货箱i将被装上船。我们的目的是找到一组x，使它满足iinn限制条件åwx≤c且xÎ{0,1},1≤i≤n。相应的优化函数是

7、åx。iiiii=1i=1n满足限制条件的每一组x都是一个可行解，能使åx取得最大值的方案是最优解。iii=1例13-3[最小代价通讯网络]这个问题曾在例12-2介绍过。城市及城市之间所有可能的通信连接可被视作一个无向图，图的每条边都被赋予一个权值，权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点（城市）的连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树，而最优解是其中具有最小代价的生成树。在这个问题中，需要选择一个无向图中的边集合的子集，这个子集必须满足如下限制条

8、件：所有的边构成一个生成树。而优化函数是子集中所有边的权值之和。13.2算法思想在贪婪算法（greedymethod）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy