算法4.贪心算法的调度问题。

r囧r小猫 2022-07-14 13:42 309阅读 0赞

1.  ![这里写图片描述][SouthEast]  
    A = \{1, 2, 3, 4, 5\}  
    T = \{5, 8, 4, 10, 3\}  
    D = \{10, 12 , 15, 11, 20\}  
    那么对于调度f1  
    f1: \{1, 2, 3, 4, 5\} → N  
    f1(1) = 0, f1(2) = 5, f1(3) = 13, f1(4) = 17, f1(5) = 27  
    客户1, 2, 3, 4, 5的延迟分别是0, 1, 2, 16, 10；最大延迟是max\{0, 1, 2, 16 ,10\} = 16。  
    但是，不同调度的最大延迟是不一样的，再如对同一个实例的另一个调度f2  
    f2: \{1, 2, 3, 4, 5\} → N  
    f2(1) = 0, f2(2) = 15, f2(3) = 23, f2(4) = 5, f2(5) = 27  
    客户1～5的延迟分别是0, 11, 12, 4 ,10；最大延迟是max\{0, 11, 12, 4 ,10\} = 12。  
    上述调度f1和f2的安排分别如下图所示：![这里写图片描述][SouthEast 1]  
    显然，调度f2比f1具有更小的延迟。  
    我们的问题是：给定 A = \{1, 2, …, n\}，T = \{t1, t2, …, tn\}和D = \{d1, d2, …, dn\}，用贪心算法求具有最小延迟的调度f。  
    (1) 算法设计思路  
    对客户希望完成的时间进行从小到大排序，相应的预计对客户服务的时间对应排序  
    初始化f和延迟数组  
    (2) 算法实现的伪代码及其计算时间复杂度分析  
    求解调度问题的算法Schedule（int\[\] d,int\[\] t）  
    输入：预计对客户服务时间t\[\]，客服希望服务时间d\[\]  
    输出：最大的延迟时间  
    s1: int n=d.length  
    s2: for (int i=0 to n-1)  
    s3: for (int j=i+1 to n-1)  
    s4: if (d\[i\]>d\[j\]) 交换d\[i\]和d\[j\]，t\[i\]和t\[j\]  
    s5: end for  
    s6: end for  
    s7: int\[\] f=new int\[n+1\];int\[\] delay=new int\[n\];f\[0\]=0  
    s8: for (inti =1 to n)  
    s9: f\[i\]=f\[i-1\]+t\[i-1\]  
    s10: end for  
    s11: for (inti =0 to n-1)  
    s12: if (f\[i+1\]>d\[i\]) delay\[i\]=f\[i+1\]-d\[i\];  
    s13: else delay\[i\]=0;  
    s14: end for  
    s15: Array.sort(d);  
    s16: return d\[n-1\]  
    算法Schedule的计算时间复杂度分析：  
    O（NlogN）  
    (3) 实验代码

import java.util.Arrays;
    
        public class 分配调度 {
             static int schedule(int[] d,int[] t){
                int n=d.length;//获取数组的长度
                //将数组d从小到大排序，相应的t对应排序
                for (int i=0;i<n;i++)
                    for (int j=i+1;j<n;j++){
                        if (d[i]>d[j]){
                            swap(d[i],d[j]);//交换两个数
                            swap(t[i],t[j]);
                        }
                    }
    
                int[] f=new int[n+1];//创建一个数组用了存储服务的依次总时间
                int[] delay=new int[n];//存储延迟数
                f[0]=0;
                for (int i=1;i<=n;i++)//初始化f
                    f[i]=f[i-1]+t[i-1];
    
                for (int i=0;i<n;i++){
       //判断是否延迟
                    if (f[i+1]>d[i])//延迟
                        delay[i]=f[i+1]-d[i];
                    else //不延迟
                        delay[i]=0;
                }
            Arrays.sort(delay);//对延迟数组进行从小到大排序
            return delay[n-1];//返回最大的延迟数
            }
             //交换两个数的方法
            static void swap(int i, int j) {
                // TODO Auto-generated method stub
                int temp=i;
                i=j;
                j=temp;
            }
            public static void main(String[] args) {
                int[] d={
       10,12,15,11,20};
                int[] t={
       5,8,4,10,3};
                int max=schedule(d,t);
                System.out.println(max);
            }
        }

(4) 体会  
贪心算法主要是做出对当前最好的选择，所以对客户的希望服务时间从小到大排序。

[SouthEast]: /images/20220714/48c95f847ccc4633a160d3b9a6a01bc8.png
[SouthEast 1]: /images/20220714/071d6b09d99647d98492b7b291a7ec93.png