实验报告四：用贪心算法优化的石板切割问题
实验报告四：用贪心算法优化石板切割问题
一、 实验要求
给出一长度、高度均已知的木板，给出一系列长度、高度的目标板。
要求：
•目标板不能旋转，目标板长宽必须与木板长宽对应。•必须沿长边短边一刀切，每一次切割将木板分割为两个矩形。•目标板的一角应与木板一角重合。•为简化问题，题中所给的长宽均为整数。请给出木板利用率最高的切割方案。
二、问题分析与方案设计
本题的解决方案是完全原创的。
贪心算法设计综述
贪心是一种通过寻求局部最优解来获得全局最优解（或全局最优近似解）的算法，因此，根据贪心的定义很容易联想到此题的贪心解法为：将所有小目标块按照面积排序，根据面积大小，进行选择，每一步选择当前最大的一个，从而每一步都是局部最优解，这个算法看起来正确，但细细深究，其实不然，如下图：
若要在橙色的木板上切割①②③④⑤五个石板，显然，石板⑤是最大的，但倘若第一步就使用贪心算法，会立即选择⑤，而得不到其他可能的结果，从图像中可以看出，直接选择⑤得到的切割率小于100%，而选择①②③④得到的切割率却为100%，因此得到了一个错误的答案，这个特例告诉我们，不能直接使用选取最大面积的方式作为贪心策略。
经过进一步思考，我发现，特例中一开始直接选择⑤会导致其他目标板失去“出场机会”，有没有办法去保证其他目标板的“出场机会”呢？其实是有的。
每一种可行的切割方案中，一定可以找出一块最大的块，最佳可行的切割方案中的最大的目标块，并不一定是所有目标块中最大的目标块，因此，我们可以考虑对所有目标块使它作为最大块，然后进行枚举，这样操作后，我们保证了每一块都能有至少一次“出场机会”，然后对他们取最大值，就可以得到贪心策略算法的（近似）最优解。这样的枚举方式涵盖了所有可能的切割方法。
这样得到的最优解是全局最优解吗？由于纵切与横切的存在，本实验报告代码得到的并非全局最优解，与张德富老师的论文结果进行比较，得到在50、100等级的数据量上，得到的结果误差小于5%，甚至在某些情况下得到了更优的解决方案，但在10000数量级的目标块下，张德富老师的有一个数据可以得到100% 的测试结果，而本算法只能得到65.9%，至于这个问题，可以参考深度学习的思想去尝试进行解决，通过增加运算量来尽可能的获得全局最优解，这一部分将其写在了未进行的优化部分中。
结构
本题我使用了两个struct结构体、两个子函数、使用到了STL中的vector、bitset和sort排序算法，下面一一介绍他们的功能：
struct Stone:
struct Stone{int x, y;int s;bool operator<(const Stone &s2) const{return s < s2.s;}} stone[N];
这一个结构体用于存放目标块的信息，且其中重载了小于运算符，使得stone数组可以使用sort算法直接排序。
struct subStone:
struct subStone{Stone substone[4];bitset<4> key;};
这一个结构体用于存放切割下来的四个子块以及他们的“开关”
两个STL容器的作用：
bitset : 用于表示已经切割完毕的石板编号vector : 建立subStone数组，存放当前有的子板
子函数divide：
bool divide(int i){if (st.empty())return false;for (int k = st.size() - 1; k >= 0; k--) //从小往大for (int j = 0; j < 4; j++){if (st[k].key[j]);elsecontinue;if (st[k].substone[j].x < stone[i].x || st[k].substone[j].y < stone[i].y)continue;//能切if (j == 0 || j == 1)st[k].key[2] = st[k].key[3] = 0; //切割方式固定了elsest[k].key[0] = st[k].key[1] = 0;subStone tmp;tmp.substone[0].x = st[k].substone[j].x;tmp.substone[0].y = tmp.substone[2].y = st[k].substone[j].y - stone[i].y;tmp.substone[1].x = tmp.substone[3].x = st[k].substone[j].x - stone[i].x;tmp.substone[1].y = stone[i].y;tmp.substone[2].x = stone[i].x;tmp.substone[3].y = st[k].substone[j].y;tmp.key.set();st.push_back(tmp);st[k].key[j] = 0;return true;}return false;}
divide的功能是尝试对目标板i在当前的子板范围内进行切割，倘若能够切割返回true并修改相关子板信息，倘若不能切割，则返回false；
select子函数：
int select(int i, int mxx, int mxy){used.reset();st.clear();int s = 0;if (mxx < stone[i].x || mxy < stone[i].y)return 0; //最大的不能被选中，return 0subStone tmp;tmp.substone[0].x = mxx;tmp.substone[0].y = mxy;tmp.key[0] = 1;st.push_back(tmp);for (int k = i; k >= 0; k--)if(divide(k)){s += stone[k].s;used[k] = 1;}return s;}
select子函数用于返回以板块i为最大板块时可以切割的最大面积。
特殊算法解释
如何完成横切与竖切
本实验中，不再特别地考虑横切与竖切，只考虑能否将当前的最大石板完成切割，那具体如何进行？如下图：
•石板刚切完形成的4个新小石板均是存在的（对应横竖切都是可能的）•下一次循环检查后，倘若能够使用小石板，小石板被切割，状态应该修改为不存在•一旦有小石板因为切割不存在，那么，根据上一块小石板产生的原因，另外一种方式产生的小石板将标记为不存在，即，倘若substone[0]，substone[1]被使用，substone[2]，substone[3]将立即被标记为不存在。
如何完成石板选择
完成石板选择依照：“目标板stone从大选到小，待切板subStone从新选到旧”的原则进行，即遍历stone和vector数组时均按照从后往前的顺序进行。进入到每一个subStone根据其已经标记好的“开关”依次进入到每一个板中，再进行切割，形成新的子板，再加入到vector数组中，直至不再有石板或目标板。
完全代码展示（含注释）
#include <iostream>#include <algorithm>#include <bitset>#include <vector>using namespace std;const int N = 100;//根据不同的测试数据大小选择不同的N值struct Stone{int x, y;//记录一块石板的长宽int s;//记录一块石板的面积bool operator<(const Stone &s2) const{return s < s2.s;}//重载小于运算符} stone[N];struct subStone{Stone substone[4];bitset<4> key;};bitset<N> used;//记录使用过的石板vector<subStone> st;//记录当前所有石板bool divide(int i){if (st.empty())return false;//如果石板已经是空的，那就返回无法切割for (int k = st.size() - 1; k >= 0; k--) //从小往大for (int j = 0; j < 4; j++){if (st[k].key[j]);elsecontinue;//如果key检查该板不存在，跳过if (st[k].substone[j].x < stone[i].x || st[k].substone[j].y < stone[i].y)continue;//如果不能切，跳过//能切if (j == 0 || j == 1)st[k].key[2] = st[k].key[3] = 0; //切割方式固定了elsest[k].key[0] = st[k].key[1] = 0;//横竖切只能存在一种subStone tmp;tmp.substone[0].x = st[k].substone[j].x;tmp.substone[0].y = tmp.substone[2].y = st[k].substone[j].y - stone[i].y;tmp.substone[1].x = tmp.substone[3].x = st[k].substone[j].x - stone[i].x;tmp.substone[1].y = stone[i].y;tmp.substone[2].x = stone[i].x;tmp.substone[3].y = st[k].substone[j].y;tmp.key.set();//1111st.push_back(tmp);//以上步骤均为给tmp（新的子板）赋值st[k].key[j] = 0;return true;//能切，切一次就行，返回true}return false;}int select(int i, int mxx, int mxy){used.reset();st.clear();//初始化int s = 0;if (mxx < stone[i].x || mxy < stone[i].y)return 0; //最大的不能被选中，return 0subStone tmp;tmp.substone[0].x = mxx;tmp.substone[0].y = mxy;tmp.key[0] = 1;st.push_back(tmp);//放入第一块子板for (int k = i; k >= 0; k--)//遍历所有子板if(divide(k)){s += stone[k].s;used[k] = 1;}return s;//返回贪心最优解}int main(){int n, maxx, maxy;cin >> n;cin >> maxx >> maxy;for (int i = 0; i < n; i++){cin >> stone[i].x >> stone[i].y;stone[i].s = stone[i].x * stone[i].y;}//数据录入完成sort(stone, stone + n);//排序完成int maxs = 0;bitset<N> fused;//用于给used数组做备份for (int i = n - 1; i >= 0; i--){int tmp = select(i, maxx, maxy);if (tmp > maxs){maxs = tmp;fused = used;}}//每一次循环都得到以板块i为最大板块时的最优解cout << maxs << ' ' << fused.to_string() << endl;cout << ((double)maxs/((double)maxx*maxy));//输出结果}
未进行的优化
•我们可以在Stone 结构体中添加从第一块目标块到第k块目标块的面积和，倘若我们求出的最大面积已经大于或等于了当前的目标和，说明，我们即使将所有比第k块小的目标块都切割，也得不到比当前结果更优的解，就可以直接输出结果，该逻辑实现并不困难，所以并未重新在代码中实现。•我们也可以在subStone结构体中添加一个标记量，从而可以记录在此处是横切还是纵切，然后通过一个觅踪函数，就可以输出每一块石板的切割方式以及切割路径。•为了提高得到全局最优解的概率，我们可以在审查subStone.key时引入随机数，使得我们不一定总是从横切开始检查，使得我们可以在横切竖切中随机优先检查，这样，可能得到横切竖切的不同路径，而本算法若要同时检查横切竖切，则会增加大量的复制与递归调用，我认为这可能使得算法丢失了贪心选择性质。
测试
1.使用书上的测试数据
测试数据输入：
44 83 22 41 64 4
测试数据输出：
24 11000.75
2.使用上述例子的测试数据测试数据输入：
54 42 22 22 22 23 3
测试数据输出：
16 011111
3.使用50、 100 、 10000数据量的测试数据及与张德福老师论文的比较结果
| 数据量 | 本实验算法结果 | 张德福老师的算法最佳结果 |
| 50 | 0.931875 | 0.3291（偏差较大，存疑） |
| 100 | 0.900467 | 0.9213 |
| 10000 | 0.658533 | 1.000000 |