回溯法 java.doc

应用数学 学院 信息安全 专业 （1） 班 学号 实验题目 回溯算法 实验评分表指导教师评分标准序号评分项目评分标准满分打分1完成度按要求独立完成实验准备、程序调试、实验报告撰写。202实验内容（1） 完成功能需求分析、存储结构设计；（2） 程序功能完善、可正常运行；（3） 测试数据正确，分析正确，结论正确。303实验报告内容齐全，符合要求，文理通顺，排版美观。404总结对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。10实验报告一、 实验目的与要求1. 理解回溯算法的基本思想；2. 掌握回溯算法求解问题的基本步骤；3. 了解回溯算法效率的分析方法。二、 实验内容回溯法解题步骤：1. 确定该问题的解向量及解空间树；当n=4，m=4时，问题的解向量为一个一维数组，取值为0-3问题的解空间大小为mn=256。解空间树为四叉树。2. 对解空间树进行深度优先搜索；见代码。3. 再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。约束条件：总价格不能超过c目标函数：即判断当前结点所在处，计算当前分支还没计算的结点的总总量，加上已计算总重量与目前最忧解进行比较。如果大于最优解，则剪枝。4. 达到叶结点时记录下当前最优解。见代码。5. 实验数据n,m, ,的值由自己假设。 int w = new int3,4,5,6,2,4,6,3,6,5,8,9,9,6,8,7;int c = new int5,4,3,2,6,3,3,2,9,8,5,4,5,6,4,5;实验源代码：public class Test3 int partNum,/零件数量shopNum,/厂商数量w,/从j个供应商购买第i个部件的重量c,/从j个供应商购买第i个部件的价格maxCost,/花费的最大价格cw,/当前的重量cc,/当前的价格bestw,/机器的最小重量bestc,/购买允许的最大价格bestx,/最优解x;/当前解public Test3(int w,int c,int cost)partNum=w.length;shopNum=w0.length;this.w=new intpartNumshopNum;this.c=new intpartNumshopNum;for(int i=0;ipartNum;i+)for(int j=0;jshopNum;j+)this.wij=wij;this.cij=cij;this.maxCost=cost;bestw=Integer.MAX_VALUE;/初始化为最大值，第一次判断会使使用，后面会改bestc=0;bestx=new intpartNum;x=new intpartNum;public void backtracking(int curNum)/curNum 当前正在计算第curNum零件if(curNum = partNum & cw = bestw)/到达叶子结点bestw = cw;bestc = cc;for(int i =0;i partNum;i+)bestxi = xi;return;for(int i=0;ishopNum;i+)cw += wcurNumi;cc += ccurNumi;xcurNum = i;/约束条件（总价格不能超过c）和目标函数（机器重量最小）if(cc = this.maxCost & (cw+restMinW(curNum+1)bestw)backtracking(curNum+1);cw -= wcurNumi;cc -= ccurNumi;public int restMinW(int Num)/第 Num,.partNum个部件的最小重量和int sum = 0;int temp;for(int i=Num;ipartNum;i+)temp = wi0;for(int j=1;j wij)temp = wij;sum += temp;return sum;public static void main(String args) / TODO Auto-generated method stubint w = new int3,4,5,6,2,4,6,3,6,5,8,9,9,6,8,7;int c = new int5,4,3,2,6,3,3,2,9,8,5,4,5,6,4,5;Test3 obj;for(int j=12;j=26;j+)obj = new Test3(w, c, j);obj.backtracking(0);System.out.println(最小重量： + obj.bestw);System.out.print(总价格： +obj.bestc+n最优方案： );for (int i = 0; i obj.partNum; +i) System.out.print(obj.bestxi + );System.out.println();实验结果： 三、问题与讨论考虑影响回溯法效率的因素有哪些？影响回溯法效率的主要因素1）产生xk的时间2）满足显约束的xk值的个数3）计算约束函数constrain的时间 （本例约束函数直接给出，不用计算）4）计算上界函数bound的时间（本例为restMinW 函数）5）满足约束函数和上界函数约束的所有xk的个数四、总结（对本次实验有什么心得体会？或建议 本次实验虽为回溯法，但却有动态规划的思想。回溯法也有子问题，可以用递归实现。回溯法与动态规划的不同在于回溯