数学模型-贪心算法及实例课件

1、数学建模竞赛中十类常用算法1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性。2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。13. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lingo 软件求解。4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决。5. 动态规划、回溯搜索、分治算

2、法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。26. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。39.

3、 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。4贪心算法5 有下面几种面值的硬币：一元、五角、一角、五分、一分，假设要付给顾客2.89元的零钱，要求用最少的硬币。问题引入：6 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪

4、心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。7活动安排问题 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当s

5、ifj或sjfi时，活动i与活动j相容。10活动安排问题在下面所给出的解活动安排问题的贪心算法greedySelector :int greedySelector(int s, int f, boolean a) int n=s.length-1; a1=true; int j=1; int count=1; for (int i=2;i=fj) ai=true; j=i; count+; else ai=false; return count; 各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列 11活动安排问题 例：设待安排的11个活动的开始时间和结束时间按结束时间的非减

6、序排列如下：i1234567891011Si130535688212fi456789101112131412这个问题有三种看似合理的选择：1、每次选择剩余物品中价值最大的2、每次选择剩余物品中重量最轻的3、每次选择剩余物品中单位重量价值最高的。16用贪心算法解背包问题的基本步骤： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页： 17float knapsack(f

7、loat c,float w, float v,float x) int n=v.length; for (int i = 0; i n; i+) di = (wi,vi,i); MergeSort.mergeSort(d); int i; float opt=0; for (i=0;in;i+) xi=0; for (i=0;ic) break; xdi.i=1; opt+=di.v; c-=di.w; if (in) xdi.i=c/di.w; opt+=xdi.i*di.v; return opt; 18最优装载 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载

8、问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。1.算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。 19Void dijkstra(int v,float a,float dist)for (int i=1;i=n;i+) disti=avi;si=false;distv=0;sv=true;For (int I=1;In;I+) float temp=MAX_Value; int u=v; for (int j=1;j=n;j+) if(! sj)&distjtemp) u=j; temp=dist

9、j; su=true;For(int j=1;j=n;j+)if(! sj)&auj MAX_Value) if (distu+aujdistj) distj= distu+auj; 23单源最短路径例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下页的表中。24单源最短路径迭代Sudist2dist3dist4dist5初始1-10maxint3010011,2210603010021,2,441050309031,2,4,331050306041,2,4,3,5510503060Dijkstra算法的迭代过程： 25最小生成树 设G =(V,E)

10、是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 26最小生成树1.最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略

11、的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。 27最小生成树2.Prim算法 设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的

12、所有边恰好构成G的一棵最小生成树。 28最小生成树利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。 例如，对于右图中的带权图，按Prim算法选取边的过程如下页图所示。29最小生成树30最小生成树在上述Prim算法中，还应当考虑如何有效地找出满足条件iS,jV-S，且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。用这个办法实现的Prim算法所需的计算时间为 31最小生成树例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。34最小生成树关于集合的一些基本运算可用于实现Kruskal算法。 按权的递增顺序查看等价于对优先队列执行removeMin运算。可以用堆实现这个优先队列。 对一个由连通分支组成