《算法设计与分析》课程实验报告
专 业： 班 级： 学 号： 姓 名：
日期： 年 月 日
一、 实验题目 回溯法 二、 实验目的 1、掌握回溯法的基本思想。 2、掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子集树与排列树的递归算法结构等内容。 3、掌握回溯法求解具体问题的方法。 三、 实验内容 1、有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为wi，且∑wi≤C1+C2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 2、在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 3、给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。 四、 实验步骤 1、题目一 (1) 问题分析 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 (2) 算法描述 public class shiaynn { static int n;//货箱数目 static int[] w;//货箱重量数组 static int c;//第一艘船的重量 static int cw;//当前装载的重量 static int bestw;//目前最优装载的重量 static int r;//剩余货箱的重量 static int[] x;//当前解，记录从根至当前结点的路径 static int[] bestx;//记录当前最优解
public static int MaxLoading(int[] ww,int cc) { //初始化数据成员，数组下标从1开始 n = ww.length - 1; w = ww; c = cc; cw = 0; bestw = 0; x = new int[n+1]; bestx = new int[n+1]; //初始化r，即剩余最大重量 for(int i =1;i<=n;i++) { r += w[i]; } //计算最优载重量 backtrack(1); return bestw; } public static void backtrack(int t) { if(t>n) {//到达叶结点 if(cw>bestw) { for(int i=1;i<=n;i++) { bestx[i] = x[i]; } bestw = cw; } return; } r -= w[t]; if(cw + w[t] <= c) {//搜索左子树 x[t] = 1; cw += w[t]; backtrack(t+1); cw -= w[t];//回溯 } if(cw + r>bestw) { x[t] = 0;//搜索右子树 backtrack(t+1); } r += w[t];//恢复现场 } public static void main(String[] args) { // TODO Auto-generated method stub int[] ww = {0,20,30,60,40,40}; int c1 = 100; int c2 = 100; int n = ww.length - 1; MaxLoading(ww,c1); int weight2 = 0; for(int i=1;i<=n;i++) { weight2 += ww[i]*(1-bestx[i]);//bestx[i]的值只能为0或1 } if(weight2>c2) { System.out.println(\无解\ } else { System.out.println(bestw); System.out.println(weight2); //第一艘船的装载情况 for(int i = 1;i<=n;i++) { if(bestx[i] == 1) { System.out.println(\第\件货物装入第一艘船\ } } //第二艘船的装载情况 for(int i = 1;i<=n;i++) { if(bestx[i] == 0) { 2
} } } } } System.out.println(\第\件货物装入第二艘船\ (3) 运行结果 2、题目二 (1) 问题分析 在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 函数Place：来测试若将皇后k放在xk列，是否与前面已放置的k-1个皇后都不在同一列，且不在同一斜线上。 } if(i >= n) { ++resultCount; } else { for(int j = 0; j < n; j++) { arr[i] = j; if(place(arr, i)) { tria(arr, i+1, n); } } } } public static void main(String[] args) { int[] queen = new int[8]; tria(queen, 0, 6); System.out.println(\结果为：\resultCount); } (3) 运行结果 (2) 算法描述 public class shiyan{
static int resultCount = 0; private static boolean place(int[] arr, int s) { for(int i = 0; i < s; i++) { if((arr[i] == arr[s]) || (Math.abs(i-s) == Math.abs(arr[i]-arr[s]))) { return false; } } return true; } public static void tria(int[] arr, int i, int n) { 3、题目三 (1) 问题分析 若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。 给定图G=(V,E)和m种颜色，如果该图不是m可着色，给出否定回答；若m可着色，找出所有不同着色方法。 (2) 算法描述 public class shiyan{ public int[] x; public int n; public int cn; 3
public int bestn; public int[] bestx; public int[][] a; public int count; public void backtrack(int i){ if(i>n){ for(int j=1;j<=n;j++){ bestx[j]=x[j]; System.out.print(x[j]+\ } System.out.println(); bestn=cn; count++; return; } else{ boolean ok=true; for(int j=1;j
4
回溯法
