零件切割问题.cpp

零件切割问题的另一个版本 可以参考 内附代码说明

#include <math.h>
#include <stdio.h>
#include <malloc.h>
#include <windows.h>
#include <GL/glaux.h>

typedef struct MuKuai{   //木块结构体定义
	float h;             //木块高度 
	float w;             //木块宽度
	struct MuKuai *next; //木块链表
}MuKuai;
typedef struct MuBan{ //木板结构体定义
	float x;          //木板的左下脚横坐标
	float y;          //木板的左下脚纵坐标
	float h;          //木板高度
	float w;          //木板宽度
	struct MuBan *next;//木板链表
}MuBan;

MuKuai *headMuKuai = NULL; //木块链表头指针
MuBan *headMuBan = NULL;   //木板链表头指针
MuBan *A = NULL;           //用于存放最终结果
MuBan *X;                  //用于保存当前找到的路径
MuBan *bestX;              //用于保存当前找到的最佳路径

int   n;             //木块总个数
int   Line;          //用于控制递归深度
float W;             //木板宽度
float h = 0;         //当前找到的路径木板总高度
float besth = 35767; //最佳路径木板高度
int x = 0;           //用于调整屏幕的相对坐标
int k = 0;           //用于动态显示木块变化
float **C = NULL;    //定义颜色数组头指针

float **CreatFloatArray_2(float **Head,int m,int n)
{//根据输入的二维数组行和列动态创建二位数组，返回数组指针
	int i,j;
	float *p=NULL;
	if( !(m > 0 && n > 0) )
	{ //判断维度是否正确
		printf("错误的数组维度\n");
		return NULL;
	}
	p = (float *)malloc(sizeof(float) * m * n);//申请总体空间
	Head = (float **)malloc(sizeof(float *)*m);//申请二级指针空间
	for(i = 0;i < m;i++) 
		Head[i]=p + n * i;
	for(i = 0;i < m;i++) 
		for(j = 0;j < n;j++)
			Head[i][j] = 0;
	return Head;
} 

MuKuai *find(int k)
{//在木块链表中查找第k个元素
	MuKuai *p = headMuKuai;
	if(k > n)
	{
		printf("查找木块链元素失败!\n");
		return NULL;
	}
	for(int i = 1; i < k; i++)
		p = p->next;
	return p;
}

void sortInsert(MuKuai *Q) 
{//在headMuKuai中按照非递减排序插入木块节点，Q是一个已有的节点
	MuKuai *p = headMuKuai,*q = headMuKuai;
	if(p == NULL)
	{ //插在链表的第一个元素
		headMuKuai = Q;
		return ;
	}
	while(p->h > Q->h && p->next != NULL)
	{q = p;p = p->next;}//寻找合适的插入位置
	if(p == headMuKuai)
	{ //替换第一个元素
		Q->next = p;headMuKuai = Q;
		return ;
	}
	if(p->next == NULL && p->h > Q->h)//插在链表末尾
		p->next = Q; 
	else                             
	{Q->next = p;q->next = Q;}        //插在链表中间
}

void freeMuBan(MuBan *X)
{//释放木板链表空间，每次在替换最佳路径是调用
	MuBan *p = X,*Q = NULL;
	while(p != NULL)
	{Q = p->next;free(p);p = Q;}
}

int even(float x,float y)
{//由于浮点数的精度问题，用此种方法检测两个浮点数是否相等
	if(fabs(x-y)<0.00001) return 1;
	else return 0;
}

void delMuBan(float x,float y,float w,float h)
{//删除木板数组中的元素，实现元素回溯
	MuBan *p = X,*q;
	if(even(X->x,x) && even(X->y,y) && even(X->h,h) && even(X->w,w))
	{                  //判断第一个元素是否相同
		X = X->next;free(p);
		return ;
	}	
	while(p != NULL && (!even(p->x,x) || !even(p->y,y) || !even(p->w,w) || !even(p->h,h)))
	{q = p;p = p->next;}//查找元素	
	if(p == NULL)
	{//如果没有找到相应的元素
		printf("查找木块失败!\n");
		exit(1);
	}
	q->next = p->next;
	free(p);
}

void insertMuBan(float x,float y,float w,float h)
{//把找到的木板插入当前路径，用于生成结果
	MuBan *p;
	if(X==NULL)
	{            //木板数组中没有元素
		X = (MuBan *)malloc(sizeof(MuBan) * 1);
		X->h = h; X->w=w; X->x = x;
		X->y = y; X->next = NULL;
		return ;
	} 
	p = (MuBan *)malloc(sizeof(MuBan) * 1);
	p->h = h; p->w = w;p->x = x; p->y = y;p->next=X;X=p;
}

//////////////////以下函数为opengl图形绘制函数/////////////////
void myinit(void)
{ 
	glClearColor(0.0,0.0,0.0,0.0); 
	glClear(GL_COLOR_BUFFER_BIT);
	glShadeModel(GL_FLAT);
}

void CALLBACK down(void) 
{ 
	if(k < n-1) k++;
	else  return ;
} 

void CALLBACK myReshape(GLsizei w,GLsizei h)
{
	glViewport(0,0,w,h);
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	if(w<=h)
		glOrtho(-x,x,-x*(GLfloat)h/(GLfloat)w,x*(GLfloat)h/(GLfloat)w,-50.0,50.0);
	else
		glOrtho(-x*(GLfloat)h/(GLfloat)w,x*(GLfloat)h/(GLfloat)w,-x,x,-50.0,50.0);
	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();
}

void DrawMyObjects(void)
{
	int i = 0;
	MuBan *p = bestX;
	glClear (GL_COLOR_BUFFER_BIT);
	glLoadIdentity();
	glColor3f(1.0,0.0,0.0);
	glTranslatef(-(x * 0.5),-(x-0.1*x),0.0);//移动屏幕坐标到木板左下方
	glBegin(GL_LINE_STRIP); //绘制木板
	glVertex2f(0.0,0.0);
	glVertex2f(0.0,2*x-0.2*x);
	glVertex2f(0.0,0.0);
	glVertex2f(x,0.0);
	glVertex2f(x,0.0);
	glVertex2f(x,2*x-0.2*x);
	glEnd(); 
	while(i <= k)
	{
		glColor3fv(C[i]);
		glBegin(GL_QUADS ); 
		glVertex2f(A[i].x,A[i].y + A[i].h);
		glVertex2f(A[i].x,A[i].y);
		glVertex2f(A[i].x + A[i].w,A[i].y);
		glVertex2f(A[i].x + A[i].w,A[i].y + A[i].h);
		glEnd(); 
		i++;
	}
} 

void CALLBACK display(void)
{
	DrawMyObjects();glFlush();
}

float backtracking(int level,int num)
{//回溯过程实现
	MuBan *k1,*k2,*k3;              //临时指针
	MuBan *MuBan1,*MuBan2;          //用于存放切割后的两块木板
	MuKuai *l;                      //当前正要放置的木块
	MuBan *pX = NULL,*pbestX = NULL;//px为当前找到的路径的头指针，pbestX为最佳路径的头指针
	if(num > n)
	{
		if(h < besth)
		{ //当前找到的路径比程序保存的最佳还要好，替换最佳路径
			free(bestX); //释放已有路径空间
			pX = X;
			pbestX = (MuBan *)malloc(sizeof(MuBan) * 1);
			*pbestX = *pX;       //复制第一个节点
			pbestX->next = NULL;
			bestX = pbestX;
			pX = pX->next;
			while(pX != NULL)
			{                    //复制其余节点
				pbestX->next = (MuBan *)malloc(sizeof(MuBan) * 1);
				*(pbestX->next) = *pX;
				pbestX->next->next = NULL;
				pbestX = pbestX->next;
				pX = pX->next;
			}
			besth=h;            //新的最佳木板高度
		}
		return 0;
	}
	l = find(num);              //需要处理的木块
	k1 = headMuBan; k2 = k1->next; k3 = k2->next;
	if(level > Line)
	{ //如果递归深度已经超过递归控制线,采用贪心算法快速得出结果,并找到合适的可以进行切割的木板
		while(!(l->h <= (k2->h + 0.0001) && l->w <= (k2->w + 0.0001)))
		{ k1 = k2; k2 = k2->next; }
		k3 = k2->next;
		level++; num++;
		k1->next=k3;
		MuBan1 = (MuBan *)malloc(sizeof(MuBan) * 1);
		MuBan2 = (MuBan *)malloc(sizeof(MuBan) * 1);
		MuBan1->next = MuBan2;
		MuBan1->x = l->w + k2->x; MuBan1->y = k2->y;
		MuBan1->w = k2->w - l->w; MuBan1->h = l->h;
		MuBan2->x=k2->x; MuBan2->y=k2->y+l->h;
		MuBan2->w=k2->w; MuBan2->h=k2->h-l->h;
		if(k2->h > 4000)
		{ //被选中切割的木板是会增加最终高度的木板，要进行剪枝
			k1->next = MuBan1;   //把剪切后的木板插入木板链表
			MuBan2->next = k3;
			h += l->h;           //高度增加
			if(h>=besth)
			{//剪枝部分
				h -= l->h;
				free(MuBan1);free(MuBan2);
				k1->next=k2;    //还原木板
				k2->next=k3;
				level--; num--; //回溯
				return 0;
			}
			insertMuBan(k2->x,k2->y,l->w,l->h);//插入选中的木板,生成结果路径
			backtracking(level,num);           //继续搜索
			delMuBan(k2->x,k2->y,l->w,l->h);   //回溯
			h -= l->h;
		}
		else
		{//切割木块的else,被选中切割的木板不会增加高度
			k1->next=MuBan1;                   //把剪切后的木板插入木板链表
			MuBan2->next=k3;
			insertMuBan(k2->x,k2->y,l->w,l->h);//插入选中的木板,生成结果路径
			backtracking(level,num);           //继续搜索
			delMuBan(k2->x,k2->y,l->w,l->h);   //回溯
		}
		free(MuBan1); free(MuBan2);
		k1->next=k2;//回溯
		k2->next=k3;
		level--; num--; 
	} //递归的if
	else
	{ //如果递归的高度不是太深，则继续深度搜索解空间
		while(k2 != NULL)
		{ //回溯法找到切割的木板K2
			if((l->h <= (k2->h + 0.0001) && l->w <= (k2->w + 0.0001)))
			{
				level++; num++; //深度搜索
				k1->next = k3;
				MuBan1 = (MuBan *)malloc(sizeof(MuBan) * 1);
				MuBan2 = (MuBan *)malloc(sizeof(MuBan) * 1);
				MuBan1->next = MuBan2;
				MuBan1->x = l->w + k2->x; MuBan1->y = k2->y;
				MuBan1->w = k2->w - l->w; MuBan1->h = l->h;
				MuBan2->x=k2->x; MuBan2->y=k2->y+l->h;
				MuBan2->w=k2->w; MuBan2->h=k2->h-l->h;
				if(k2->h < 4000)
				{ //进行剪枝
					k1->next = MuBan1;                 //把剪切后的木板插入木板链表
					MuBan2->next = k3;
					insertMuBan(k2->x,k2->y,l->w,l->h);//插入选中的木板,生成结果路径
					backtracking(level,num);           //继续搜索
					delMuBan(k2->x,k2->y,l->w,l->h);   //回溯
				}
				else
				{
					k1->next = MuBan1;
					MuBan2->next = k3;
					h += l->h;//高度增加
					if(h >= besth)
					{ //剪枝
						h -= l->h;
						free(MuBan1); free(MuBan2);
						k1->next=k2; k2->next=k3;
						level--; num--;
						return 0;
					}
					insertMuBan(k2->x,k2->y,l->w,l->h);//插入选中的木板,生成结果路径
					backtracking(level,num);           //继续搜索
					delMuBan(k2->x,k2->y,l->w,l->h);   //回溯
					h -= l->h;
				}
				free(MuBan1);free(MuBan2);
				k1->next=k2;k2->next=k3;
				level--; num--;
			}//if
			k1=k2; k2=k2->next;
			if(k2 == NULL) break;
			k3 = k2->next;
		}//while
	}
	return besth;
}

int main(void)
{	
	int i = 1;
	char FileName[20]; //数据文件
	float m;
	MuKuai *p = NULL; 	
	FILE *fp;	
	printf("请输入正确的数据文件:");
	scanf("%s",FileName);
	fflush(stdin);
	while(!(fp = fopen(FileName,"r")))
	{ //打开数据文件
		printf("\n当前目录不存在输入文件%s\n",FileName);
		printf("\n请输入正确的数据文件:");
	    scanf("%s",FileName);
		fflush(stdin);
	}
	fscanf(fp,"%d %f",&n,&W);
	printf("\n稍等，程序正在打开图形窗口!\n\n");
	printf("请按向下键实现整个画图过程!\n\n");
	x = (int)W; //用于调整opengl中屏幕的相对坐标
	while(i <= n)
	{
		p = (MuKuai *)malloc(sizeof(MuKuai) * 1);
		fscanf(fp,"%f %f",&(p->h),&(p->w));
		p->next = NULL;
		sortInsert(p);
		i++;
	}
	//根据不同的数据文件，控制递归深度
	if(n > 150)      Line = 12;
	else if(n == 16) Line = 16;
	else if(n == 25) Line = 14;
	else if(n == 50) Line = 14;
	else             Line = 15;
	A = (MuBan *)malloc(sizeof(MuBan) * n);
	headMuBan = (MuBan *)malloc(sizeof(MuBan) * 1);
	headMuBan->next = (MuBan *)malloc(sizeof(MuBan) * 1);	
	headMuBan->x = 0; headMuBan->y = 0;
	headMuBan->w = 0; headMuBan->h = 0;
	headMuBan->next->x = 0; headMuBan->next->y = 0;
	headMuBan->next->w = W; headMuBan->next->h = 65767;
	headMuBan->next->next = NULL;
	m=backtracking(1,1);
	MuBan *pA = bestX;
	for(i = n-1; i >=0; i--, pA = pA->next)
		A[i] = *pA;
	C = CreatFloatArray_2(C,n,3); //动态创建二位数组，用于存放颜色
	for(i = 0; i < n; i++)
	{
		C[i][0] = (rand()%3)/3.0 + 0.01;
		C[i][1] = (rand()%6)/6.0 + 0.3;
		C[i][2] = (rand()%9)/7 + 0.05;
	}
	auxInitDisplayMode(AUX_SINGLE|AUX_RGBA); 
	auxInitPosition(250,100,800,800); 
	auxInitWindow("阙寿辉的实验:回溯算法的运用之零件切割问题"); 
	myinit(); 
	auxKeyFunc(AUX_DOWN,down); 
	auxReshapeFunc(myReshape); 
	auxMainLoop(display); 
	printf("切割所需最佳高度为:H=%4.2f\n\n",besth);
	return 0;
}