叠木块问题与贪心算法简介20151109

问题描述：给定一个半无限大水平桌面和n个完全相同的、质量均匀的长方体木块，在桌面边缘逐个向上叠放木块并在保持不倾倒的前提下尽可能地伸出桌面，应采用什么策略可使得伸出量最大？理想化条件：问题中几个理想化的用词——“水平桌面”、“完全相同”、“质量均匀”、“长方体”。物理学原理：若物体的重心位于支持面的上方，当重力作用线在支持面内，重力矩与支持力矩平衡，物体处于平衡状态；反之，重力矩与支持力矩同方向，物体处于不平衡状态；临界的平衡条件为重力的作用线恰好经过支持面的边缘。贪心法求解：设每个木块长度均为L，重力均为G。将木块从上到下编号，依次为1、2、3、…、n。记第k（k=1,2,3,…,n）块木块相对其下方支持物的最大允许伸出量为xk（n号木块的支持物为水平桌面，其余木块的支持物为其下方的木块），第k块木块及其上方所有木块的公共重心到第k块木块另一端的距离为gk。显然，1号木块的伸出量为及公共重心为Lx211Lg211现加入2号木块，1号木块平衡的临界条件为其重力作用下恰好位于2号木块对其支持面的边缘。公共重心的坐标是其各组成部分的重心坐标的加权平均，在图示位置下两个木块的公共重心到2号木块最左端的距离为LGLGLGGGLGLGg4322221212加入第k块木块后的公共重心到第k块木块最左端的距离为LkkGLGkGGkLGLGkgk21121121第t块木块的最大允许伸出量为LkgLxkk21总伸出量为nLkLxXnknkk13121121211贪心算法简介：所谓贪心算法，就是指在对问题求解时，总是做出在当前看来是最好的选择。在本题中，每一步加入一个木块，1号木块的最大允许伸出量为L/2；加入2号木块后，两个木块的公共重心与1号木块的伸出量有关，那么2号木块的最大允许伸出量也就受1号木块的最大允许伸出量所限。由于贪心算法并非从整体最优上加以考虑，使得贪心算法并非对所有的问题都能求得最佳解；但在大多数情况下，贪心算法都能得出满意解。假设你身处一座金矿中，你最多可以携带100斤的金子离开。你身边有50斤、40斤的金块各1块，其余金块都是25斤，而你无法对金块进行切割，只能整块地拿走。最佳的策略是拿走4块25斤的金块，总计100斤；如果采用贪心法，则第一次挑选50斤的金块，第二次挑选40斤的金块，你就无法携带更多的金子了，这样一来总计只能带走90斤。这个例子说明，贪心算法并不总能求出最佳解。拓扑学中使用贪心算法的两个经典实例是最小生成树和最短哈密顿回路的问题。最小生成树问题使用普里姆（Prim）算法或克鲁斯卡尔（Kruskal）算法可以得到最佳解；而最短哈密顿回路问题通常使用“便宜”算法求满意解，以降低求解所需的时间代价。最小生成树问题：一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有结点，并且有保持图连通的最少的边。例如：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低，这就需要找到带权的最小生成树。Kruskal算法先构造包含全部结点而没有边的子图，在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，再选取次小边，直至将所有结点都连通。Prim算法是按逐个将结点连通的方式来构造最小生成树，从某一结点出发，选择与它关联的具有最小权值的边，将其结点加入到生成树的结点集合U中，以后每一步从一个结点在U中，而另一个结点不在U中的各条边中选择权值最小的边，把该边加入到生成树的边集中，把它的结点加入到集合U中，如此重复执行，直到拓扑结构中的所有结点都加入到生成树结点集合U中为止。最短哈密顿回路问题：又称旅行商问题（TSP），指从一个结点出发，经过其他所有结点一次且仅仅一次，最后返回出发点的回路称为哈密顿回路。TSP问题就是求最短哈密顿回路的问题。TSP问题已被证明不存在多项式时间①的精确解法，使用分支限界法所需时间代价（指最不利的情况下所需代价，下同）为O(n!)②③（n为拓扑结构中结点总数）；而一种称为“便宜”算法的贪心算法，使得求解的代价降为O(n2)，并且已经证明，在满足三角不等式④的拓扑结构中，使用“便宜”算法得到哈密顿回路总长度与最短哈密顿回路总长度的比值小于不大于2，通常情况下两者十分接近。分支限界法的步骤为：（1）将边权从小到大排列，初始界d0=∞；（2）在边权序列中依次选边进行深探，已选边放入栈中⑤，直至选取n条边，判断是否构成哈密顿回路（每个结点标号指出现两次且这些边只构成一个回路）；（3）（继续深探）依次删除当前已选的最长边，加入后面第一条待选边，如果构成哈密顿回路且总长度d(si)d0，则将d0=d(si)作为界；（4）（退栈过程）不能再深探时需要退栈，若栈空，则结束，其最佳值为d0，否则若新分支的d(si)≥d0，继续退栈，若d(si)d0则转（3）。“便宜”算法步骤为：（1）置nS,,3,2，01,1w，k=1，序列)1,1(T，1,,iwkiw，Si；（2）在S中，令kitjwTkSi,min,,，对回路T中的边(t,t1)和(t,t2)，若11,,ttwtjw22,,ttwtjw，则j插入到T的t和t1之间，否则j插入到T的t和t2之间。jSS，若S为空，结束，否则转（3）；（3）对全部Si，jiwkiwkiw,,,min,，转（2）。上图中，使用“便宜”算法的结果为①→②→③→④→⑤→①，总长度109；精确解为①→②→⑤→③→④→①，总长度107。叠木块问题贪心算法的正确性：设已经叠放好的(k-1)块木块的组合体放到第k块木块上时，并非放置于临界平衡位置，而是与临界平衡位置有一定的距离Δk（Δk≥0），将xk重新定义为伸出量而非最大伸出量，因此kkgLx也相应地变为kkkgLx故111211121kkkkkLkGGkLGLGkgkkkkkkkLkgLx1121nkkknknkkkkkLxX1111112式中第一项为贪心算法中的结果，第二项为各次叠放是的偏移量之间的运算。考虑第二项knkknnnnnnnkkkknnnnnkk1112111232211111113121112322101由于Δk≥0，所以该项非正，当且仅当对任意k有Δk=0时，nkkkkk1101。因此，贪心算法的结果就是最佳解。注释：①多项式时间算法：指求解所需的时间是问题规模（比如结点数、边数）的各次幂的线性组合，或者说，算法的时间复杂度为O(nk)。②n!：读作“n的阶乘”，值为1×2×3×…×n，递推式为n!=n(n-1)!，由递推式可得0!=1。③O(n!)：称一个函数g(n)是O(f(n))，当且仅当存在常数c0和n0=1，对一切nn0均有|g(n)|=c|f(n)|成立，也称函数g(n)以f(n)为界，记作g(n)=O(f(n))。定义如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。O(f(n))可以简单理解为当n→∞时与f(n)成正比。④三角不等式：三角形任意两边之和大于第三边。本文中特指从结点i出发经过结点k再到结点j的路径总长度大于从结点i直接到结点j的路径长度，即d(i,k)+d(k,j)d(i,j)）。⑤栈：一种数据结构，其限制是仅允许在表的一端进行插入和删除运算，这一端被称为栈顶。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。