数学模型_贪心算法及实例

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

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

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

4、结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。8主要知识点：n活动安排问题n背包问题n最优装载n单源最短路径n最小生成树9活动安排问题 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。10活动安排问题 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同

5、一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。11活动安排问题在下面所给出的解活动安排问题的贪心算法greedySelectorgreedySelector :int greedySelector(int s, int f, boolean a) int n=s.length-1; a1=true; int

6、 j=1; int count=1; for (int i=2;i=fj) ai=true; j=i; count+; else ai=false; return count; 各活动的起始时间和结各活动的起始时间和结束时间存储于数组束时间存储于数组s s和和f f中且按结束时间的非减中且按结束时间的非减序排列序排列 12活动安排问题 例：例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011Si130535688212fi456789101112131413活动安排问题 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活

7、动i，否则选择活动i加入集合A中。 贪心算法并不总能求得问题的整体最优解整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。14 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?（假定物品可以分割成更小部分，亦即物品可以部分装入）背包问题15例：有5件物品，背包的容量为100，物品的重量和价值分别如下所示：12345W1020304050V203066406016这个问题有三种看似合理的选择：1、每次

8、选择剩余物品中价值最大的2、每次选择剩余物品中重量最轻的3、每次选择剩余物品中单位重量价值最高的。17用贪心算法解背包问题的基本步骤： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页： 18float knapsack(float c,float w, float v,float x) int n=v.length; for (int i = 0;

9、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; 19最优装载 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。1.1.算法描述算法描述最优装载问题可用贪心算法求解。采用重量

10、最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。 20float loading(float c, float w, int x) int n=w.length; for (int i = 0; i n; i+) di = (wi,i); MergeSort.mergeSort(d); float opt=0; for (int i = 0; i n; i+) xi = 0; for (int i = 0; i n & di.w = c; i+) xdi.i = 1; opt+=di.w; c -= di.w; return opt; 21单源最短路径给定带权

11、有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源源。现在要计算从源到所有其他各顶点的最短路长度最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单单源最短路径问题源最短路径问题。算法基本思想算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法。22单源最短路径其基本思想基本思想是，设置顶点集合S并不断地作贪心选贪心选择择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特

12、殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。23Void 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;

13、 temp=distj; su=true;For(int j=1;j=n;j+)if(! sj)&auj MAX_Value) if (distu+aujdistj) distj= distu+auj; 24单源最短路径例如例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下页的表中。25单源最短路径迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5初始初始1-10maxint301001 11,221060301002 21,2,44105030903 31,2,4,3310503060

14、4 41,2,4,3,5510503060Dijkstra算法的迭代过程： 26最小生成树 设G =(V,E)是无向连通带权图，即一个网络网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树最小生成树。网络的最小生成树在实际中有广泛应用。例如例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 27最小生成树1.1.最小生成树性质最小生成

15、树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的PrimPrim算法算法和KruskalKruskal算法算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质最小生成树性质：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MSTMST性质性质。 28最小生成树2.Prim2.Prim算法算法 设G=(V,E)是连通带权图，V=1,2,n。构造

16、G的最小生成树的Prim算法的基本思想基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最最小生成树小生成树。 29最小生成树利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合边集合T T始始终包含终包含G G的某棵最小生成的某棵最小生成树中的边树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。 例如例如，对于右图中的带权图，按PrimPrim算法算法选取边的过程如下页图所示。30最小生成树31最小生成

17、树在上述Prim算法中，还应当考虑如何有效地找出满如何有效地找出满足条件足条件i i S,jS,j V-SV-S，且权，且权cijcij最小的边最小的边(i,j)(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。用这个办法实现的Prim算法所需的计算时间计算时间为 )(2nO32void prim(int n,float c)s1=true; for (int i=

18、2;i=n;i+) lowcosti=c1i; closesti=1; si=false; for(int i=1;in;i+) min=MAX_Value; int j=1; for(int k=2;k=n;k+) if (lowcostkmin) &(!sk) min=lowcostk; j=k; sj=true; for(int k=2;k=n;k+) if(cjk,lowcostk)&(!sk) lowcostk=cjk; closestk=j; 33最小生成树3.Kruskal3.Kruskal算法算法Kruskal算法构造G的最小生成树的基本思想基本思想是，首先将G的n个顶点看成n个孤立