@TOC
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;
/**
* @Author:WSKH
* @ClassName:Question01
* @ClassType:
* @Description:第一章练习题1.5
* @Date:2022/5/19/17:09
* @Email:1187560563@qq.com
* @Blog:https://blog.csdn.net/weixin_51545953?type=blog
*/
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<Solution> solutionHashSet = new HashSet<>();
// 搜索过的解集合
static HashSet<String> 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<Integer> 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<Integer>> 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<Integer> integerList : list) {
sb.append(integerList.toString()).append("\n");
}
return sb.toString();
}else if(flag == 2){
for (List<Integer> integerList : list) {
for (Integer integer : integerList) {
sb.append(p[integer]).append(",");
}
sb.append("\n");
}
return sb.toString();
}
return null;
}
}
}