《算法分析设计回溯法求解装载问题实验报告》由会员分享，可在线阅读，更多相关《算法分析设计回溯法求解装载问题实验报告（8页珍藏版）》请在装配图网上搜索。
1、回溯法求解装载问题一、方法一般原理回溯法也称为试探法，该方法首先暂时放弃关于问题规模人小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩人当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找卞一个候选解的过程称为回溯。扩人当前候选解的规模，以继续试探的过程称为向前试探。可用回溯法求解的问题P,通常要能表达为：对于已知的由n元组（X1,x2,，xa）组成的一个状态空间E=（xi,X2，xj|Xi
2、ESi,i二1,2,，n,给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。其中&是分量监的定义域，且|SJ有限，i=l,2,，no我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（X1,x2,，监）满足D中仅涉及到畑，&的所有约束意味着j（ji）元组（&,刘,，Xj）一定也满足D中仅涉及到x2,，的所有约束，i=l,2,，no换句话说，只要存在0
3、WjWn-l,使得（xi,X：,，）违反D中仅涉及到xi,x2,，为的约束之一，则以（xi,X2,，Xj）为前缀的任何n元组（X1,X2,，Xj,Xj+1,，xa）一定也违反D中仅涉及到xx,也，监的一个约束，因此，对于约束集D具有完备性的问题P,旦检测断定某个j元组（&,x:,，禺）违反D中仅涉及x：,，的一个约束，就可以肯定，以（X1,X2,，Xj）为前缀的任何n元组（X1,X2，Xj,Xj+11，xa）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的
4、带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：设S冲的元素可排成&,xj2）,，x严,|Si|壬,i=l,2,，no从根开始,让T的第I层的每一个结点都有血个儿子。这血个儿子到它们的双亲的边，按从左到右的次序，分别带权Xi+1,Xi+1,，Xi+i,i二0,1,2,，n-lo照这种构造方式,E中的一个n元组（&,x2,，xj对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为也，x2,，反之亦然。另外，对于任意的0WiWn-l,E中n元组（刘，xa）的一个前缀I元组（xi,也，Xi）对应于T中的一个非叶子结点，T
5、的根到这个非叶子结点的路径上依次的I条边的权分别为Xi，也，Xi,反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权刘，x2,，x满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入,即依次搜索满足约束条件的前缀1元组(知)、前缀2元组(&,禺)、，前缀I元组(&,X2,，Xi),，直到i=n为止。在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点：树T上的任意一个叶子结点
6、被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。二、描述问题有一匕共n个集装箱要装上2艘载重量分别为6和心的轮船，其中集装箱i的重量为他，且Wxn)Output(x);elsefor(inti二0;in时，搜索至叶节点，若装载量bestw,更新bestwo当i=n时，扩展节点Z是子集树内部节点。左儿子节点当cw+win)if(cwbestw)for(j_index=l;j_index=n;j_index+)bestxj_index=xj_index;bestw=cw;return1;)搜索子树r-二wi;if(
7、cw+wi=c)/搜索左子树，如果当前剩余空间可以放下当前物品也就是，cw+wibestvz)/搜索右子树xi二0;Backtrack(i+1);)r+=wil;intmaxloading(intinu,intc,intn,int*mx)loadingx;x.w=inu;x.x二mx;x.c=c;x.n=n;x.bestw二0;x.cw=0;x.Backtrack(1);returnx.bestw;五、总结由此，我们可以总结出回溯法的一般步骤：(1) 针对所给问题，定义问题的解空间；(2) 确定易于搜索的解空间结构；(3) 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。通过D
8、FS思想完成回溯，完整过程如下：(1) 设置初始化的方案(给变量赋初值，读入已知数据等)。(2) 变换方式去试探，若全部试完则转(7)。(3) 判断此法是否成功(通过约束函数)，不成功则转(2)。(4) 试探成功则前进一步再试探。正确方案还未找到则转(2)已找到一种方案则记录并打印。(7) 退回一步(回溯)，若未退到头则转(2)。(8) 已退到头则结束或打印无解。可以看出，回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以人人提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。六. 附录(源码)#include#in
9、clude#includetypedefintStatus;typedefintType;intn二0;集装箱数Type*x=(Type*)malloc(50)*sizeof(Type);/当前解Type*bestx=(Type*)malloc(50)*sizeof(Type);当前最优解Typec二0,/第一艘轮船的载重量cw二0,当前载重量bestw=0,当前最优载重量r二0,*w=(Type*)malloc(50)*sizeof(Type);集装箱重量数组intBacktrack(inti)搜索第i层节点intj_index;如果到达叶结点，则判断当前的cw,如果比前面得到的最优解bes
10、tw好，则替换原最优解。辻(in)if(cwbestw)for(j_index=l;j_index=n;j_index+)bestxj_index=xj_index;bestw=cw.:return1;)搜索自树r-二wi;if(cw+wi=c)/搜索左子树，如果当前剩余空间可以放下当前物品也就是，cw+wibestv7)/搜索右子树i二0;Backtrack(i+1);)r+=wil;Type*Initiate()intindex=l;printfC输入集装箱个数：“)；scanf&n);printf(z/输入轮船载重量：”)；scanf&c);曲订e(index=n)/数组从1号单元开始存
11、储printf(输入集装箱%(1的重量：，index);scanf&windex);index+;)bestw=0;cw=0;r=0;for(index=1;index=n;index+)r+=windex;/初始时r为全体物品的重量和printfc=%dcw=%dbestw=%dn,c,cw,bestw,r);for(index=l;index=n;index+)printf(w%d=%d、index,windex);)printfCAnO；returnw;intmain0inti;Initiate0;计算最优载重量Backtrack(1);for(i=l;i=n;i+)printf(z/%d气wi);printf(z/%dn?/,bestxti);)returnbestw;
算法分析设计回溯法求解装载问题实验报告
