贪心算法-----单线程:活动安排问题 多线程:多机调度问题

一、贪心算法的特点

顾名思义,贪心算法总是做出在当前看来是最好的选择。虽然贪心算法并不从整体最优上加以考虑,它所做出的选择只是在某种意义上的局部最优选择。

贪心算法的优点是更简单,更直接且解题效率更高,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好的近似解。

二、贪心算法的理解

由于涉及到在做出在当前看来最好的选择,所以会经常采用排序算法,推荐使用快速排序算法,复杂度是O(nlgn),且在同等复杂度算法中效率是最高的,

本文涉及的排序都采用冒泡排序,只是注明需要排序而已。

贪心算法可以从“单线程”还是“多线程”这个角度划分问题。例如:

(1)单线程问题

“活动安排问题”:由于规定使用同一资源,且活动不会同时进行,即同一时间内只有一个活动能使用这一资源,需要对活动开始和结束时间进行排序,即单线程问题;

“背包问题”:注意不是经常所见的0-1背包问题,它的特点是可以选择物品i的一部分,而不是0(不选择)和1(选择)。这种情况下根据每种物品单位重量的价值

作为排序的对象。同理,只有一个背包,所以属于单线程问题;

“最优装载问题”:是将一批集装箱装上有重量限制的轮船,无体积限制,此时需要对重量从小到大排列,同理只有一艘轮船,所以属于单线程问题。

(2)多线程问题

多线程问题主要是多个服务器处理多个任务,寻求处理所有任务的情况下,用掉最少时间的问题。因为任务并不局限于在某一个服务器上处理,还是要综合考虑

这些服务器,所以属于多线程问题。

三、算法应用实例

(1)单线程问题------活动安排问题

问题描述:

设有n个活动的集合E={1,2,...n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求

使用该资源的起始时间si和fi,且si<fi。如果选择了活动i,则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)和[sj,fj)不相交,则称活动i和活动j是相容的。

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集和。

解决思路:

利用贪心算法,将各活动按结束时间的非减序进行排列,由于输入的活动以完成的时间非减序排列,所以都每次都选择具有最早完成时间的活动
进行考虑,因为这样可以为未安排的活动留下尽可能多得时间,使剩余的可安排时间段极大化,以安排更多的相容活动。

程序设计:

例子描述:

贪心算法-----单线程:活动安排问题 多线程:多机调度问题

算法具体实现:

贪心算法-----单线程:活动安排问题 多线程:多机调度问题

贪心算法-----单线程:活动安排问题 多线程:多机调度问题

程序结果:

贪心算法-----单线程:活动安排问题 多线程:多机调度问题

跟图示的效果是一致的。

(2)多线程问题 之多机调度问题类型一:机器是完全相同的,不同的作业处理时间是独立的

问题描述:

设有n个独立的作业{1,2,...n},由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现规定,任何作业可以在任何一台
机器上加工处理,但未完工之前不允许中断处理。任何作业不能拆分成更小的子作业。

解决思路:

需要实现将n个独立的作业按照时间从大到小排序;在这里需要考虑的是:
如果n<=m,则需要的时间就是n个作业当中最长处理时间t。
如果n>m,先给每个机器分配作业,这一趟下来就分配了m个作业。然后对每个作业而言,选取处理时间最短的机器区域处理。
以上就是贪婪算法的思路。

例子描述:

贪心算法-----单线程:活动安排问题 多线程:多机调度问题

具体实现过程:

贪心算法-----单线程:活动安排问题 多线程:多机调度问题

程序设计:

贪心算法-----单线程:活动安排问题 多线程:多机调度问题

贪心算法-----单线程:活动安排问题 多线程:多机调度问题

程序结果:

贪心算法-----单线程:活动安排问题 多线程:多机调度问题

与图示的结果是一致的。

(3)多线程问题 之多机调度问题类型二:任务是完全相同的,每个服务器的执行时间是独立的

问题描述:

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzwfzz.html