02-算法设计与分析-贪心算法.ppt

2.6 日程安排 在一台计算机上安排任务的问题。 第一个问题：最小化任务的平均执行时间； 第二个问题：每个任务有一个最后期限，只有在最后期限前完成任务，才有一定的收益，目标是最大化收益。 2.6.1 最小化时间 一个服务者Server，如一台计算机，一个车床，一个设备、一个ATM等。有n顾客（customer）要服务（任务）。服务时间已知，设顾客i(1,2,3,…,n),服务时间分别是t1,t2,…,tn. 因为顾客n是固定的，平均时间最小化就是顾客花费的总时间最小化。 Chapter 2 GREEDY ALGORITHMS 换言之，希望最小化： 例子： 顾客 1，2，3 服务时间：t1=,=5,t2=10,t3=3 下面是可能的6种服务顺序 顺序 T 1 2 3 5+（5+10）+（5+10+3）=38 1 3 2 5+（5+3）+（5+3+10）=31 2 1 3 10+（10+5）+（10+5+3）=43 2 3 1 10+（10+3）+（10+3+5）=41 3 1 2 3+（3+5）+（3+5+10）=29 3 2 1 3+（3+10）+（3+10+5）=34 Chapter 2 GREEDY ALGORITHMS 定理 2.6.1 这个贪婪算法所的解是最优解。 证明：设 P=p1p2…pn是1—n的任意排列。设si=tpi, 如果顾客按照P的顺序进行服务，则第i个顾客需要服务的时间是si,所有顾客需要的总时间是： Chapter 2 GREEDY ALGORITHMS 设 P不是按服务时间的不减序，那么，至少存在一对顾客a和b，ab,但sasb,将a和b换位，得到P’，根据日程表，P‘的所有顾客花费的时间是： Chapter 2 GREEDY ALGORITHMS 所以换位后的时间和小于换位前。 算法分析： 对 t进行排序需要O(nlogn),其他的工作需要O(n) 2.6.2 有期限的日程安排，需要执行n个任务，每个任务费时一个单位时间，如果任务i在di之前完成，会带来收益gi0. 收益最大化。 例： 安排和收益 i 1 2 3 4 安排 收益 安排 收益 g 50 10 15 30 1 50 2 1 60 d 2 1 2 1 2 10 2 3 25 3 15 3 1 65 4 30 4 1 80 1 3 65 4 3 45 Chapter 2 GREEDY ALGORITHMS 算法思想： 设S为可行解，G是收益集，T为任务集,时间为n单位 （1）置S为空，G排为降序； （2）从G中选收益最大的任务t； （3）若t加入S后，S是可行的，则将t加入S，从G中除去gt； （4）重复（2）（3）n次，或直到无可选的任务使S可行。 什么是S是可行的 Chapter 2 GREEDY ALGORITHMS 什么是S是可行的？ 通过例子来说明 i 1 2 3 4 5 d 4 3 1 2 3 设S={1,3,4}, 它有6种排列，只要其中的一种是可以执行的，就是可行的。 1，3，4 是不可执行的 1，4，3 是不可执行的 3，1，4 是不可执行的 3，4，1 是可执行的 4，1，3 是不可执行的 4，3，1 是不可执行的 所以S是可行的。 Chapter 2 GREEDY ALGORITHMS 引理 6.6.2 设T是有k项任务的集合。不失一般性，设任务编号为1,2,…,k，且d1≤d2≤…≤dn, 那么，T是可行的，iff 序列1,2,…,k是可行的。 证明：如果任务序列1,2,…,k是可执行的，则必然有d1d2…dn,T是可行的。 如果T是可行的，则必然存在一个任务序列是可执行的（有定义知）。该序列就是1,2,…,k。 Chapter 2 GREEDY ALGORITHMS 反证：假设任务序列1,2,…,k是不可执行的，则至少存在一个r，它的完成时间超过了它的期限。设r是任意的这样的任务，所以dr≤r-1。