种菜建模
[編輯] [转简体] (简体译文)
|
作者:zouhaiyuan
| 分類:【算法】種菜算法
[
26 瀏覽
0 評論
7 贊
7 踩
]
概要
种菜建模 有两种方案
1)横排
2)竖排
注意:
横排与竖排可以通过地块及障碍物坐标变换来实现
每种方案都采用如下4个步骤
step1.求取宽度方向能放几排,每排如何组合
step2.求取长度方向组合,即一排中能放什么规格的箱子
step3.避开障碍物
step4.求取种植面积
正文
#include <stdio.h> typedef struct _tagBlock { int left; int bottom; int length; int width; }BLOCK; typedef struct _tagFarmland { int length; int width; BLOCK stBlock; }FARMLAND; //箱子宽度方向组合利用率 typedef struct _tagBoxWidthAvailability { int width1; int width2; double availability; }BOX_WIDTH_AVAILABILITY; typedef struct _tagRowClass { BOX_WIDTH_AVAILABILITY stWidthAvailability; int nRowNum; }ROW_CLASS; typedef struct _tagColClass { int nLenSpec; int nColNum; }COL_CLASS; typedef struct _tagRowRect { int left; int top; int right; int bottom; int halfTop;//半行处的top int width1;//上半行箱子宽度 int width2;//下半行箱子宽度 int realBoxNum1;//上半行箱子数量 int realBoxNum2;//下半行箱子数量 int blocked1;//上半行是否受阻,0--未障碍,1--受障碍 int blocked2;//下半行是否受阻,0--未障碍,1--受障碍 int ailseBlocked;//所属走道是否阻塞,0--未受阻,1--受阻,注意,走道在每行的下侧 int boxClassIndex;//改行采用的箱子组合类型序号 }ROW_RECT; int GetArea(int p_pnLenBoxSpecs[], int p_nNumLenSpecs, int p_pnWidthBoxSpecs[], int p_nNumWidthSpecs, int p_nAisle, FARMLAND p_stFarmland) { //将长度规格和宽度规格从大到小排好序 //注意,每种长度规格都有其对应的全部宽度规格,即总规格数量为 长度规格数量*宽度规格数量 //int pnLenBoxSpecs[] = { 80,120,200,160}; //int pnWidthBoxSpecs[] = {80,40}; int* pnLenBoxSpecs = new int[p_nNumLenSpecs]; int* pnWidthBoxSpecs = new int[p_nNumWidthSpecs]; int nNumLenBoxSpecs = p_nNumLenSpecs;//sizeof(pnLenBoxSpecs)/ sizeof(int); int nNumWidthBoxSpecs = p_nNumWidthSpecs;//sizeof(pnWidthBoxSpecs)/ sizeof(int); for (int i = 0; i < nNumLenBoxSpecs; i++) { pnLenBoxSpecs[i] = p_pnLenBoxSpecs[i]; } for (int i = 0; i < nNumWidthBoxSpecs; i++) { pnWidthBoxSpecs[i] = p_pnWidthBoxSpecs[i]; } printf("种植箱规格:\r\n"); for (int i = 0; i < nNumWidthBoxSpecs; i++) { for (int j = 0; j < nNumLenBoxSpecs; j++) { printf("%d x %d\r\n", pnLenBoxSpecs[j], pnWidthBoxSpecs[i]); } } printf("\r\n"); FARMLAND stFarmland = p_stFarmland;//{ 1080,550,{100,200,170,140} }; printf("地块 长 %d, 宽 %d\r\n", stFarmland.length, stFarmland.width); printf("管线井 左侧 %d,底部 %d, 长 %d, 宽 %d\r\n", stFarmland.stBlock.left, stFarmland.stBlock.bottom, stFarmland.stBlock.length, stFarmland.stBlock.width); int aisle = p_nAisle;//30; printf("过道宽度 %d\r\n\r\n", aisle); //方案一,横排 //根据种植要求,种植箱长边至少一侧预留通道, // 那么,最大利用率就是仅仅一侧留通道,即箱子A的长边和箱子B的长边紧紧挨着。 // 此时宽度方向的利用率为 (箱子A的宽度+箱子B的宽度)/(箱子A的宽度+箱子B的宽度+过道宽度) // 由此可知,要想宽度方向利用率高,那箱子的宽度就要尽量的大 // // 种植箱宽度方向未对过道作要求,因此箱子的宽度侧紧紧挨着,此时利用率最大 // // 进园后需要横向和纵向过道 // // 种植示意图如下: // //*********************************************************************************** //* 过道 * //* ________________________________________________________________________ * //*过道 | | | | |可* //* |____________________|___________________|___________________|___________|能* //入 | | | | |空* //口 |____________________|___________________|___________________|___________|隙* //* * //* 过道 * //* ________________________________________________________________________ * //*过道 | | | | | * //* |____________________|___________________|___________________|___________| * //* | | | | | * //* |____________________|___________________|___________________|___________| * //* * //* 过道 * //* ________________________________________________________________________ * //*过道 | | | | | * //* |____________________|___________________|___________________|___________| * //* | | | | | * //* |____________________|___________________|___________________|___________| * //* * //* 过道 * //* ________________________________________________________________________ * //*过道 | | | | | * //* |____________________|___________________|___________________|___________| * //* | | | | | * //* |____________________|___________________|___________________|___________| * //* * //* 过道 * //* ________________________________________________________________________ * //*过道 | | | | | * //* |____________________|___________________|___________________|___________| * //* |____________________|___________________|___________________|___________| * // * * //* 过道 * //* * //* 可能空隙 * // *********************************************************************************** // // 如上图,将两个箱子长度方向紧紧靠在一起,又将四个箱子宽度方向靠在一起,形成一行 // 那么如果有 N 行的话,那么与之平行的过道就有N+1条过道 // 注意,最后一行可能不是两个最大宽度的箱子靠在一起,甚至可能是单个箱子成一行 // 由此,我们先将两个箱子长度靠在一起,甚至单个箱子成一行的利用率按照从大到小形成一个数组 // printf("\r\nStep1.\r\n计算宽度方向箱子布局\r\n\r\n"); //step1. //计算两个箱子长度靠在一起,甚至单个箱子成一行的利用率 BOX_WIDTH_AVAILABILITY* pstAvailability = new BOX_WIDTH_AVAILABILITY[nNumWidthBoxSpecs * nNumWidthBoxSpecs + nNumWidthBoxSpecs]; int nNumAvailability = 0; int nNumWidthBoxSpecsTemp = nNumWidthBoxSpecs; //双排箱子 while (nNumWidthBoxSpecsTemp > 0) { for (int i = nNumWidthBoxSpecs - nNumWidthBoxSpecsTemp; i < nNumWidthBoxSpecs; i++) { pstAvailability[nNumAvailability].width1 = pnWidthBoxSpecs[nNumWidthBoxSpecs - nNumWidthBoxSpecsTemp]; pstAvailability[nNumAvailability].width2 = pnWidthBoxSpecs[i]; pstAvailability[nNumAvailability].availability = (pstAvailability[nNumAvailability].width1 + pstAvailability[nNumAvailability].width2) * 1.0 / (pstAvailability[nNumAvailability].width1 + pstAvailability[nNumAvailability].width2 + aisle); nNumAvailability++; } nNumWidthBoxSpecsTemp--; } //单排箱子 for (int i = 0; i < nNumWidthBoxSpecs; i++) { pstAvailability[nNumAvailability].width1 = pnWidthBoxSpecs[i]; pstAvailability[nNumAvailability].width2 = 0; pstAvailability[nNumAvailability].availability = (pstAvailability[nNumAvailability].width1) * 1.0 / (pstAvailability[nNumAvailability].width1 + aisle); nNumAvailability++; } printf("种植箱宽度组合\r\n"); for (int i = 0; i < nNumAvailability; i++) { printf("%d: %d - %d - %lf\r\n", i, pstAvailability[i].width1, pstAvailability[i].width2, pstAvailability[i].availability); } //利用率排序 int nLoop = nNumAvailability; for (int i = 0; i < nLoop;) { BOX_WIDTH_AVAILABILITY stAvailability = pstAvailability[i]; for (int j = 1; j < nLoop; j++) { if (stAvailability.availability < pstAvailability[j].availability) { pstAvailability[j - 1] = pstAvailability[j]; pstAvailability[j] = stAvailability; } else { stAvailability = pstAvailability[j]; } } nLoop--; } printf("种植箱宽度组合(排序)\r\n"); for (int i = 0; i < nNumAvailability; i++) { printf("%d: %d - %d - %lf\r\n", i, pstAvailability[i].width1, pstAvailability[i].width2, pstAvailability[i].availability); } //按照利用率高的优先使用的原则布满地块宽度,求取布了多少行,及使用何种组合布置 //注意,该原则下,并不一定结果是最优解。但很接近最优解 // /* //下面尝试多次使用该原则找最优解,增加了代码复杂的,抛弃。。。 nLoop = nNumAvailability;//如果nLoop =1,就是优先使用最大利用率组合。不进行多次尝试。 ROW_CLASS *pstRowClass = new ROW_CLASS[nLoop*nNumAvailability]; int* pnRowClassNum = new int[nLoop]; int* pnWidthRemainder = new int[nLoop]; int* pnWidthUsed = new int[nLoop]; for (int k = 0; k < nLoop; k++) { int nValidWidth = stFarmland.width - aisle;//有效宽度,即去掉了第一行过道之后的剩余宽度 int nRowClassNum = 0; int nWidthUsed = 0; for (int i = k; i < nNumAvailability; i++) { int nNum = nValidWidth / (pstAvailability[i].width1 + pstAvailability[i].width2 + aisle); if (nNum > 0) { pstRowClass[k* nNumAvailability + nRowClassNum].stWidthAvailability = pstAvailability[i]; pstRowClass[k * nNumAvailability + nRowClassNum].nRowNum = nNum; nRowClassNum++; nWidthUsed += nNum*(pstAvailability[i].width1 + pstAvailability[i].width2); } //剩余地块宽度 nValidWidth = nValidWidth % (pstAvailability[i].width1 + pstAvailability[i].width2 + aisle); } pnRowClassNum[k] = nRowClassNum; pnWidthRemainder[k] = nValidWidth; pnWidthUsed[k] = nWidthUsed; printf("--组合类型数 %d ,使用的宽度%d 最后空隙 %d--\r\n", nRowClassNum, nWidthUsed,nValidWidth); } printf("\r\n地块宽度方向的布置\r\n"); for (int k=0;k<nLoop;k++) { printf("[-- %d --]\r\n", k); for (int i = 0; i < pnRowClassNum[k]; i++) { printf("%d: 行数:%d 箱1宽度:%d 箱2宽度%d\r\n", i, pstRowClass[k* nNumAvailability +i].nRowNum, pstRowClass[k * nNumAvailability + i].stWidthAvailability.width1, pstRowClass[k * nNumAvailability + i].stWidthAvailability.width2); } printf("使用宽度 %d, 最后空隙 %d\r\n", pnWidthUsed[k], pnWidthRemainder[k]); } */ // //下面直接优先使用利用率高的箱子,不多次尝试 nLoop = 1;//如果nLoop =1,就是优先使用最大利用率组合。不进行多次尝试。 ROW_CLASS* pstRowClass = new ROW_CLASS[nLoop * nNumAvailability]; int* pnRowClassNum = new int[nLoop]; int* pnWidthRemainder = new int[nLoop]; int* pnWidthUsed = new int[nLoop]; int nValidWidth = stFarmland.width - aisle;//有效宽度,即去掉了第一行过道之后的剩余宽度 int nRowClassNum = 0; int nWidthUsed = 0; int nWidthRemainder = 0; for (int i = 0; i < nNumAvailability; i++) { int nNum = nValidWidth / (pstAvailability[i].width1 + pstAvailability[i].width2 + aisle); if (nNum > 0) { pstRowClass[nRowClassNum].stWidthAvailability = pstAvailability[i]; pstRowClass[nRowClassNum].nRowNum = nNum; nRowClassNum++; nWidthUsed += nNum * (pstAvailability[i].width1 + pstAvailability[i].width2); } //剩余地块宽度 nValidWidth = nValidWidth % (pstAvailability[i].width1 + pstAvailability[i].width2 + aisle); } nWidthRemainder = nValidWidth; printf("\r\n宽度方向利用率较高箱子组合 [结果]\r\n"); for (int i = 0; i < nRowClassNum; i++) { printf("%d: 行数:%d 箱1宽度:%d 箱2宽度%d\r\n", i, pstRowClass[i].nRowNum, pstRowClass[i].stWidthAvailability.width1, pstRowClass[i].stWidthAvailability.width2); } printf("使用宽度 %d, 最后空隙 %d\r\n\r\n", nWidthUsed, nWidthRemainder); printf("\r\nStep2.\r\n计算长度方向箱子布局\r\n\r\n"); //Step2. //计算长度方向需要哪些规格箱子组合 // //先将箱子长度进行排序 nLoop = nNumLenBoxSpecs; for (int i = 0; i < nLoop;) { int nLen = pnLenBoxSpecs[i]; for (int j = 1; j < nLoop; j++) { if (nLen < pnLenBoxSpecs[j]) { pnLenBoxSpecs[j - 1] = pnLenBoxSpecs[j]; pnLenBoxSpecs[j] = nLen; } else { nLen = pnLenBoxSpecs[j]; } } nLoop--; } printf("种植箱长度(排序)\r\n"); for (int i = 0; i < nNumLenBoxSpecs; i++) { printf("%d: %d\r\n", i, pnLenBoxSpecs[i]); } //下面同样采用优先选用长度更长的种植箱之原则, //由于在该方向上,箱子一个个紧紧挨着,不需要留出过道,因此,该方向的利用率全都是100%, //所以需要比较不同情况下分别剩余的空隙,找到间隙最小的即利用率最大 int nValidLength = stFarmland.length - aisle; int* pnLenRemainder = new int[nNumLenBoxSpecs]; COL_CLASS* pstColClass = new COL_CLASS[nNumLenBoxSpecs * nNumLenBoxSpecs]; int* pnColClassNum = new int[nNumLenBoxSpecs]; for (int i = 0; i < nNumLenBoxSpecs; i++) { int nColClassNum = 0; nValidLength = stFarmland.length - aisle; for (int j = i; j < nNumLenBoxSpecs; j++) { int nNum = nValidLength / pnLenBoxSpecs[j]; if (nNum > 0) { nValidLength = nValidLength % pnLenBoxSpecs[j]; pstColClass[i * nNumLenBoxSpecs + nColClassNum].nLenSpec = pnLenBoxSpecs[j]; pstColClass[i * nNumLenBoxSpecs + nColClassNum].nColNum = nNum; nColClassNum++; } } pnLenRemainder[i] = nValidLength; pnColClassNum[i] = nColClassNum; } printf("箱子长度方向排列\r\n"); for (int i = 0; i < nNumLenBoxSpecs; i++) { printf("[-- %d --]\r\n", i); for (int j = 0; j < pnColClassNum[i]; j++) { printf("[规格 %d: 数量 %d ] ", pstColClass[i * nNumLenBoxSpecs + j].nLenSpec, pstColClass[i * nNumLenBoxSpecs + j].nColNum); } printf("空隙 %d\r\n", pnLenRemainder[i]); } //寻找最小余数 int nLenMinIndex = 0; int nMin = pnLenRemainder[0]; for (int i = 0; i < nNumLenBoxSpecs; i++) { if (pnLenRemainder[i] < nMin) { nMin = pnLenRemainder[i]; nLenMinIndex = i; } } //将长度方向的最具有最小余数的箱子组合 (可能是其中一种) int nNumBoxInRow = 0;//储存长度方向箱子组合结果 数量 for (int i = 0; i < pnColClassNum[nLenMinIndex]; i++) { nNumBoxInRow += pstColClass[nLenMinIndex * nNumLenBoxSpecs + i].nColNum; } int* pnBoxLenSpecInRow = new int[nNumBoxInRow];//储存长度方向箱子组合结果 int nIndex = 0; for (int i = 0; i < pnColClassNum[nLenMinIndex]; i++) { for (int j = 0; j < pstColClass[nLenMinIndex * nNumLenBoxSpecs + i].nColNum; j++) { pnBoxLenSpecInRow[nIndex] = pstColClass[nLenMinIndex * nNumLenBoxSpecs + i].nLenSpec; nIndex++; } } printf("\r\n长度方向最小余数的箱子组合 [结果]\r\n"); for (int i = 0; i < nNumBoxInRow; i++) { printf("[ %d ] ", pnBoxLenSpecInRow[i]); } printf("空隙 %d\r\n\r\n", pnLenRemainder[nLenMinIndex]); printf("step3.\r\n避让障碍物\r\n\r\n"); //step3. //避让障碍物 //换算障碍物坐标 int nBlockLeft = stFarmland.stBlock.left; int nBlockTop = stFarmland.width - (stFarmland.stBlock.bottom + stFarmland.stBlock.width); int nBlockRight = stFarmland.stBlock.left + stFarmland.stBlock.length; int nBlockBottom = stFarmland.width - stFarmland.stBlock.bottom; printf("障碍物坐标 %d,%d,%d,%d\r\n\r\n", nBlockLeft, nBlockTop, nBlockRight, nBlockBottom); //计算哪些行在障碍物处 int nAllRowNum = 0; for (int i = 0; i < nRowClassNum; i++) { nAllRowNum += pstRowClass[i].nRowNum; } ROW_RECT* pstRowRect = new ROW_RECT[nAllRowNum]; int nRowIndex = 0; int nRowTop = aisle; for (int i = 0; i < nRowClassNum; i++) { for (int j = 0; j < pstRowClass[i].nRowNum; j++) { pstRowRect[nRowIndex].boxClassIndex = i; pstRowRect[nRowIndex].left = aisle; pstRowRect[nRowIndex].top = nRowTop; pstRowRect[nRowIndex].right = stFarmland.length - aisle - pnLenRemainder[nLenMinIndex]; pstRowRect[nRowIndex].bottom = pstRowRect[nRowIndex].top + (pstRowClass[i].stWidthAvailability.width1 + pstRowClass[i].stWidthAvailability.width2); pstRowRect[nRowIndex].halfTop = pstRowRect[nRowIndex].top + pstRowClass[i].stWidthAvailability.width1; pstRowRect[nRowIndex].width1 = pstRowClass[i].stWidthAvailability.width1; pstRowRect[nRowIndex].width2 = pstRowClass[i].stWidthAvailability.width2; int nRowHalf = pstRowRect[nRowIndex].halfTop; //判断是否阻碍该行 if (nRowHalf > nBlockTop) { if (pstRowRect[nRowIndex].top < nBlockBottom) { //上半行阻塞 pstRowRect[nRowIndex].blocked1 = 1; } else { pstRowRect[nRowIndex].blocked1 = 0; } } else { pstRowRect[nRowIndex].blocked1 = 0; } if (pstRowRect[nRowIndex].bottom > nBlockTop) { if (nRowHalf < nBlockBottom) { //下半行阻塞 pstRowRect[nRowIndex].blocked2 = 1; } else { pstRowRect[nRowIndex].blocked2 = 0; } } else { pstRowRect[nRowIndex].blocked2 = 0; } //判断走道阻塞 if (pstRowRect[nRowIndex].bottom + aisle > nBlockTop) { if (pstRowRect[nRowIndex].bottom + aisle + pnLenRemainder[nLenMinIndex] < nBlockBottom) { //这里挪用了最下面的空隙 pstRowRect[nRowIndex].ailseBlocked = 1; } else { pstRowRect[nRowIndex].ailseBlocked = 0; } } else { pstRowRect[nRowIndex].ailseBlocked = 0; } nRowTop = pstRowRect[nRowIndex].bottom + aisle; nRowIndex++; } } //显示行受阻情况 printf("行受阻情况\r\n"); for (int i = 0; i < nAllRowNum; i++) { printf("行%d: [%d,%d,%d,%d] %d,%d,%d\r\n", i, pstRowRect[i].left, pstRowRect[i].top, pstRowRect[i].right, pstRowRect[i].bottom, pstRowRect[i].blocked1, pstRowRect[i].blocked2, pstRowRect[i].ailseBlocked); } //根据受阻行的信息,剔除合适大小的箱子 //int* pnRealBoxNumInRow = new int[nAllRowNum*2];//避让障碍物后每行的箱子数,每行都分上半行和下半行 printf("剔除行中合适大小的箱子\r\n"); for (int i = 0; i < nAllRowNum; i++) { int nDeleteNum = 0; //先初始化 //pnRealBoxNumInRow[i * 2] = nNumBoxInRow; //pnRealBoxNumInRow[i * 2 + 1] = nNumBoxInRow; pstRowRect[i].realBoxNum1 = nNumBoxInRow; pstRowRect[i].realBoxNum2 = nNumBoxInRow; printf("第 %d 行", i); if (pstRowRect[i].ailseBlocked) { //过道受阻 //清理出过道 if (nBlockTop - pstRowRect[i].halfTop > aisle) { //清出下半行即可通行 //需要清理出的纵向空间为 2*aisle + stFarmland.stBlock.length //找出该上半行中合适大小的箱子 nDeleteNum = 0; int nLen = pnLenRemainder[nLenMinIndex]; if (nLen >= 2 * aisle + stFarmland.stBlock.length) { //空隙就已经够障碍物宽度,不用剔除箱子 } else { //箱子已经从大到小排列了,从面删除即可 for (int i = nNumBoxInRow - 1; i >= 0; i--) { nLen += pnBoxLenSpecInRow[i]; nDeleteNum++; if (nLen >= stFarmland.stBlock.length) { break; } } } pstRowRect[i].realBoxNum2 = nNumBoxInRow - nDeleteNum; //pnRealBoxNumInRow[i * 2+1] = nNumBoxInRow - nDeleteNum; printf("下 删除 %d 个箱子 \r\n", nDeleteNum); } else { //上下半行都需要清理 nDeleteNum = 0; int nLen = pnLenRemainder[nLenMinIndex]; if (nLen >= 2 * aisle + stFarmland.stBlock.length) { //空隙就已经够障碍物宽度,不用剔除箱子 } else { //箱子已经从大到小排列了,从面删除即可 for (int i = nNumBoxInRow - 1; i >= 0; i--) { nLen += pnBoxLenSpecInRow[i]; nDeleteNum++; if (nLen >= stFarmland.stBlock.length) { break; } } } pstRowRect[i].realBoxNum1 = nNumBoxInRow - nDeleteNum; pstRowRect[i].realBoxNum2 = nNumBoxInRow - nDeleteNum; //pnRealBoxNumInRow[i * 2] = nNumBoxInRow - nDeleteNum; //pnRealBoxNumInRow[i * 2 + 1] = nNumBoxInRow - nDeleteNum; printf("上 删除 %d 个箱子 \r\n", nDeleteNum); printf("下 删除 %d 个箱子 \r\n", nDeleteNum); } } else { if (pstRowRect[i].blocked1) { //找出该上半行中合适大小的箱子 nDeleteNum = 0; int nLen = pnLenRemainder[nLenMinIndex]; if (nLen >= stFarmland.stBlock.length) { //空隙就已经够障碍物宽度,不用剔除箱子 } else { //箱子已经从大到小排列了,从面删除即可 for (int i = nNumBoxInRow - 1; i >= 0; i--) { nLen += pnBoxLenSpecInRow[i]; nDeleteNum++; if (nLen >= stFarmland.stBlock.length) { break; } } } pstRowRect[i].realBoxNum1 = nNumBoxInRow - nDeleteNum; //pnRealBoxNumInRow[i * 2] = nNumBoxInRow- nDeleteNum; printf("上 删除 %d 个箱子 \r\n", nDeleteNum); } if (pstRowRect[i].blocked2) { //找出该下半行中合适大小的箱子 nDeleteNum = 0; int nLen = pnLenRemainder[nLenMinIndex]; if (nLen >= stFarmland.stBlock.length) { //空隙就已经够障碍物宽度,不用剔除箱子 } else { //箱子已经从大到小排列了,从面删除即可 for (int i = nNumBoxInRow - 1; i >= 0; i--) { nLen += pnBoxLenSpecInRow[i]; nDeleteNum++; if (nLen >= stFarmland.stBlock.length) { break; } } } pstRowRect[i].realBoxNum2 = nNumBoxInRow - nDeleteNum; &