贪心算法经典例题贪心算法( 三 )

3.2.2.1 贪心算法1
第一步:设置一个记录三角剖分中边的数组T 。
第二步:计算点集S中所有点对之间的距离d(pi，pj)，1≤i，j≤n，i≠j，并且对距离从小到大进行排序，设为d1，d2，…，dn(n-1)/2，相应的线段记为e1，e2，…，en(n-1)/2，将这些线段存储在数组E中。
第三步:从线段集E中取出长度最短的边e1存到T中作为三角剖分的第一条边，此时k=1 。
第四步:依次从E中取出长度最短的边ek，与T中已有的边进行求交运算，如果不相交则存到T中，并从E中删除ek 。这一步运行到S中没有边为止，即至k=n(n-1)/2 。
第五步:输出T 。
该算法中，第二步需要计算n(n-1)/2次距离，另外距离排序需要O(n2lgn)次比较。T中元素随第四步循环次数的增加而增加，因此向T中加入一条新边所需要的判定两条线段是否相交的次数也随之增加。如果第四步的前3n-6次循环后已经构成点集的三角剖分，那么第四步循环所需要的判定两条线段是否相交的次数为
1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n3)
在常数时间内可以判定两条线段是否相交，因此该算法的时间复杂性为O(n3) 。
3.2.2.2 贪心算法2
第一步:求点集的凸壳，设凸壳顶点为p1，p2，…，pm，凸壳的边为e1，e2，…，em 。并将凸壳顶点按顺序连接成边的ei加入T(三角剖分的边集合)，并且ei的权值被赋为1 。凸壳内点的集合为S1={pm+1，pm+2，…，pn} 。
第二步:从内部点S1中任取一点pi，求与pi距离最近的点pj，将线段存入T 。
第三步:求与pj距离最近的点(除点pi外)，设为pk，并将线段存入T，pipjpk构成一个三角形，并将三条边wij、wjk和wki的权值设为1 。
第四步:分别求与pi、pj和pk距离最近的点(除点pi、pj和pk本身外)，设为p'i，p'j，p'k，将加入T，并将这些边的权值设为1，而wij、wjk和wki的值加1，即为2 。边的权值为2则表示该边为两个三角形共有。
第五步:对权值为1的边(除e1，e2，…，em外)的两个端点分别求与其距离最近的点，并将其连线(得到新的三角形)加入T，新三角形边的权值加1 。
第六步:对权值为1的边重复上一步，当一条边被使用一次其权值增加1，直到所有边的权值均为2为止(除e1，e2，…，em外) 。
贪心算法2中，第一步耗费O(nlgn);第二步需要计算n-1次距离与n-2次比较;第三步求pk要计算n-2次的距离与n-3次比较;第四步要进行(n-3)×3次的距离计算及(n-4)×3次比较;第五步至多进行n-6次的距离计算与n-7次比较;第六步到第五步的循环次数不超过3n-9;因此整个贪心算法2的时间复杂性为
O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n2)
(三) 贪心算法贪心算法的思想非常简单且算法效率很高，在一些问题的解决上有着明显的优势。
假设有3种硬币，面值分别为1元、5角、1角。这3种硬币各自的数量不限，现在要找给顾客3元6角钱，请问怎样找才能使得找给顾客的硬币数量最少呢？
你也许会不假思索的说出答案：找给顾客3枚1元硬币，1枚5角硬币，1枚1角硬币。其实也可以找给顾客7枚5角硬币，1枚1角硬币。可是在这里不符合题意。在这里，我们下意识地应用了所谓贪心算法解决这个问题。
所谓贪心算法，就是总是做出在当前看来是最好的选择(未从整体考虑) 的一种方法。以上述的题目为例，为了找给顾客的硬币数量最少，在选择硬币的面值时，当然是尽可能地选择面值大的硬币。因此，下意识地遵循了以下方案：
（1）首先找出一个面值不超过3元6角的最大硬币，即1元硬币。
（2）然后从3元6角中减去1元，得到2元6角，再找出一个面值不超过2元6角的最大硬币，即1元硬币。
（3）然后从2元6角中减去1元，得到1元6角，再找出一个面值不超过1元6角的最大硬币，即1元硬币。
（4）然后从1元6角中减去1元，得到6角，再找出一个面值不超过6角的最大硬币，即5角硬币。
（5）然后从6角中减去5角，得到1角，再找出一个面值不超过1角的最大硬币，即1角硬币。
（6）找零钱的过程结束。
这个过程就是一个典型的贪心算法思想。
贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注：贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解。但其解必然是最优解的很好近似解。）
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。选择的贪心策略必须具备无后效性。

贪心算法经典例题 贪心算法( 三 )

秒懂生活扩展阅读

贪心算法经典例题贪心算法( 三 )