实验 4《回溯法实验》
一、实验目的
- 掌握回溯算法思想
- 掌握回溯递归原理
- 了解回溯法典型问题
二、实验内容
-
编写一个简单的程序，解决 8 皇后问题。
-
批处理作业调度问题
[问题描述]给定 n 个作业的集合 J= (J1, J2, … , Jn)。每一个作业 Ji 都有两项任务 需要分别在 2 台机器上完成。每一个作业必须先由机器 1 处理，然后再由机器 2 处理。作业j需要机器 i 的处理时间为 tji，i=1,2, … ,n; j=1,2。
对于一个确定的作业调度，设 Fji 是作业 i 在机器 j上完成处理的时间。则所有作业在机器 2 上完成处理的时间和成为该作业调度的完成时间和。批处理作业调度问题要求对于给定的 n 个作业，制定一个最佳的作业调度方案，使其完成时间和达到最小。
要求输入：
1）作业数 2）每个作业完成时间表：完成时间 机器 1 机器 2 作业 1 2 1 作业 2 3 1 作业 3 2 3
要求输出： 1）最佳完成时间 2）最佳调度方案
提示：算法复杂度为 O(n !),建议在测试的时候 n 值不要太大，可以考虑不要超过 12。 -
数字全排列问题
任意给出从 1 到 N 的 N 个连续的自然数，求出这 N 个自然数的各种全排列。如 N=3 时， 共有以下 6 种排列方式：123，132，213，231，312，321。
注意：数字不能重复，N 由键盘输入（N<=9）。
三、算法思想分析：
回溯算法：
带优化的穷举法，具有限界函数的深度优先搜索算法。 优化是指在搜索过程中用剪枝函数避免无效搜索。 常用剪枝函数有两种（不一定两种同时存在，但有可能两种同时存在）：
- 约束函数，剪去不满足约束条件的左子树；
- 限界函数，剪去得不到最优解的右子树
可以解决的问题：
- 组合问题
- 切割问题：给一个字符串及约束条件，问有几种切割方式
- 排列问题：与组合的区别在于排列强调顺序
- 子集问题
- 棋盘问题：如N皇后问题
回溯算法的理解：
- 递归是有终止的，回溯与递归相辅相成，可以抽象为一棵n叉树。树的宽度为处理的集合大小，常用for循环遍历；树的深度即为递归的深度。
- 通常处理逻辑：
void backtrack(){
if(终止条件){
收集结果;
return;
` }
for(集合元素){
处理结点;
递归函数;
回溯操作;//撤销处理结果
}
}
-
通过递归控制有多少层for循环，递归的每一层相当于一个for循环。for循环横向遍历，递归纵向遍历，回溯不断调整结果集。
-
八皇后问题：约束条件（没有限界函数）——同一列/斜线上是否已经放了一个皇后（行不用管，因为就是在找当前行能不能放皇后，一行一行地找，若在该行遍历完n之前能够找到位置放置皇后，则向下一行递归，若没有位置可放，则向上回溯）
-
批处理作业调度问题：剪枝函数——total < bestT(当前用时比已找到的bestT小才往下遍历)
-
排列问题：约束条件——当前数字是否已经被排列
四、实验过程分析
1) 遇到的问题及解决
n皇后问题
- 与类似组合问题的情况不同，不能像组合问题那样在函数最开始判断i>n时就output，因为n皇后问题中并不是走到最深层就是一个解了，还要判断在该层上能不能找到一个符合要求的位置来摆放第n个皇后。而在组合问题中只要深度符合要求了就已经是一个解了，没有其他要求。n皇后问题的输出需要在摆放好皇后后进行判断，看本次放的是不是最后一个皇后，只有当放的是最后一个皇后时才是可行解。
- 刚开始我将当前处理的是第几行作为类的静态变量处理，结果最终只输出了一种解决方案。后来将改为将处理第几行作为参数传入backtrack函数后就输出了所有结果。
这个参数不能作为类的静态成员变量，因为若将i设为静态变量，它在所有实例之间是共享的，在一次递归中递增i，然后在另一次递归中回溯i时，这个修改会影响到所有的递归调用，每次递归调用都在同一个i上进行操作，导致程序只能得到一个解！以后要注意，类似情况中，与递归深度相关的变量不能作为类的成员变量（能否作为类的成员变量处理需要谨慎考虑），否则在某次递归中对其进行修改就会影响所有递归的深度，会出问题的。 - 回溯的时机要找准，刚开始误将回溯放在了递归调用backtrack的那个else分支中，结果只输出了一个解。因为当i = n-1时，即当找到一个解后，就没有回溯了，相当于这个程序只是用来找出一个解的，而不是找出所有解。这个问题的根本原因跟将i作为静态成员的情况一样，都是用来找出一个可行解的，而不是所有可行解。
批处理作业调度问题
- 刚开始我一直在思考这道题是不是需要构造两棵解空间数，一个是机器1的，一个是机器2的，但是机器2的调度是有要求的，需要先被机器1处理完才能被2调度，那么我是不是需要再用一个数据结构来保存机器1的处理顺序呢？机器2的解空间树依赖于机器1的调度顺序，所以其约束函数是此时该作业是否在机器1上执行完成？这样一来感觉问题变得比较复杂，不太清楚到底该怎么下手了。
到网上搜了一下，发现他们都说易证当两台机器的调度顺序一致时用时最小，这怎么就易证了呢，我还觉得应该用抢占式调度完成时间才比较短呢，FCFS不一定最短吧，搜了半天也没搜出个所以然来，暂时就默认这样吧------好吧，画出图后好像确实易证调度顺序一致时用时最短？
数字全排列问题 - 递归终止条件写错了，误写成了i == n-1时结束，其实应该是i > n – 1（或者i == n）时，因为n-1处也是需要排数字的，如果i == n-1时结束则最后一位还没有排，故输出时最后一位全为0
2) 实验体会
回溯算法比较灵活，我觉得是比动态规划要难的，动规掌握原理后难点弄清楚那道题的动规五部曲，弄清楚后思路是很清晰的，但是回溯算法的剪枝函数非常灵活，要分析其约束条件或限界函数或者两个可能同时存在，这个问题就需要一定熟练度，要对题目较为敏感，反正对我来说还是很有难度的，特别是批处理作业调度那道题，可能学了操作系统后我反而将题目考虑复杂了，总觉得完成时间不只是简单的将时间相加，应该还要比较值。还有就是什么时候需要回溯，回溯的时机要能够准确找出。
五、算法源代码及用户屏幕
1．八皇后问题：
源代码：
public class NQueens {
private static int n = 8;//n个皇后
private static int count = 0;//统计解决方法的数量
private static boolean[]col = new boolean[n];//某列是否有皇后
private static boolean[]left = new boolean[2n];//左斜线是否有皇后
private static boolean[]right = new boolean[2n];//右斜线是否有皇后
private static int[][]chessBoard = new int[n][n];//棋盘，若未放皇后，则用0表示
public static void main(String[] args) {
backtrack(0);
System.out.println("共计" + count + "种摆放方法");
}
private static void print(){//打印棋盘
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
System.out.print(chessBoard[i][j] + " ");
}
System.out.println();//换行
}
}
private static void backtrack(int i){//第i行
for(int j = 0; j < n; j++){//第i行有没有可以放皇后的位置
if(!col[j] && !left[i + j] && !right[i - j + n]){
//放入皇后
chessBoard[i][j] = i + 1;//表示这是第几个放入的皇后
//修改其所在列、斜线的标志
col[j] = left[i + j] = right[i - j + n] = true;
if(i == n - 1){
count++;
print();
System.out.println();
}else {
//处理下一行
backtrack(i + 1);
}
//回溯
{
chessBoard[i][j] = 0;//拿走皇后
//修改相关标志
col[j] = left[i + j] = right[i - j + n] = false;
}
}
}
}
}
用户屏幕：
2．批处理作业调度问题：
源代码：
import java.util.Scanner;
public class JobScheduling_backtrack {
private static int n;//总作业数
private static int[][] needTime;//每个作业在两台机器上各自所需用时
private static int time1;//作业在机器1上完成处理的时间
private static int[]time2;//机器2完成处理时间
private static int total;//总计用时，即前i个作业在机器2上完成处理的时间和
private static int bestT = Integer.MAX_VALUE;//最佳完成时间
private static int[]path;//当前调度方案
private static int[]bestPath;//当前最佳调度方案
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("请输入总作业数：");
n = input.nextInt();
needTime = new int[n][2];
time2 = new int [n];
path = new int[n];
//初始化path
for(int i = 0; i < n; i++){
path[i] = i;
}
bestPath = new int[n];
System.out.println("请分别输入每个作业需要在两台机器上的运行时间，如2 1，表示需要在第一台机器上运行2s，需要在第二台机器上运行1s");
for(int i = 0; i < n; i++){
needTime[i][0] = input.nextInt();
needTime[i][1] = input.nextInt();
}
// for(int i = 0; i < n; i++){
// System.out.println(needTime[i][0] + " " + needTime[i][1]);
// }
backtrack(0);
for(int i = 0; i < n; i++){
System.out.print(bestPath[i] + " ");
}
System.out.println("
共计用时" + bestT);
}
private static void backtrack(int i){//第i次调度哪个作业
if(i > n-1){//一种调度方案
//不用再比较了，因为total < bestT是用来剪枝的，当遍历到叶子结点时，这个就是最优解
// if(total < bestT){//若比当前最优方案用时少，则更新方案
bestT = total;
System.arraycopy(path, 0 , bestPath, 0, path.length);
}else {
for(int j = i; j < n; j++){
time1 += needTime[path[j]][0];//机器一的完成时间
if(i > 0){//如果选的不是第一个调度，则要判断当前机器一和机器二谁后执行完，用后执行完的时间（即更长的那个时间）加上这个作业要在机器二上运行的时间
time2[i] = ((time2[i-1] > time1) ? time2[i-1] : time1) + needTime[path[j]][1];
}else {//如果选的是第一个调度谁，则time2就等于该作业需要的两个机器运行时间和
time2[i] = time1 + needTime[path[j]][1];
}
total += time2[i];
if(total < bestT){
swap(i, j);
backtrack(i + 1);
swap(i, j);
}
//回溯
time1 -= needTime[path[j]][0];
total -= time2[i];
}
}
}
private static void swap(int i, int j){
int temp = path[i];
path[i] = path[j];
path[j] = temp;
}
}
用户屏幕：
3．数字全排列问题：
源代码：
import java.util.Scanner;
public class Permutation {
private static int n;
private static int[]path;//保存当前排列
private static int count;//共计多少种排列方法
private static boolean[]isP;//是否已经被排列
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("请输入n: ");
n = input.nextInt();
path = new int[n];
isP = new boolean[n];
backtrack(0);
System.out.println("共计" + count + "种排列方式");
}
private static void backtrack(int i){
if(i == n){
print();
count++;
return;
}
for(int j = 0; j < n; j++){
if(!isP[j]){//约束条件:不能重复出现
isP[j] = true;
path[i] = j + 1;//第i+1个位置排自然数j+1
backtrack(i + 1);
isP[j] = false;//回溯
}
}
}
private static void print(){
for(int i = 0; i < n; i++){
System.out.print(path[i]);
}
System.out.println();
}
}
用户屏幕：
