聂程飞-算法设计与分析报告

《聂程飞-算法设计与分析报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Treap姓名：樊梦丹学号：406130915117专业班级：计算机科学与技术一、问题描述：冇一批井n个集装箱要装上2艘载重fi分别为q和q的轮船，其中集装箱f的重呈为叫，且t叫Sq+q。要求确定是否奋一个合理的装载方案可以将这Z7个集装箱装上这2/=1艘轮船。如果右，找出一种装载方案。二、回溯法求解算法分析：1.方法原理：回溯法的基本做法足搜索，或足一种纟II织得外井奋条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任意一点吋，先判断该节点足否包含问题的解。如果肯定

2、不也含，则跳过对该节点为根的子树的搜索，逐S向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。2.算法策略：如果一个给定的装载问题有解，则采用K面的策略可以得到最优装载方案：(1)酋先将第一艘轮船从可能装满；(2)然后将剩余的集装筘装上第二艘轮船。将第一艘轮船尽讨能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c,。由此可知，装载问题等价于以下特殊的0-1背包问题：maxcojxiXjg{0，1}，1

3、ov记当前的装载重/=!量，即=t叫；，当吋，以节点Z为根的子树中所有节点都不满足约朿条件，/=1因而该了树屮的解均为不可行解，故可将该了树剪去。算法中MaxLoading函数调用递!Tl函数Backtrack(l)实现回溯搜索。Backtrack(i)搜索了•集树屮第i层子树。类Loading屮数据成员记录子集树屮节点信息，以减少传给Backtrack蚋数的参数。cw记诚•当前Vf点所相应的装载重量，bestw记诚•当前最大装载S量。Backtrack函数屮，当i〉n时，算法搜索至叶节点，K相/.、V的装载重m为cw。劳cw〉bestw，则表乐当侃解优于当最优解，此吋应31新bes

4、tw。当i<=n吋，当前忙展节点Z是子集树中的内部节点。该节点有x[i]=l和x[i]=0两个儿子节点。其左儿子节点表示x[i]=l的情形，仅当CW+W山<=c吋进入左子树，对左子树递归搜索。其右儿子节点表示xl_ij=O的情形，凼于可行节点的右儿子节点总是可行的，因此进入右子树时不需检查可行性。在此函数中可以引入一个上界函数，用于剪去不含敁优解的了•树，从而改进算法在平均情况下的运行效率。1.主要算法描述：temp1ate::Backtrack(inti){//搜索第iS节点。如果到込叶节点，则判断当前的cw：如果比前而得到的

5、最优解bestw好，则替换原最优解。if(i>n){//到达叶节点if(cw>bestw){for(intj=1;j<=n;j++)bestx[j]=xfj];bestw=cw;}return;}//搜索子树r-二w[i];if(cw+w[i]<=c){//搜索左了•树x[i]=l；cw+=w[i];Backtrack(i+1);//递归访问其左子树cw-=w⑴;//访问结束，回到调川点}if(cw+r>bestw){//搜索右子树x[i]=0;Backtrack(i+1);}r+=w[il;}tcmplatc

6、，Typec,int*bestx){//返回最优载重量LoadingX;//初始化XX.x=newint[n+l];X.w=w;X.c=c;X.n=n;X.bestx=bestx;X.bestw=0;X.cw=0;//初始化rX.r=0;for(inti=l;i<=n;i++)X.r+=w[i];X.Backtrack(l);returnX.bestw;delete[]X.x;}2.复杂度分析：算法中Backtrack函数动态的生成解空间树。在每个节点处花费0(1)时间。子集树屮节点个数为0(2”)，故Backtrack函数所耑计算时间为0(2")。另外Backtrack

7、函数还耑嬰额外O(n)的递归栈空间。1.实验结果：C:Windowssystem32cmd.exe40188:•■5丑里10量1董:重12载黨8船k—装6轮讀1艘：¥-24一为集105第解w入2入优c:s.is^17眷取为：L&量重0<-个f载船轮0曰^<15艘：02_

8、为1一入入8入优第116^D取»

9、为.量.童■81靈1S1船意111二按第请三、队列式分支限界法求解算法分析：1.方法原理：分支限界法常以广度优先或以最小粍费(最大效益)优先的方式搜