每日科技名词|贪婪算法
来源：全国科学技术名词审定委员会
贪婪算法
greedy algorithm
又称：贪心算法
定义：一种不追求全局最优解，只在每一步求得局部最优解的算法。
学科：计算机科学技术_理论计算机科学_算法设计与分析
相关名词：算法 最优子结构性
​贪婪算法是一种用于优化问题的简单、直观的算法。该算法在每个步骤进行最优选择，试图找到解决整个问题的总体最优方法。贪婪算法每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，在一些最优解问题的求解上表现得更简单、更迅速。
​如果求解问题具有贪婪选择属性与最优子结构属性，则可以使用贪婪算法解决。贪婪选择属性是指通过在每个步骤中选择最优选择，可以得到一个全局（总体）最优解。最优子结构是指如果整个问题的最优解包含子问题的最优解，那么问题就有最优子结构。
​有很多经典的应用，比如霍夫曼编码，普利姆和克鲁斯卡尔最小生成树算法，还有迪杰斯特拉单源最短路径算法，都是使用了这种思维。然而，在许多问题中，贪婪算法并不会产生最优解，因为贪婪算法没有考虑到所有的数据，当前结果都是基于它前一步的数据而计算出的局部最优结论，缺乏瞻前顾后和统筹全局的能力。所以在贪婪算法失败的问题中，动态规划可能会是更好的选择[OK] https://t.cn/A6XvcZ3N

打卡第65天
体重：49.4
生活：整理一下最近的思绪吧。

在宿舍也待了好一阵子，笔试面试什么的都不太理想。核酸，抗原，截图，排队，让我对生活近乎感到麻木。今天下午做中国银行的笔试被拉去核酸，艾，能不能运气爆棚，让我有个offer啊。

最近两天开始刷力扣了，主要是贪心算法这一块，提到了局部最优和全局最优，感觉这对生活也有一定的启发哈哈哈哈，短期目标和长期目标的确定和实现。

前些天和本科室友聊天，以及最近与现在室友聊天还是有些感慨的。在现在的生活状态之下，我一直觉得自己太过感性了，选择了城市再考研。因为后续打算去银行工作，就希望工作多少和金融有一点关系，发现中南财经政法大学才是最合理的选择，坐标武汉，学制两年，学费比现在少，奖学金多。哈哈哈哈哈哈，可是冷静下来，才发现当初支撑我考研的信念就是来上海，所以这些所谓的理性也不太存在了。况且，如果不来这边待两年，也会是后面生活中的遗憾吧。

在疫情后时代，经济和生活多多少少受到了影响。我透过自媒体平台也了解到了更多的水深火热，果然，人类的悲欢并不想通。很多人的起点、生活环境都不一样，所以也要认清现实，不能浑浑噩噩度日。还有，赚钱不是很轻松的事情，至少在一开始不是，还是要明白这一点了。

最近，也有重新认识核心利益、消费主义和所谓的稳定。其实，核心利益和情绪也有很多关系，不只是在关键决策的时候体现出来，可能在生气、在面对危险的时刻，如何规避风险，平衡自我或者及时改善局面。对于消费主义而言，只和不太富有的人有关系，因为日常消费确实是有利于经济发展的，而所谓的消费主义则是针对奢侈品的，没钱的人却疯狂的想要拥有，其他方面的开支自然会降低、生活质量下降；而对富人来说这些只是日用品罢了。对于最后的稳定，也不完全取决于是否有房，因为大部分人会因此负债，背上房贷会感到一定焦虑；而有些人自身各方面能力都很稳定，比如情绪稳定、工作能力稳定、人际关系稳定等等，所以在一定层面上，稳定感也来自于个人，不完全依赖于外部事务。

竟然把凸包拿出来了，很早之前复现过 Graham算法可惜已经忘得差不多了，极角排序没整出来，退而求其次去贪心扫描选边缘，共线情况炸两发WA总算ac。核心思想和Jarvis 算法是类似的，不过没想到力扣官解也在共线上栽跟头[笑而不语]，因为共线从二维退化到一维会丢失信息导致误判。这要求对于起点的选择要确保在边角上，而官解只是选了x坐标最左的点，没控制y坐标，p3构造一个反例可以把官解卡出TLE导致“预期结果”无法正常显示