【排序引论】第一章 绪论

• 1 排序问题的引例
• 2 排序问题的定义
• 3 处理机分类
• 4 部分符号说明
• 5 排序问题分类
• 6 排序问题的求解
• 7 课后习题

习题1

习题2

这一题使用java编写的程序，进行遍历（全排列）求解，但是由于规模较大，需要遍历很久，所以我将题目简化成了2个处理机，p=（9，8，7，6，5，4，3），求解结果如下（最优解由任务索引构成，从0开始）：

Java程序如下：

import lombok.Data;
import lombok.ToString;
import org.apache.commons.lang3.SerializationUtils;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;


public class Question02 {
    // 主函数
    public static void main(String[] args) {
        // 开始时间记录
        long start = System.currentTimeMillis();
        // 处理机个数
//        int m = 5;
        int m = 2;
        // 各工序加工时间
//        int[] p = new int[]{9,9,8,8,7,7,6,6,5,5,5};
        int[] p = new int[]{9,8,7,6,5,4,3};
        // 递归求解（全排列）
        dfs(m,p,new boolean[p.length],new Solution(m),0);
        // 输出求解结果
        System.out.println("最优解个数为："+solutionHashSet.size());
        if(!solutionHashSet.isEmpty()){
            System.out.println("最优解为："+bestValue);
            System.out.println("其中1个最优解为：");
            for (Solution solution : solutionHashSet) {
                System.out.println("工序索引：");
                System.out.print(solution.toString(p,1));
                System.out.println("工序P值：");
                System.out.print(solution.toString(p,2));
                break;
            }
            System.out.println("求解用时："+(System.currentTimeMillis()-start)/1000d+" s");
        }
    }
    // 最优解
    static int bestValue = Integer.MAX_VALUE;
    // 解的集合
    static HashSet solutionHashSet = new HashSet<>();
    // 搜索过的解集合
    static HashSet allSolutionHashSet = new HashSet<>();
    // 递归搜索函数
    private static void dfs(int m,int[] p,boolean[] used,Solution solution,int curCount){
        int evaluate = evaluate(solution, p);
        if(!allSolutionHashSet.add(solution.toString())){
            return;
        }
        if (curCount == p.length){
            if(evaluate < bestValue){
                bestValue = evaluate;
                solutionHashSet.clear();
                solutionHashSet.add(Solution.copySolution(solution));
            }else if(evaluate == bestValue){
                solutionHashSet.add(Solution.copySolution(solution));
            }
            return;
        }
        for (int i = 0; i < p.length; i++) {
            // 如果当前i任务没有被安排
            if(!used[i]){
                // 遍历每个处理机
                for (int j = 0; j < m; j++) {
                    // 回溯
                    used[i] = true;
                    solution.getList().get(j).add(i);
                    dfs(m,p,used,solution,curCount+1);
                    used[i] = false;
                    solution.getList().get(j).remove(new Integer(i));
                }
            }
        }
    }
    // 评价函数
    private static int evaluate(Solution solution,int[] p){
        int cMax = 0;
        for (List list : solution.getList()) {
            int c = 0;
            for (Integer index : list) {
                c += p[index];
            }
            cMax = Math.max(cMax,c);
        }
        return cMax;
    }
    // 求解结果类
    @Data
    @ToString
    static class Solution implements Serializable{
        List> list = new ArrayList<>();
        public Solution(int m) {
            for (int i = 0; i < m; i++) {
                list.add(new ArrayList<>());
            }
        }
        // 复制结果
        private static Solution copySolution(Solution solution){
            return SerializationUtils.clone(solution);
        }

        public String toString(int[] p,int flag) {
            StringBuilder sb = new StringBuilder();
            if(flag == 1){
                for (List integerList : list) {
                    sb.append(integerList.toString()).append("n");
                }
                return sb.toString();
            }else if(flag == 2){
                for (List integerList : list) {
                    for (Integer integer : integerList) {
                        sb.append(p[integer]).append(",");
                    }
                    sb.append("n");
                }
                return sb.toString();
            }
            return null;
        }
    }
}