贪心算法活动安排问题

《贪心算法活动安排问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、活动安排问题，对每项活动的按照结束时间非减序排列。然后选第一个。按照第一个的结束时间来看接下去怎么选，以此类推。•第一步：-选择活动1作为第一个被选中的活动，并将活动1的结束时间作为判断下一个活动是否被选中的依据；■1234567891011s[i]130535688212f[i]567891011121314•第二步：-判断活动2与活动1是否相容•即s[2雇否大于或等于耳口•1X34567891011s[i]130535688212f[i]567891011121314瞬隔疇哒踽束•第三步：-

2、判断活动3与活动1是否相容•即s[3雇否大于或等于f[1]；■1XX4567891011s[i]130535688212f[i]567891011121314结果，不相容，活动礙有被选中，活动1的结束时间仍作为判断下一个活动是否被选中的依据15•第四步：-判断活动4与活动1是否相容•即s[4]是否大于或等于■1XX567891011s[i]130535688212f[i]56(7)891011121314结果，相容，活动4被选中，活动4的结束时间将作为判断下一个活动是否被选中的依据贪心选择性质的

3、证明：1.活动安排问题的一个最优解是以贪心选择开始。即最优解包含第一个活动（叫做活动l）o证明：假设有一个最优解叫做A。它的活动也是以结束时间的非减序进行排列。假设A中第一个活动叫做K。如果K是我们的活动1,则A就是以活动1开始的。如果K不是活动1.则把K从A中去掉，并加上活动1,而且活动1是相容的是因为活动1的结束时间最早。所以证明了活动安排问题的一个最优解是以贪心选择开始。最优子结构的证明：把起始时间大于活动1的结束时间的活动去掉，A也可以把K去掉，这样子有一个递推的关系就是（总活动中）接下

4、去那个耳活动1相容的解必然可以相容在最优解（A・K）里血。（因它又可以化为一个贪心选择的开始）所以每一步做出的贪心选择将使得原问题化为规模变小的相似的子问题。