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

9
活动安排问题
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求 使用同一资源，如演讲会场等，而在同一时间内只有一个 活动能使用这一资源。每个活动i都有一个要求使用该资源 的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动 i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与 区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说， 当si≥fj或sj≥fi时，活动i与活动j相容。
3
9. 数值分析算法。如果在比赛中采用高级语言进行编 程的话，那些数值分析中常用的算法比如方程组 求解、矩阵运算、函数积分等算法就需要额外编写库 函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关， 即使问题与图形无关，论文中也会需要图片来说明 问题，这些图形如何展示以及如何处理就是需要解决 的问题，通常使用MATLAB 进行处理。
贪心算法并不总能求得问题的整体最优解。但对 于活动安排问题，贪心算法greedySelector却总能求 得的整体最优解，即它最终所确定的相容活动集合A 的规模最大。这个结论可以用数学归纳法证明。
13
背包问题
给定n种物品和一个背包。物品i的重量是Wi， 其价值为Vi，背包的容量为C。应如何选择装 入背包的物品，使得装入背包中物品的总价值 最大?（假定物品可以分割成更小部分，亦即 物品可以部分装入）
具体算法可描述如下页：
17
float knapsack(float c,float w[], float v[],float x[]) { int n=v.length; for (int i = 0; i < n; i++) d[i] = (w[i],v[i],i); MergeSort.mergeSort(d); int i; float opt=0; for (i=0;i<n;i++) x[i]=0; for (i=0;i<n;i++) { if (d[i].w>c) break; x[d[i].i]=1; opt+=d[i].v; c-=d[i].w; } if (i<n){ x[d[i].i]=c/d[i].w; opt+=x[d[i].i]*d[i].v; } return opt; }
4
贪心算法
5
问题引入：
有下面几种面值的硬币：一元、五角、 一角、五分、一分，假设要付给顾客 2.89元的零钱，要求用最少的硬币。
6
顾名思义，贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从整体最优考虑，它所作出的 选择只是在某种意义上的局部最优选择。当然，希望 贪心算法得到的最终结果也是整体最优的。虽然贪心 算法不能对所有问题都得到整体最优解，但对许多问 题它能产生整体最优解。如单源最短路经问题，最小 生成树问题等。在一些情况下，即使贪心算法不能得 到整体最优解，其最终结果却是最优解的很好近似。
if (s[i]>=f[j]) {
各活动的起始时间和结 束时间存储于数组s和f
a[i]=true; j=i; count++;
中且按结束时间的非减 序排列
}
else a[i]=false;
}
return count;
}
11
活动安排问题
例：设待安排的11个活动的开始时间和结束时间按结 束时间的非减序排列如下：
10
活动安排问题
在下面所给出的解活动安排问题的贪心算法greedySelor(int s[], int f[], boolean a[])
{
int n=s.length-1;
a[1]=true;
int j=1;
int count=1; for (int i=2;i<=n;i++) {
i 1 2 3 4 5 6 7 8 9 10 11 S[i] 1 3 0 5 3 5 6 8 8 2 12 f[i] 4 5 6 7 8 9 10 11 12 13 14
12
活动安排问题
若被检查的活动i的开始时间Si小于最近选择的活动j 的结束时间fi，则不选择活动i，否则选择活动i加入集 合A中。
14
例： 有5件物品，背包的容量为100，物品的重量 和价值分别如下所示：
12345 W 10 20 30 40 50 V 20 30 66 40 60
15
这个问题有三种看似合理的选择： 1、每次选择剩余物品中价值最大的 2、每次选择剩余物品中重量最轻的 3、每次选择剩余物品中单位重量价值最高的。
2
6. 最优化理论的三大非经典算法：模拟退火算法、神 经网络算法、遗传算法。这些问题是用来解决一 些较困难的最优化问题的，对于有些问题非常有帮助， 但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算 法，在很多竞赛题中有应用，当重点讨论模型本 身而轻视算法的时候，可以使用这种暴力方案，最好 使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的， 数据可以是连续的，而计算机只能处理离散的 数据，因此将其离散化后进行差分代替微分、求和代 替积分等思想是非常重要的。
16
用贪心算法解背包问题的基本步骤：
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪 心选择策略，将尽可能多的单位重量价值最高的物品装 入背包。若将这种物品全部装入背包后，背包内的物品 总重量未超过C，则选择单位重量价值次高的物品并尽可 能多地装入背包。依此策略一直地进行下去，直到背包 装满为止。
7
主要知识点：
活动安排问题 背包问题 最优装载 单源最短路径 最小生成树
8
活动安排问题
活动安排问题就是要在所给的活动集合中选出最 大的相容活动子集合，是可以用贪心算法有效求解的 很好例子。该问题要求高效地安排一系列争用某一公 共资源的活动。贪心算法提供了一个简单、漂亮的方 法使得尽可能多的活动能兼容地使用公共资源。
数学建模竞赛中十类常用算法
1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通 过计算机仿真来解决问题的算法，同时可以通过模拟 来检验自己模型的正确性。 2. 数据拟合、参数估计、插值等数据处理算法。比赛 中通常会遇到大量的数据需要处理，而处理数据的关 键就在于这些算法，通常使用MATLAB 作为工具。
1
3. 线性规划、整数规划、多元规划、二次规划等规划 类算法。建模竞赛大多数问题属于最优化问题，很多 时候这些问题可以用数学规划算法来描述，通常使用 Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、 网络流、二分图等算法，涉及到图论的问题可以用这 些方法解决。 5. 动态规划、回溯搜索、分治算法、分支定界等计算 机算法。这些算法是算法设计中比较常用的方法， 竞赛中很多场合会用到。