算法实验四回溯法

《算法实验四回溯法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《算法设计与分析》课程实验报告专业：一-班级：学号：姓名：日期■■2013年12月11日、实验题目回溯法二、实验目的1.掌握回溯法的基本思想。2.掌握回溯法巾W题的解空间、解向量、显式约朿条件、隐式约朿条件以及子集树与排列树的递归算法结构等内容。3.掌握回溯法求解具体W题的方法。三、实验内容1.有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其屮集装箱i的重量为wi,且Ewi

2、n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的祺子。n后问题等价于在nXn格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。3.给定无叫连通阁G和m种不同的颜色。用这些颜色为阁G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G屮每条边的2个顶点着不同颜色。这个问题是阁的m可着色判定问题。!L>实验步骤1、装载问题【问题分析】例如，当n=3，cl=c2=50，Mw=[l0,40,40]时，可将集装箱1和集装箱2装上一艘

3、轮船，而将集装箱3装在第二艘轮船；如果w=[20,40,40]，则无法将这3个集装箱都装上轮船。容易证明，如果一个给定的装载问题有解，则采用如T的策略可以得到最优装载方案。1.首先将第••艘轮船尽可能装满。1.将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能的装满等价于选取全体集装箱的子集，使该子集屮集装箱的重兑之和最接近cl。因此，等价于一个特殊的0-1背包问题。因此是一棵子集树。max(wlxl+w2x2+...+wixi)(wlxl+w2x2+•…+wixi)<=cl;xi@{0,1},l<=i<

4、=n用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。可行性约束函数可剪去不满足约束条件((wlxl+w2x2+...+wixi)<=cl)的子树。在子集树的第j+1层的节点Z处，用cw记当前的装载重量，即cw=(wlxl+w2x2+...+wjxj〉，当cw〉cl时，以Vf点Z为根的子树中所有节点都不满足约束条件，因而该子树中解均为不可行解，故可将该子树剪去。下而的解装载问题的回溯屮，算法MaxLoading返回不超过C的最大子集和，但并未给出达到这个最大子集和的相应子集。稍后加以完善。算法M

5、axloading调用递归函数Backtrack(1)实现冋溯搜索。Backtrack(i)搜索子集树中第i层子树。类Loading的数据成语。记录子集树中结点信息，以减少传给Backtrack的参数。cw记录当前结点所相应的装载重量，bestw记录当前最大装载重量。在算法Backtrack中，当i>n时，算法搜索至叶节点，其相应的装载重量为cw。如果cw〉bestw，则表示当前解优丁•当前最优解，此时应更新bestw。当i<=n时，当前扩展结点Z是子集树巾的内部节点。该结点有x[i]=l和x[i]=0

6、两个儿子结点。其左儿子结点表示x[i]=l的情形，仅当cw+w[i]<=c吋进入左子树，对左子树进行递归搜索。其右儿子结点表示x[i]=o的情形。由于可行结点的右儿子结点总是可行的，故进入右子树时不需要检查可行性。算法Backtrack动态地生成问题的解空间树。在每个结点出算法花费0(1)时间。子集树种结点个数为0(2n),，故Backtrack所滞的计算时间0(2n)。另夕卜Backtrack还需要额外的0(n)的递归栈空间。【算法描述】importjava•utileScanner;publiccl

7、assBacktrack{staticintn;//集装箱数staticint[>;//集装箱贡量数组staticstaticstaticstaticstaticstaticintc;//第一艘轮船的载重显intcw;//当前载重最intbestw;//当前最优载重量intr;//剩余集装箱亟量int当前解int[]bestx;//当前最优解publicstaticintmaxLoading(int[]ww,intcc,int[]xx){n=ww.length-1;iv=ww;c=cc;bestw=0;

8、x=newint[n+1];bestx=xx;for(inti=0;i<=n;i++)r+=w[i];//计算最优装载重量backtrack(Q);returnbestM；publicstaticvoidbacktrack(inti){//搜索第i层结点if(i>n){//到达叶结点if(cw>bestu/){for(intj=0；j<=n;j++)hestx[j]=x[j];bestiv=ctv;}return;}卜=w[i];if(cu