?? 零件切割問題.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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -