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

问题描述： 给定一个半无限大水平桌面和n个完全相同的、质量均匀的长方体木块，在桌面边缘逐个向上叠放木块并在保持不倾倒的前提下尽可能地伸出桌面，应采用什么策略可使得伸出量最大？ 理想化条件： 问题中几个理想化的用词——“水平桌面”、“完全相同”、“质量均匀”、“长方体”。 物理学原理： 若物体的重心位于支持面的上方，当重力作用线在支持面内，重力矩与支持力矩平衡，物体处于平衡状态；反之，重力矩与支持力矩同方向，物体处于不平衡状态；临界的平衡条件为重力的作用线恰好经过支持面的边缘。 贪心法求解： 设每个木块长度均为L，重力均为G。将木块从上到下编号，依次为1、2、3、…、n。记第k（k=1,2,3,…,n）块木块相对其下方支持物的最大允许伸出量为xk（n号木块的支持物为水平桌面，其余木块的支持物为其下方的木块），第k块木块及其上方所有木块的公共重心到第k块木块另一端的距离为gk。显然，1号木块的伸出量为及公共重心为 现加入2号木块，1号木块平衡的临界条件为其重力作用下恰好位于2号木块对其支持面的边缘。公共重心的坐标是其各组成部分的重心坐标的加权平均，在图示位置下两个木块的公共重心到2号木块最左端的距离为 加入第k块木块后的公共重心到第k块木块最左端的距离为 第t块木块的最大允许伸出量为 总伸出量为 贪心算法简介： 所谓贪心算法，就是指在对问题求解时，总是做出在当前看来是最好的选择。在本题中，每一步加入一个木块，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，继续退栈，