贪心算法求解区间覆盖问题.docx

《贪心算法求解区间覆盖问题.docx》由会员分享，可在线阅读，更多相关《贪心算法求解区间覆盖问题.docx（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析与设计试验报告第5次试验区间掩盖时间4. 28下午地点软件大楼109试验名称贪心算法求会场支配问题试验目的通过上机试验，要求把握贪心算法的思想，解决会场支配的问题并且实 现。试验原理贪心算法重要的两共性质：贪心选择性质和最优子结构性质。从问题的某一个初始解动身逐步靠近给定的目标，以尽可能快的地求得更好 的解。当达到某算法中的某一步不能再连续前进时，算法停止。1 .建立数学模型来描述问题。2 .把求解的问题分成若干个子问题。3 .对每一子问题求解，得到子问题的局部最优解。4 .把子问题的解局部最优解合成原来解问题的一个解。在这个试验当中，将会场的开头和结束的时间都用vector向量来表示

2、， 然后将将开头的值用bool变量表示，开头时间是true,结束时间是false,依 次检索,运用推断语句 if (i=nTxi. tmax)对这些会议的时间进行推断，然后看是否需要添加会议室；再在进行推断；试验步骤步骤如下：1、首先定义数据结构：以时间为核心，定义结构体point,它拥有两个属性， t是时间，f表示是开头时间还是结束时间；2、对全部对象按时间大小排序；3、依次计算，假如是开头时间则count+,假如是结束时间则count-,其中 最大的count即是最少的会场数。count表示目前开头且未结束的活动数；struct point(int t;bool f;);bool cmp(

3、point x,point y)(return x. ty. t;)关键代码int greedy(vector x)(int max=0, cur=0, n二x. size ();sort (x. begin (), x. end (), cmp);for(int i=0;in;i+)(if (xi. f)cur+;elsecur;if (i=n-l | xi. tmax 且xi=xi+l时，i时间确定是开头时间，i + 1时间可能是开头时间，也可能是结束时间假如是结束时间，说明某活动开头时间和结束时间相同，不需要会场，故不对max更新;假 如是开头时间，那在i+1次更新max效果一样retu

4、rnmax;因此i次不进行更新测试结果 3 E:学习算法分析与没计实验课第五次实验课会场安排问爱l.exe.n叫Tg51 2312 2825 35 2? 8036 503.一 一试验心得关于运用贪心算法来球会议场地的问题，这个问题主要是需要计算的是上一个 会场的结束时间与下一个会场的开头时间会不会重合，所以在这里我奇妙的运 用了 vector向量来表示会议的开头于结束的时间，然后依据bool来检索会议 的开头于结束时间，然后推断是否时间重合，然后再来推断是否需要再添加会 议室，在这个试验中最奇妙的还是要运用vector函数来推断，所以试验的过 程中需要我们精密的思索问题，将问题简化才是最重要的

5、。试验得分助教签名附录：完整代码/4d5贪心算法单源最短路径问题ttinclude ttinclude ttinclude using namespace std;const int N = 5;const int M = 1000;ifstream fin(“4d5 txt);templatevoid Di jkstra(int n, int v, Type dist , int prev, Type cN+l);void Traceback(int v, int i, int prev);输出最短路径 v 源点,i 终点int main ()int v = 1;源点为 1 .int dis

6、t N+l, prevN+l, cN+l N+l;cout有向图权的矩阵为：endl;for (int i=l; i=N; i+)(for (int j=l; j=N; j+)(finci j;coutci Ejz)coutendl;)Di jkstra(N, v, dist, prev, c);for (int i=2; i=N; i+)(cout源点1到点*i的最短路径长度为:其路径为;Traceback(l, i, prev);coutendl;return 0;template void Di jkstra(int n, int v, Type dist , int prev, Typ

7、e cN+l)(bool sN+l;.for (int i=l; i=n; i+)(disti = cv i表示当前从源到顶点i的最短特别路径长度si = false;if(disti = M)(previ = 0;纪录从源到顶点i的最短路径i的前一个顶点)else(previ = v;)distv = 0;v = true; 源到本身的距离是0；for(int i=l; in; i+)int temp = M;int u = v; 上一顶点取出V-S中具有最短特别路径长度的顶点u for (int j=l; j=n; j+)(if(!sj) & (distjtemp)temp = distj

8、;su = true;依据作出的贪心选择更新Dist值for (int j=l; j=n; j+)(if(!sj) & (cu jM)Type newdist = distu + cuj;if(newdist i;会场支配问题（贪心算法）/input, txt/5 /I 23/12 28/25 35/27 80/36 50/output.txt/3ttinclude ttinclude ttinclude using namespace std;struct point(int t;bool f;);bool cmp(point x,point y)(return x. ty. t; int

9、greedy(vector x)int max=O, cur=O, n=x. size();sort (x. begin (), x. end (), cmp);for (int i=0;in;i+)(.if (xi. f)cur+;elsecur；if (i=n-l | | xi. tmax)处理 xi=xi+l的状况max=cur;当 curmax 且 xi=xi+l时,i时间确定是开头时间，i+1时间可能是开头时间，也可能是结束时间假如是结束时间，说明某活动开头时间和结束时间相同，不需要会场，故不对max更新;假如是开头时间，那在i+1次更 新max效果一样max;return因此i次不

10、进行更新int main ()vector x;int n, i;point temp;while (cinn, n)for(i=0;iajl) t=ai ;ai=aj ;aj=t;)max=k+aO;for (i=l;in;i+)if(maxai)temp. f=true;cintemp. t;x. push_back (temp);temp. f=false;cintemp. t;x. push_back (temp);)coutgreedy (x) endl;x. clear ();)return 0;区间掩盖问题#include#includeusing namespace std;i

11、nt main()int n, k, i, j, aElOOOO, t, max, sum=l;cinnk;for(i=0; in; i+)cinai;for(i=0;in;i+) for(j=i+l;jaj) t=ai ;ai=aj ;aj=t;)max=k+aO;for(i=l;in;i+)(if(maxai) max=ai+k;,sum+;.)coutsumendl;return 0; max=ai+k;SUD1+;)测试结果3 E:学习、算法分析与没计实给课逢五次实验课区间蔡美问题Lexe 口 |回|目!5 31 3 8 5 113Process exited after 21.04

12、seconds with return ualue 0请按任意键继续.试验心得关于运用贪心算法来求区间掩盖的问题，其实这个问题和会议场地的问题是类 似的，依次用k来衡量是否达到了最终一个坐标值，假如没有达到，那么我们 就加k,依次进行计数，所以这个过程中最重要的就是运用了贪心算法的核心 思想。试验得分助教签名算法分析与设计试验报告第5次试验最短路径姓名杨玉茹学号202208010325班级计科1503时间4. 28下午地点软件大楼109试验名称贪心算法求最短路径试验目的通过上机试验，要求把握贪心算法的思想，采用Dijkstra算法求解最短 路径并实现。试验原理Dijkstra算法是解单源最短路

13、径问题的贪心算法。基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶 点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含 有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从 源到u的特别路径，并用数组dist纪录当前每个顶点所对应的最短特别路径 长度。Dijkstra算法每次从V-S中取出具有最短特别路长度的顶点u,将u 添加到S中，同时对数组dist作必要的修改。一旦S包含了全部V中顶点， dist就纪录了从源到全部其他顶点之间的最短路径长度。Dijkstra算法可描述如下，其中输入带权有向图是G=(V,E), V=1,2,， n),顶点v

14、是源。c是一个二维数组，表示边(i, j)的权。当(i,j)不 属于E时，ci j是一个大数。disti表示当前从源到顶点i的最短特别路 径长度。在Dijkstra算法中做贪心选择时，实际上是考虑当S添加u之后， 可能消失一条到顶点的新的特别路，假如这条新特别路是先经过老的S到达顶 点u,然后从u经过一条边直接到达顶点i,则这种路的最短长度是 distu+cu i。假如 distu+cu idisti,则需要更新 disti的值。试验步骤步骤如下：(1)用带权的邻接矩阵c来表示带权有向图，表示弧vi,vj上的 权值。设S为已知最短路径的终点的集合，它的初始状态为空集。从源点V经 过S到图上其余

15、各点Vi的当前最短路径长度的初值为:disti=cvi, vi 属于V.(2)选择 vu,使得 dist u=Mindist ivi 属于 V-S, vj 就是长度最短的最短路径的终点。令S二S U u.(3)修改从v到集合V-S上任一顶点vi的当前最短路径长度:假如 distu+cu j distj则修改 distj= distu+cu j.(4)重复操作(2), (3)共n-l次.关键代码templatevoid Dijkstra(int n, int v,Type dist, int prev,Type cN+l)bool sN+l;for (int i=l; i=n; i+)(dist

16、i - cv i ;disti表小当前从源到顶点i的最短特别路 径长度si= false;if (disti = M)(previ二0;纪录从源到顶点i的最短路径i的前一个顶点else(previ = v;)dist v = 0;sv=true; 源到本身的距离是0；for(int i=l; in; i+)int temp = M;int u=v;上一顶点取出V-S中具有最短特别路径长度的顶点u for(int j=l; j=n; j+)(if(!sj) & (distjtemp)(U = j；temp = dist j;)su = true;依据作出的贪心选择更新Dist值for(int j

17、=l; j=n; j+)(if(!sj) & (cujM)(Type newdist = distu + cuj;测试结果试验心得if(newdist 3eu- 甘咯泽为45径为1-5源点1到点4的曩短皤径长度为:2293252,其粮宜 源点1到点5的取短路径长度为：1979446784,其由Process exited after 0.5235 seconds with return value 0 请按任意键继续.关于运用贪心算法求解单源最短路径的问题，其实Dijkstra算法就是一个贪 心算法，但是由于求单源最短路径是一个过程比较简单的问题，而且这个算法 也实质上是一个广度优先算法，所以

18、在进行比较的时候，思维就会变得比较混 乱，但是可以讲二将这些比较的步骤也许分为两个步骤，首先从源点v经过S 到图上其余各点vi的当前最短路径长度的初值为：disti=cvi, vi属 于V.假如某个元素被纳入源点的时候，那么相应的Si就为true；然后再修改从V到集合V-S上任一顶点vi的当前最短路径长度：假如 distu+cu j distj则修改 distj= distu+cu j,依次进行循 环即可，所以其实在最开头将思路理清，那么我们就可以进行写代码了。姓名杨玉茹学号OAQOAOA no Q r班级计科1503试验得分助教签4zOzzOol) LOozb 7算法分析与设计试验报告第5次试验会场支配