实验四

实验四贪心算法实现最佳任务调度实验

[学号 : SA19225157]

一、实验内容

实现一个任务调度问题：在单处理器上具有期限和惩罚的单位时间任务调度

实现这个问题的贪心算法，并写出流程图或者伪代码。
将每个 Wi 替换为 max{W1,W2……Wn}-Wi 运行算法、比较并分析结果。

二、算法思路及代码

按通用的加权胚的贪心算法，把任务先按权值递减排列
结果集A一开始是空集，是独立子集,遍历所有任务,加入前进行独立性检测. 对t = 0,1,2,,,n,有Nt(A) <= t,则A是独立的。
将结果集A调成规范形式，即按deadline增序排列
加入迟任务，此时即为最终调度.

package com.ustc.g_tanxin;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Tanxin {
    public static void main(String[] args) {
        //输入所有任务
        Task a1 = new Task(1,4,70);
        Task a2 = new Task(2,2,60);
        Task a3 = new Task(3,4,50);
        Task a4 = new Task(4,3,40);
        Task a5 = new Task(5,1,30);
        Task a6 = new Task(6,4,20);
        Task a7 = new Task(7,6,10);
        //构造任务集合
        List taskList = new ArrayList<>();
        taskList.add(a1);
        taskList.add(a2);
        taskList.add(a3);
        taskList.add(a4);
        taskList.add(a5);
        taskList.add(a6);
        taskList.add(a7);
        //替换前
        System.out.println("替换前");
        Result result1 = getBestSchedule(taskList);
        //替换后
        System.out.println(result1);
        System.out.println("替换后");
        Result result2 = getBestSchedule(explaceWeight(taskList));
        System.out.println(result2);

    }
    public static List explaceWeight(List taskList){
        int max = Integer.MIN_VALUE;
        for (Task task : taskList) {
            max =  task.weight > max ? task.weight : max;
        }
        for (Task task : taskList) {
            task.weight = max - task.weight;
        }

        return taskList;
    }

    /**
     * 贪心算法求出最优调度
     * @param taskList 任务集
     * @return 最优调度集
     */
    private static Result getBestSchedule(List taskList) {
        //按权值降序排序
        Collections.sort(taskList, new Comparator() {
            @Override
            public int compare(Task o1, Task o2) {
                return o2.weight - o1.weight;
            }
        });
        //初始化结果集
        List resultList = new ArrayList<>();
        //辅助集合，存储加入后不独立的task
        List helper = new ArrayList<>();
        //遍历任务集加入结果集，独立性检测
        for (Task task : taskList) {
            resultList.add(task);
            boolean isIndependent = checkIndependence(resultList);
            if (!isIndependent){
                resultList.remove(task);
                helper.add(task);
            }
        }
        //规范化
        Collections.sort(resultList, new Comparator() {
            @Override
            public int compare(Task o1, Task o2) {
                return (int) (o1.deadline - o2.deadline);
            }
        });
        int weightSum = 0;
        for (int i = 0; i < helper.size(); i++) {
            resultList.add(helper.get(i));
            weightSum += helper.get(i).weight;
        }

        return new Result(resultList,weightSum);
    }

    /**
     * 对任务集resultList进行独立性检测
     * @param resultList
     * @return
     */
    private static boolean checkIndependence(List resultList) {
        int size = resultList.size();
        for (int i = 1; i <= size; i++) {
            long sum = 0;
            for (int j = 0; j < size; j++) {
                if (resultList.get(j).deadline <= i){
                    sum++;
                }
            }
            if (sum > i){
                return false;
            }
        }
        return true;
    }
    static class Result{
        List bestSchedule;//最优调度
        int weight;//惩罚总数

        public Result(List bestSchedule, int weight) {
            this.bestSchedule = bestSchedule;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "最优调度=" + bestSchedule +
                    ", 总的惩罚=" + weight ;
        }
    }
    static class Task{
        long deadline;
        int weight;
        long aIndex;

        public Task(long aIndex, long deadline, int weight) {
            this.deadline = deadline;
            this.weight = weight;
            this.aIndex = aIndex;
        }

        @Override
        public String toString() {
            return
                    "a" + aIndex +
                    " ";
        }
    }
}