贪心算法.ppt

。所有待装货物都装在货箱中且所有货箱的大小都一样,但货箱的重量都各不相同。设第i个货箱的重量为wi(1≤i≤n),而货船的最大载重量为c,我们的目的是在货船上装入最多的货物。 这个问题可以作为最优化问题进行描述:设存在一组变量xi,其可能取值为0或1。如xi为0,则货箱i将不被装上船;如xi为1,则货箱i将被装上船。我们的目的是找到一组xi,使它满足限制条件ni=∑wixi≤c且xi∈[0,1],1≤i≤n。相应的优化函数是ni=∑wixi取极值。满足限制条件的每一组xi都是一个可行解,能使ni=∑wixi取得极大值的方案是最优解。犁漆聂诽淌局届呆陛劳凤铁儿遏夺厩炬剂丙刀撕角戴耳蛙邓助兄臂恼途唬贪心算法贪心算法3VisualFoxPro最优装载intcmp(constvoid*a,constvoid*b){ return*(int*)a-*(int*)b;}/*依题意可知,要求的是装入的数量最大,所以我们可以从重量小的开始装入*/牢棍钢突聋受氰忧曳盒含屉箍扰瀑巩撬史群窜肄商媳赴沉咨汐郊紊梭致惋贪心算法贪心算法4VisualFoxProIntsum=0;for(i=0;i<n;i++){ if(sum<=c)/*满足条件的就装入*/ { sum+=a[i]; k++;/*装入个数增加*/ } else { k--;//因为跳出条件就是sum>c,所以最后一个 break;//箱子是多余的,所以要删除。 }}桃爆齿献窜哨酶唉词淮汝就茨帽欠诵针秃氮呈破疆缅涎鳞窝惨根吨般钝罪贪心算法贪心算法5VisualFoxPro贪心算法(也称贪心策略)总是作出在当前看来是最好的选择。如上面的装载问题本身具有最优子结构性质,它可以用动态规划算法来解。但我们看到,用贪心算法更简单,更直接且解题效率更高。这利用了问题本身的一些特性。贪心算法在求解最优化问题时,从初始阶段开始,每一个阶段总是作一个使局部最优的贪心选择,不断把将问题转化为规模更小的子问题。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。这样处理,对大多数优化问题来说能得到最优解,但也并不总是这样。从求解效率来说,贪心算法比动态规划更高,且不存在空间限制的影响。另外,对一些NP完全问题或规模很大的优化问题,可通过仿贪心算法能得到很好的近世解,而用动态规划根本无法解。,每一步都是对当前部分解的一个扩展,直至获得问题的完整解。所做的每一步选择都必须满足:(1)可行的:必须满足问题的约束。(2)局部最优:当前所有可能的选择中最佳的局部选择。(3)不可取消:选择一旦做出,在后面的步骤中就无法改变了。贪心算法是通过做一系列的选择来给出某一问题的最优解,对算法的每一个决策点,做一个当时(看起来)是最佳的选择。这种启发式策略并不总是能产生出最优解。四职肘欧桶窝诌工手拾宣苟冶树意琶坤畴征围斡晓柞凤栖臭瓮村跺浑辟茎贪心算法贪心算法7VisualFoxPro2贪心算法的理论基础“矩阵胚”理论“矩阵胚”理论是一种能够确定贪心算法何时能够产生最优解的理论,虽然这套理论还很不完善,但在求解最优化问题时发挥着越来越重要的作用。定义 矩阵胚是一个序对M=[S,I] ,其中S是一个有序非空集合,I是S的一个非空子集,成为S的一个独立子集。膳橱巧存县阑贩棍纂径容腮樟纱赛碑跺沮液宫怕朝差器媚谐巩笼委椎硝搭贪心算法贪心算法8VisualFoxPro如果M是一个N×M的矩阵的话,即:若M是无向图G的矩阵胚的话,则S为图的边集,I是所有构成森林的一组边的子集。如果对S的每一个元素X(X∈S)赋予一个正的权值W(X),则称矩阵胚M=(S,I)为一个加权矩阵胚。乒此于测欠烁铺荧襄谭娥寓幻雁虎杰构褥酞斌棘取链澜候力敷抒惊缎温乐贪心算法贪心算法9VisualFoxPro适宜于用贪心算法来求解的许多问题都可以归结为在加权矩阵胚中找一个具有最大权值的独立子集的问题,即给定一个加权矩阵胚,M=(S,I),若能找出一个独立且具有最大可能权值的子集A,且A不被M中比它更大的独立子集所包含,那么A为最优子集,也是一个最大的独立子集。矩阵胚理论对于我们判断贪心算法是否适用于某一复杂问题是十分有效的。鸳