贪默算法先容及应用

贪默算法是一种在求解优化题目时常用的算法战略。
根本概念
贪默算法在对题目求解时，总是做出在当前看来是最好的选择。也就是说，它不从团体最优上加以思量，而是在每一步的决议中都接纳当前状态下的最优决议。这种战略通常是局部最优解的选择，盼望通过一系列的局部最优选择来到达全局最优解，但并不能包管肯定能得到全局最优解。
工作流程

  

• 分解题目：将一个复杂的题目分解为一系列的子题目。比方，在找零题目中，把找零这个大题目分解为每次选择一种面额货币的子题目。  
  
• 确定贪婪战略：这是贪默算法的焦点。比如在运动安排题目中，贪婪战略是每次选择竣事时间最早的运动，由于如许可以为后续运动留出更多的时间。在背包题目（部门背包题目）中，贪婪战略是按照物品的代价与重量的比值（性价比）举行排序，优先选择性价比高的物品放入背包。  
  
• 按战略求解：根据确定的贪婪战略，一步一步地办理子题目。以运动安排为例，按照竣事时间最早的运动优先安排，依次查抄每个运动是否与已安排的运动辩论，不辩论就到场安分列表。
  

示例

  

• 找零题目
  
     
  
  • 假设货币的面额有10元、5元、1元。要找零18元，贪默算法的做法是：起首选择一张10元，此时还剩下8元；接着选择一张5元，剩下3元；末了选择3张1元。通过每次选择面额最大的货币，快速地完成找零。   
    
     
  
• 运动安排题目
  
     
  
  • 假设有一系列运动，每个运动都有开始时间和竣事时间。比如运动A（1,4），运动B（3,5），运动C（0,6），运动D（5,7），运动E（3,8）。按照贪婪战略（选择竣事时间最早的运动），起首选择运动A，由于它的竣事时间最早是4。然后查抄其他运动，发现运动B的开始时间3小于运动A的竣事时间4，以是运动B不能选。接着看运动C，开始时间0小于4，不能选。运动D开始时间5大于4，可以选。运动E开始时间3小于4，不能选。以是终极选择的运动是A和D，这是一种比力公道的运动安排方式。   
    
    
  

实用场景和范围性

  

• 实用场景：贪默算法实用于具有最优子布局性子的题目。即一个题目标最优解包罗其子题目标最优解。比方，在部门背包题目中，团体的最优装载方案中，对于背包的任何剩余容量部门，装入的物品组合也是在该剩余容量下的最优选择。  
  
• 范围性：由于贪默算法只是寻求局部最优，对于一些复杂的题目，大概会陷入局部最优陷阱，无法得到真正的全局最优解。比方观光商题目（TSP），假如使用贪默算法，每次选择间隔当前都会近来的都会作为下一站，很大概得到的是一个比力差的观光蹊径，而不是最短的全局蹊径。
  

贪默算法的应用案例:

  

• 任务调治题目
  
     
  
  • 场景形貌：假设有多个任务，每个任务都有一个完成时间和对应的收益。必要在有限的时间内安排任务，以得到最大的收益。   
    
  • 贪婪战略：按照单位时间收益（收益/完成时间）对任务举行排序，优先选择单位时间收益高的任务。比方，有任务A（收益为10，完成时间为2），任务B（收益为15，完成时间为3），任务C（收益为8，完成时间为1）。盘算单位时间收益，任务A为5，任务B为5，任务C为8。按照贪婪战略，先选择任务C，再思量任务A和B，如许可以在有限的时间内得到最大收益。   
    
     
  
• 哈夫曼编码
  
     
  
  • 场景形貌：在数据压缩范畴，必要将字符用二进制编码表现，使得总编码长度最短。   
    
  • 贪婪战略：构造哈夫曼树。起首将全部字符出现的频率统计出来，把频率最低的两个节点归并为一个新节点，新节点的频率为这两个节点频率之和。不绝重复这个过程，直到形成一棵二叉树。字符的编码就是从根节点到该字符节点的路径，左子树路径为0，右子树路径为1。通过这种贪婪的构建方式，使得出现频率高的字符编码较短，从而实现数据的高效压缩。比方，对于字符集{a: 5, b: 9, c: 12, d: 13, e: 16}，构建哈夫曼树后，a的编码大概较长，而e的编码较短，终极实现团体编码长度的优化。   
    
     
  
• 最小天生树题目 - 普利姆（Prim）算法
  
     
  
  • 场景形貌：给定一个带权无向图，要找到一棵天生树，使得树上全部边的权值之和最小。   
    
  • 贪婪战略：从恣意一个顶点开始，每次选择一条权值最小的边，将一个尚未在树中的顶点到场到天生树