回溯法实验报告.doc

实验04 回溯法 班级：0920561 姓名：宋建俭 学号：20一 、实验目的1. 掌握回溯法的基本思想。2. 掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子集树与排列树的递归算法结构等内容。3. 掌握回溯法求解具体问题的方法。二 、实验要求1. 认真阅读算法设计教材,了解回溯法思想及方法;2. 设计用回溯算法求解装载问题、n后问题、图的m着色问题的java程序三 、实验内容1. 有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为wi，且wiC1+C2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。2. 在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。3. 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。四、算法原理1、装载问题用回溯法解装载问题时，用子集树表示其解空间是最合适的。可行性约束可剪去不满足约束条件(w1x1+w2x2+wnxn)c1时，以结点Z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。解装载问题的回溯法中，方法maxLoading返回不超过c的最大子集和，但未给出达到这个最大子集和的相应子集。算法maxLoading调用递归方法backtrack(1)实现回溯搜索。Backtrack(i)搜索子集树中第i层子树。类Loading的数据成员记录子集树结点信息，以减少传给backtrack的参数。cw记录当前结点相应的装载重量，bestw记录当前最大装载重量。在算法backtrack中，当in时，算法搜索至叶结点，其相应的装载重量cw。如果cwbestw,则表示当前解优于当前最优解,此时应更新bestw。当i=n时，当前扩展结点Z是子集树的内部结点。该结点有xi=1和xi=0两个儿子结点。其左儿子结点表示xi=1的情形，仅当cw+win时，算法搜索至叶节点，得到一个新的n皇后互不攻击方案，当前已找到的可行方案数sum曾1.当i=n时，当前扩展节点Z是解空间中的内部结点。该结点有xi=1,2,，n，共n个儿子结点。对当前扩展结点Z的每一个儿子结点，由place检查其可行性，并以深度优先的方式递归地对可行子树搜索，或剪去不可行子树。3、图的m着色问题给定图G=(V,E)和m种颜色，用图的邻接矩阵a表示无向连接图G=(V,E)。若(i,j)属于图G=(V,E)的边集E，则aij=0。整数1,2，m用来表示m种不同颜色。顶点i所着颜色用xi表示。数组x1:n是问题的解向量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第i(1=in时，算法搜索至叶结点，得到新的m着色方案，当前找到的m可着色方案数sum增1。当i=n时，当前扩展结点Z是解空间中的内部结点。该结点有xi=1,2,，m共m个儿子结点。对当前扩展结点Z的每一个儿子结点，由方案ok检查其可行性，并以深度优先的方式递归地对可行子树搜索，或剪去不可行子树。五、实验程序功能模块1、装载问题import java.io.IOException;public class MainLoading public static void main(String args) throws IOException Loading loading = new Loading();int n = 4;System.out.println(集装箱个数: + n);int x = new intn + 1;String b = new Stringn;String a = 30 50 20 70;System.out.println(集装箱重量: + a);int w = new intn + 1;w1 = 30;w2 = 50;w3 = 20;w4 = 70;int c1 = 130;int c2 = 70;System.out.println(轮船载重量: + c1 + , + c2);int result = loading.maxloading(w, c1, x);int max, temp;for (int i = 1; i 3; i+) for (int j = 2; j wj) temp = wi;wi = wj;wj = temp;if (w3 c1) & (w3 c2) System.out.println(都不可装); else System.out.println(轮船1装载的集装箱：);for (int u = 1; u (result + c2)System.out.println(轮船1可装： + result + + 轮船2装不完.);else System.out.println(轮船2装载的集装箱：);for (int u = 1; u n + 1; u+)if (loading.bestxu = 0)System.out.println(u + );System.out.println(最优装载-轮船1: + result + + 轮船2:+ (loading.r - result);public class Loading static int n;static int w;static int c1, c2; / 第一、二艘轮船的载重量static int cw;static int bestw;static int r;static int x;static int bestx;public static int maxloading(int ww, int cc, int xx) n = ww.length - 1;w = ww;c1 = cc;bestw = 0;cw = 0;x = new intn + 1;bestx = xx;r = 0;for (int i = 1; i n) if (cw bestw) for (int j = 1; j = n; j+)bestxj = xj;bestw = cw;return;r -= wi;if (cw + wi bestw) xi = 0;backtrack(i + 1);r += wi;2、n后问题import java.io.IOException;public class MainNQueen public static void main(String args) nQueen nqueen = new nQueen();int nn; / 输入n值int sum; / 可行方案个数try nn = 4; / 将输入值转换为int保存if (nn = 0) throw new IOException(不能输入负数);System.out.println(方格数是： + nn);sum = nqueen.nQueen(nn); / 调用nqueen方法System.out.println(可行方案个数为： + sum); / 输出sum catch (IOException e) System.out.println(e.getMessage(); catch (NumberFormatException e) System.out.println(请输入数字。);public class nQueen static int n; / 皇后个数static int x; / 当前解static int sum; / 当前已找到的可行方案个数static int nQueen(int nn) n = nn; / 把输入给全局变量nsum = 0; / 初始化totlex = new intn + 1;for (int i = 0; i 0) xk+=1; / 第k列皇后向下移一行while (xk = n) & !(place(k) / 如果当前第k列皇后未出界或者和其他皇后冲突xk += 1; / 第k列皇后向下移一行继续寻找if(xk=n) / 找到一个值并且未出界if (k=n) / 已是最后一列说明已找到一个方案sum+; else / 不是最后一列故寻找下一列k+;xk = 0;else/ 找到的值已经出界，回退到上一列k-;/ 判断皇后是否冲突private static boolean place(int k) for (int j=1; jn)System.out.println(解决方案：); sum+;for(int i=1;i=n;i+)System.out.println(顶点+i+用颜色+xi+ );System.out.println();elsefor(int i=1;i=m;i+)xt=i;if(ok(t)backtrack(t+1);xt=0;private static boolean ok(int k)for(int j=1;j=n;j+)if(akj & (xj=xk)return false;return true;七、测试数据1、装载问题int n = 4;System.out.println(集装箱个数: + n);int x = new intn + 1;String b = new Stringn;String a = 30 50 20 70;System.out.println(集装箱重量: + a);int w = new intn + 1;w1 = 30;w2 = 50;w3 = 20;w4 = 70;int c1 = 130;int c2 = 70;System.out.println(轮船载重量: + c1 + , + c2);2、n后问题nn = 4;3、图的m着色问题int n = 4;System.out.println(图的顶点数: + n);int m = 3;System.out.println(颜色数: + m);boolean g = new booleann + 1n + 1;g12 = true;g21 = true;g13 = true;g31 = true;g23 = true;g32 = true;g24 = true;g42 = true;g34 = true;g43 = true;测试结果装载问题集装箱个数: 4集装箱重量: 30 50 20 70轮船载重量: 130,70轮船1装载的集装箱：1 3 4 轮船2装载的集装箱：2 最优装载-轮船1:120 轮船2:50n后问题方格数是：4 可行方案个数为：2图的m