文档介绍：回溯算法的应用

Email:dao0oad@
厦门大学计算机科学系04级四班
问题描述:
给定一块宽度为W的矩形板,矩形板的高度不受限制。现需要从板上分别切割出n个高度为hi,宽度为wi的矩形零件。切割的规则是零件的高度方向与矩形板的高度方向保持一致。问如何切割使得所使用的矩形板的高度h最小?
例如:
h1=3
h2=2
h3=1
w1=2
w2=4
w3=5
h=4
要求使用分治算法对与任给的一个输入实例,能输出切割所需要的最小实际高度h并能用图形演示切割的过程。
算法思路:
本实验明确要求要使用回溯的方法求解,当然最简单最易想到的方法是对所有的木块进行搜索,求解出一个高度最低的排列,这样如果不算剪枝函数,算法的解空间是一颗有所有木块构成的一颗排列树,算法时间复杂度为O(2^n),其中n为木块的个数,老师提供的数据最少的是17个,2的17次方还是很惊人的数字,就算用上剪枝函数,要进行17层的递归也是非常可怕,这就是很多同学没有算出结果最后自己构造数据的原因。
本程序试图换个思路,对木板空间进行回溯,由于最开始时木板才一个,虽然随着切割的不断深入,木板个数逐步提升,时间复杂度相对与刚才的想法还是有很大的提升,然而老师提供的数据最大的是156个木板,这对于完全递归来说显然是不大可能,因此本程序设置了一条控制递归深度的线,在程序中设为Line,当程序的递归深度超过Line值时,就换成贪心算法,只需找出第一个可以切割的木板即可。程序中Line值的设置是根据可以接受的最长程序运行时间,一般使程序运行不超过20秒。虽然这样做使得最后得到的不是最优解,但对于求不出解来说还是不错的进步。
程序X数组用来存放当前的搜索路径,bestX用来存放目前求得的最佳路径,每次搜索到叶子节点时就比较路径X是否比路径bestX 的高度低,如果是的话,就替换当前最佳路径为X。
程序中维护了两个链表,一个四headMuKuai,用来存放所有的木块,且他们按照高度非递减进行排序。另一个是headMuBan,用来存放切割后的木板。
函数float **CreatFloatArray_2(float **Head,int m,int n)是根据输入的二维数组头指针和二维数组的行列大小自动生成内存结构和C语言内置二维数组完全一样的二维数组。
程序中切割模板的方法是实验一是一致的,如下图所示:
木块
切割后的木板1
切割后的木板2
算法伪代码:
void backtracking(int level,int num)
{
MuBan *MuBan1,*MuBan2; //用于存放切割后的两块木板
MuKuai *l; //当前正要放置的木块
MuBan *pX = NULL,*pbestX = NULL;//px为当前找到的路径的头指针,pbestX为最佳路径的投指针
if(num > n){//叶子节点
if(h < besth){
//当前找到的路径比程序保存的最佳还要好,替换最佳路径
besth=h; //新的最佳木板高度
}
}
l = find(num); //需要处理的木块
if(level > Line){ //如果递归深度已经超过递归控制线,采用贪心算法快速得出